前言
工作了十几年,从普通的研发工程师一路成长为研发经理、研发总监。临近40岁,本想辞职后换一个相对稳定的工作环境一直干到老, 没想到离职后三个多月了还没找到工作,愁肠百结。为了让自己有点事情做,也算提高一下自己的编程能力,无聊之余打算用一些大厂的编程题练练手。希望通过这些分享能够帮到一些人,也希望能和看到此文的大神们沟通交流,提升自己,更希望在此期间能够找到一份理想的工作。
题目描述
给定一个字符串s,最多只能进行一次变换,返回变换后能得到的最小字符串(按照字典序进行比较)。变换规则:交换字符串中任意两个不同位置的字符。
输入
一串小写字母组成的字符串s
备注
- s是都是小写字符组成
- 1<=s.length<=1000
输出
一串小写字母组成的字符串s
示例
示例1
输入
abcdef
输出
abcdef说明
abcdef已经是最小字符串,不需要交换。
示例2
输入
bcdefa
输出
acdefb
说明
a和b进行位置交换,可以得到最小字符串。
解题思路
因为要找最小字符串,所有后面替换的字符串越靠后越小。
题解
Java实现
package huawei.e100;
import java.util.Arrays;
import java.util.Scanner;
/**
* @author arnold
* @date 2024年12月19日
* 字符串变换最小字符串
*/
public class T30 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
String str = sc.nextLine();
String s = run(str);
System.out.println(s);
}
}
static String run(String str) {
// 判断是否是最小字符串
char[] cs = str.toCharArray();
Arrays.sort(cs);
if (new String(cs).equals(str)) {
return str;
}
// 查找最优的字符和位置
char minchar = Character.MAX_VALUE;
int changeIndexStart = cs.length-1;
int changeIndexEnd = 0;
for (int i = 0; i < cs.length-1 && i <= changeIndexStart; i++) {
for (int j = i+1; j < cs.length; j++) {
if(str.charAt(j) < str.charAt(i) && str.charAt(j) <= minchar) {
minchar = str.charAt(j);
changeIndexStart = i;
changeIndexEnd = j;
}
}
}
// 交换位置
cs = str.toCharArray();
cs[changeIndexEnd] = cs[changeIndexStart];
cs[changeIndexStart] = minchar;
return new String(cs);
}
}
标签:OD,String,变换,30,最小,cs,str,字符串
From: https://blog.csdn.net/arnold66/article/details/144587883