华为OD机试真题---字符串变换最小字符串

---

题目描述:

给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串(按照字典序进行比较)。

变换规则:

交换字符串中任意两个不同位置的字符。

输入描述:

一串小写字母组成的字符串s

输出描述:

按照要求进行变换得到的最小字符串

补充说明:

s是都是小写字符组成
1<=s.length<=1000

示例

示例1

输入:abcdef
输出:abcdef
说明:abcdef已经是最小字符串，不需要交换

示例2

输入:bcdefa
输出:acdefb
说明:a和b进行位置交换，可以等到最小字符串

在Java中，我们可以实现一个函数来找到可以通过最多一次字符交换得到的字典序最小的字符串。以下是一个可能的实现：

---

代码实现

public class MinStringBySwap {public static String getMinStringBySwap(String s) {// 将字符串转换为字符数组char[] chars = s.toCharArray();// 复制一份排序后的字符数组，用于比较char[] sortedChars = chars.clone();java.util.Arrays.sort(sortedChars);// 如果原字符串已经是排序后的，直接返回if (java.util.Arrays.equals(chars, sortedChars)) {return s;}// 查找需要交换的字符位置int i = 0;while (i < chars.length && chars[i] == sortedChars[i]) {i++;}// 从后向前查找可以交换的字符位置int j = chars.length - 1;while (j > i && chars[j] != sortedChars[i]) {j--;}// 交换字符if (j > i) {char temp = chars[i];chars[i] = chars[j];chars[j] = temp;}// 将字符数组转换回字符串并返回return new String(chars);}public static void main(String[] args) {// 测试示例1String s1 = "abcdef";System.out.println(getMinStringBySwap(s1));  // 输出: abcdef// 测试示例2String s2 = "bcdefa";System.out.println(getMinStringBySwap(s2));  // 输出: acdefb}
}

解释

1. 字符数组转换和排序：

   • 将输入字符串转换为字符数组chars。
   • 复制一份字符数组并排序，得到sortedChars。

2. 检查是否已排序：

   • 如果chars和sortedChars相同，说明字符串已经是字典序最小的，直接返回原字符串。

3. 查找交换位置：

   • 使用变量i从前往后遍历chars，找到第一个与sortedChars不匹配的字符位置。
   • 使用变量j从后往前遍历chars，找到最后一个与sortedChars[i]相等的字符位置。

4. 字符交换：

   • 如果找到了合适的i和j，则交换chars[i]和chars[j]。

5. 返回结果：

   • 将交换后的字符数组转换回字符串并返回。

这个算法的时间复杂度主要由排序步骤决定，为O(n log n)，其中n是字符串的长度。空间复杂度为O(n)，因为需要复制一份字符数组进行排序。