题目要求:
给一个字符串s,你可以至多选择两个不同位置的字符进行交换(可以不交换),问所有可能中字典序最小的串。
输入:aaazbcdeadcd
输出:aaaabcdezdcd
题目解析:
字典序最小 即与当前字符串相比最小的字符串
那么只需要找到字符串中前面一个字符与后面一个字符之间差距最大且前大于后的一组字符交即可
从后向前遍历 与当前元素之前的所有元素比较并记录 交换
java代码:
public class Main {
public static void main(String[] args) {
String string = "aaazbcdeadcd";
int num = 0;
char[] cs = string.toCharArray();
int flag1 = cs.length - 1;
int flag2 = 0;
for (int i = cs.length-1;i>0;i--) {
for (int j = 0;j < i;j++) {
if(num < cs[j] - cs[i]) {
num = cs[j] - cs[i];
flag1 = i;
flag2 = j;
}
}
}
char c = cs[flag2];
cs[flag2] = cs[flag1];
cs[flag1] = c;
for(int i = 0;i<cs.length;i++) {
System.out.print(cs[i]);
}
}
}
欢迎提出问题并指正~