题目描述:
给定一个字符串s,最多只能进行一次变换,返回变换后能得到的最小字符串(按照字典序进行比较)。
变换规则:交换字符串中任意两个不同位置的字符。
输入描述:
一串小写字母组成的字符串s
输出描述:
按照要求进行变换得到的最小字符串
补充说明:
s是都是小写字符组成
1<=s.length<=1000
示例1
输入:
abcdef
输出:
abcdef
说明:
abcdef已经是最小字符串,不需要交换
示例2
输入:
bcdefa
输出:
acdefb
说明:
a和b进行位置交换,可以等到最小字符串
解题思路: 这个跟冒泡算法差不多,就是相邻两个进行比较,双重for循环来诸葛交换找到最小
package com.xiaomi.immonitorcenter;import jdk.nashorn.internal.runtime.regexp.joni.exception.SyntaxException;import java.util.Scanner;public class Main {public String minStringAfterSwap(String s){String res = s;char[] chars = s.toCharArray();int n = s.length();for(int i = 0; i < n; i++) {for(int j = i+1; j < n; j++) {swap(chars, i, j);if(res.compareTo(String.valueOf(chars)) > 0) {res = String.valueOf(chars);}}}return res;}public void swap(char[] chars, int i, int j) {char t = chars[i];chars[i] = chars[j];chars[j] = t;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s = scanner.nextLine();String res = new Main().minStringAfterSwap(s);System.out.println(res);}
}