排序 (蓝桥杯) JAVA
目录
- 题目描述:
- 冒泡排序算法(排序数字,字符):
- String与String buffer的区别:
- 纯暴力破解(T到爆炸):
- 暴力破解加思考(bingo):
- 总结:
题目描述:
小蓝最近学习了一些排序算法,其中冒泡排序让他印象深刻。 在冒泡排序中,每次只能交换相邻的两个元素。
小蓝发现,如果对一个字符串中的字符排序,只允许交换相邻的两个字符,则在所有可能的排序方案中,冒泡排序的总交换次数是最少的。
例如,对于字符串lan 排序,只需要1 次交换。对于字符串qiao 排序,总共需要4 次交换。
小蓝找到了很多字符串试图排序,他恰巧碰到一个字符串,需要100 次交换,可是他忘了吧这个字符串记下来,现在找不到了。
请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串,对该串的字符排序,正好需要100
次交换。如果可能找到多个,请告诉小蓝最短的那个。如果最短的仍然有多个,请告诉小蓝字典序最小的那个。
这是一道结果填空的题,你只需要算出结果后提交即可。
本题的结果为一个只包含小写英文字母的字符串,在提交答案时只填写这个字符串,填写多余的内容将无法得分。
答案:jonmlkihgfedcba
冒泡排序算法(排序数字,字符):
理解:
冒泡排序的正序排序,整个实现过程,就类似气泡从水底,到水面的过程,即越到水面,气泡越大,在排序过程中也是如此,每次排序都会将数值最大的数,挪到数组后端。
冒泡排序正序排列数字代码如下:
public static void maopao(int a[]) {for(int i = 0; i < a.length; i ++)for(int j = 0; j < a.length - i - 1; j ++) {if(a[j] > a[j + 1]) { int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}
冒泡排序正序排列字符代码如下:
public static void maopao(char a[]) {for(int i = 0; i < a.length; i ++)for(int j = 0; j < a.length - i - 1; j ++) {if(a[j] > a[j + 1]) { char temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}
String与String buffer的区别:
思路:
在暴力破解的代码中我用到了StringBuffer存储字符串,为什么不用String存储呢,因为String储存的字符串有时候不可变动,StringBuffer可以。以下为两者在被函数调用的区别:
代码:
import java.nio.Buffer;public class text {public static void main(String[] args) {StringBuffer s = new StringBuffer("abcd");String s1 = "abcd";add(s);add(s1);System.out.println(s);System.out.print(s1);}public static void add(String s) {s = s + 'A';}public static void add(StringBuffer s) {s.append('A');}}
输出:
可以看出,StringBuffer,被调用后内容更新了,而String 没有被更新
以下是StringBuffer 的一些基本函数的用法:
1. delete(0 , 1) : 删除[0 , 1)区间内的字符
2. insert (0, 'a') : 将字符 a 插入0的位置
3. appand( 'a' ) :将字符a添加到末尾。
纯暴力破解(T到爆炸):
解题思路:
所谓纯暴力,就是不加思索,直接用 dfs + 回溯思想,一个一个遍历直到找到符合条件的字符串。这里将冒泡排序进行了一些改进,让其能够记数:
冒泡排序记数代码如下:
public static int maopao(char a[]) {int sum = 0;for(int i = 0; i < a.length; i ++)for(int j = 0; j < a.length - i - 1; j ++) {if(a[j] > a[j + 1]) { char temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;sum ++;}}return sum;}
纯暴力完整代码如下:
import java.util.*;public class Main{public static char a[] = new char[26];public static boolean b[] = new boolean[26];public static void main(String[] args){ a[0] = 'a';for(int i = 1; i <= 25; i ++) {a[i] = (char)(a[i - 1] + 1);}StringBuffer s = new StringBuffer("ihgfedcba");for(int i = 0; i < 26; i ++) {b[i] = true;dfs(a[i], s);b[i] = false;s = s.delete(0, 1);}}public static int maopao(char a[]) {int sum = 0;for(int i = 0; i < a.length; i ++)for(int j = 0; j < a.length - i - 1; j ++) {if(a[j] > a[j + 1]) { char temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;sum ++;}}return sum;}public static void dfs(char d, StringBuffer s) {s = s.insert(0, d);String s1 = new String(s);char c[] = s1.toCharArray();if(maopao(c) == 100) {print(s);return;}for(int i = 0; i < 26; i ++) {if(b[i] == false) {b[i] = true;dfs(a[i], s);b[i] = false;s.delete(0, 1);}}}public static void print(StringBuffer s) {System.out.println(s);}
}
大家也别运行这个代码了,我粗略地算了一下,要得出结果至少要 26!/ 10^9 / 3600 = …小时。 😭数据太大了不足以用年来计量了😭我只能说我是真SB
。
暴力破解加思考(bingo):
解题思路:
所以做这种填空题,纯暴力是吃力不讨好的,我们应该尽可能的大胆去思考,大胆去猜测,去举例论证,以减小我们搜索的范围。
1.首先明确题目要求,字符最少,且字典序最小,不能重复。
所以左端应该越接近a越好,例如:......dcba, 这种序列交换次数也很大,所以相应需要的字符也少。
对冒泡排序的核心代码进行分析:
对于上述推测的字符串类型,可以发现每次运行都会交换次序,我们可以用 cba,ba,带入冒泡排序去推规律,不难发现,交换次数 N = (x - 1 + x - 2 + x - 3 + … + 0)化简得到:N = x * (x - 1) / 2
可以算出 x = 15 时 N = 105。
也可以对上述纯暴力代码修改,让其输出,第一个大于 100 次交换次序的数列:
import java.util.*;public class Main{public static char a[] = new char[26];public static boolean b[] = new boolean[26];public static void main(String[] args){ a[0] = 'a';for(int i = 1; i <= 25; i ++) {a[i] = (char)(a[i - 1] + 1);}StringBuffer s = new StringBuffer("");for(int i = 0; i < 26; i ++) {b[i] = true;dfs(a[i], s);b[i] = false;s = s.delete(0, 1);}}public static int maopao(char a[]) {int sum = 0;for(int i = 0; i < a.length; i ++)for(int j = 0; j < a.length - i - 1; j ++) {if(a[j] > a[j + 1]) { char temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;sum ++;}}return sum;}public static void dfs(char d, StringBuffer s) {s = s.insert(0, d);String s1 = new String(s);char c[] = s1.toCharArray();if(maopao(c) >= 100) {print(s);return;}for(int i = 0; i < 26; i ++) {if(b[i] == false) {b[i] = true;dfs(a[i], s);b[i] = false;s.delete(0, 1);}}}public static int k = 1;public static void print(StringBuffer s) {if(k > 0)System.out.println(s);k --;}
}
输出:
-那么问题来了,上述字符串的交换次序是105
要想让交换次序变成100,有两种方案,1. 让一个字符少换5次,2.让5个字符都少交换1次,整体少交换5次
1.让一个字符少交换5次 :
即把某个字符往前移动即可:
例如:
onmlkjihgfedcba
让 o
少交换5次
得nmlkjoihgfedcba
刚好交换次数为100
这种方式如果将最后一个字母向前移动的话,是可以将字典序变小的。
我们再来看看让五个字符都少交换1次的方法。
2.让五个字符都少交换1次,整体少交换5次 :
即将onmlkjihgfedcba
中某个字符向后移动,这样其他字符就会少交换一次
为了让交换后的字典序尽可能小,且满足交换次序为100次,我们最好是将中间某个字符放到尾部,这样字典序就小的更多。
满足上述要求我们发现将j
交换到尾部刚好能满足条件即:
jonmlkihgfedcba
也就是我们的最终答案
总结:
这道题难度不言而喻,思维量很大,对我来说很难。所以,我们不能小看蓝桥杯的小题,没有把握的填空题可能真的没必要钻牛角尖去s
扣它不放,而导致后面大题能骗或者搞到分的地方没有时间。适当放弃就要放弃,等能得的分都得到了,再来会会它也不迟,这里更是提醒我自己,我本人就爱怒怼一道题s
扣不放。要明白,我们的目的是尽可能得我们能得的分,而不是将所有题做对。把我们的努力成果好好的发挥出来。能够权衡什么是西瓜什么是芝麻并灵活应对也是一个合格程序员该具备的能力不是么?😁
相关文章:

排序 (蓝桥杯) JAVA
目录题目描述:冒泡排序算法(排序数字,字符):String与String buffer的区别:纯暴力破解(T到爆炸):暴力破解加思考(bingo):总结:题目描述: 小蓝最近学习了一些排序算法,其中冒泡排序让他…...

【Blender 水墨材质】实现过程剖析01
写在前面 想把Blender一位大佬演示的Blender水墨材质过程,在Unity用Shader重现,过程中会拿能拿到的节点代码举例(ShaderGraph或者UE的都会有)。第一步当然是要跟着人家做一遍!我会尽可能地分析一下每一步的原理~ 教程…...
代码随想录算法训练营第五十六天|583. 两个字符串的删除操作、72. 编辑距离
LeetCode 583 两个字符串的删除操作 题目链接:https://leetcode.cn/problems/delete-operation-for-two-strings/ 思路: 方法一:两个子串同时删除元素 dp数组的含义 dp[i][j]dp[i][j]dp[i][j]代表以i-1为结尾的字符串word1,和以j-1位结…...

【ArchLinux】【KDE】Archlinux的安装与使用
文章目录开头前言所需环境演示环境相关链接安装教程在Windows环境下制作启动盘进入ArchLinux Live环境安装为硬盘分区如何新建分区?分区表格式化分区分区完成,开始安装挂载分区切换镜像源安装基本系统设置将Live环境(当前)挂载信息…...

Go语言精修(尚硅谷笔记)第六章
六、函数、包和错误处理 6.1 函数概念 不用函数的弊端 1)写法可以完成功能, 但是代码冗余 2 ) 同时不利于代码维护 概念:为完成某一功能的程序指令(语句)的集合,称为函数。 在Go中,函数分为: 自定义函数、系统函数 基本语法 //函数的基本语法 fu…...
Photoshop的功能
Photoshop是一款功能强大的图片编辑软件,它提供了数百种不同的工具和特效,让您可以编辑图片、创建图形和设计网页等。 以下是Photoshop的一些主要功能: 1.图层:Photoshop允许您创建多个图层,让您可以在每一个图层上进…...

C++初阶——内存管理
目录 1. C/C内存分布 2. C语言中动态内存管理方式:malloc/calloc/realloc/free 3. C内存管理方式 3.1 new/delete操作内置类型 3.2 new和delete操作自定义类型 4. operator new与operator delete函数 重要 4.1 operator new与operator delete函数(…...

uds服务汇总
还有一些服务列举在下面: RequestDownload(服务ID为0x34)和RequestUpload(服务ID为0x35):这两个服务用于在ECU和诊断器之间进行数据传输。通过 RequestDownload服务,诊断器可以请求ECU接收一些数…...
【深度学习】2023李宏毅homework1作业一代码详解
研一刚入门深度学习的小白一枚,想记录自己学习代码的经过,理解每行代码的意思,这样整理方便日后复习也方便理清自己的思路。感觉每天时间都不够用了!!加油啦。 第一部分:导入模块 导入各个模块࿰…...

【软件测试】基础知识第二篇
文章目录一. 开发模型1. 瀑布模型2. 螺旋模型3. 增量和迭代模型3.1 增量模型3.2 迭代模型3.3 增量和迭代模型的区别4. 敏捷模型4.1 敏捷宣言4.2 scrum模型二. 开发模型V 模型W 模型一. 开发模型 1. 瀑布模型 瀑布模型在软件工程中占有重要地位,是所有其他模型的基…...
Java中File类以及初步认识流
1、File类操作文件或目录属性 (1)在Java程序中通过使用java.io包提供的一些接口和类,对计算机中的文件进行基本的操作,包括对文件和目录属性的操作、对文件读写的操作; (2)File对象既可以表示…...

【C语言】文件操作详细讲解
本章要分享的内容是C语言中文件操作的内容,为了方便大家学习,目录如下 目录 1.为什么要使用文件 2.什么是文件 2.1 程序文件 2.2 数据文件 2.3 文件名 3.文件的打开和关闭 3.1文件指针 3.2打开和关闭 4.文件的顺序读写 4.1顺序读写函数介绍…...

爱奇艺万能联播使用教程
众所周知,爱奇艺是百度旗下的一款产品,所以今天用爱奇艺万能联播的方法实现下载百度网盘,并没有破解百度网盘,是官方正版下载渠道。软件是官方版本,大家双击安装即可。 安装完成以后,在软件中就有了“访问网…...

真题讲解-软件设计(三十七)
数据流图DFD(真题讲解)-软件设计(三十六)https://blog.csdn.net/ke1ying/article/details/129803164 在网络安全管理中,加强内防内控可采取的策略是? 终端访问权限,防止合法终端越权访问。加强…...

Android 上的协程(第一部分):了解背景
本系列文章 Android 上的协程(第一部分):了解背景 Android 上的协程(第二部分):入门 Android上的协程 (第三部分): 实际应用 Android 上的协程(第一部分):了解背景 这篇…...
【H3C】VRRP2 及Vrrp3基本原理 华为同用
文章目录VRRP2基本概念报文格式主备选举规则(优先级)0和255双Master原因VRRP认证VRRP状态机抢占模式VRRP主备切换状态项目场景VRRP3H3C参考致谢VRRP2 基本概念 VRRP路由器(VRRP Router):运行VRRP的设备,它…...

【数据库】SQL语法
目录 1. 常用数据类型 2. 约束 3. 数据库操作 4. 数据表操作 查看表 创建表格 添加数据 删除数据 修改数据 单表查询数据 多表查询数据 模糊查询 关联查询 连接查询 数据查询的执行顺序 4. 内置函数 1. 常用数据类型 整型:int浮点型:flo…...

JavaEE简单示例——文件的上传和下载
文件的上传和下载的实现原理的简单介绍 表单的构成 首先,我们先来介绍我们的需要用到的表单,在这个表单中,首先值得我们注意的就是,在type为file的input标签中.这个控件是我们主要用来选择上传的文件的, 除此之外,我们要想实现文件的上传,还需要将method的属性的值设置为post…...

【C语言督学训练营 第五天】数组字符串相关知识
文章目录前言一、数组的定义1.一维数组①.如何定义②.声明规则③.内存分布④.初始化方法2.二维数组3.高维数组二、访问数组元素相关问题1.访问越界2.数组的传递三、Scanf与字符数组1.字符数组初始化2.scanf读取字符四、字符数组相关函数前言 今天的C语言训练营没有安排高维数组…...

GPT-4 免费体验方法
POE 在Quora上非常受欢迎的手机聊天机器人Poe App已经集成ChatGPT助手!除了最初集成的三个聊天机器人Sage、Claude和Dragonfly外,Poe现在还加入了第四位ChatGPT。由于使用了ChatGPT API,因此Poe拥有真正的ChatGPT。 现在更是第一批集成了GP…...

【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...

面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...

力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...