华为OD机试E卷 --字符串变换最小字符串 --24年OD统一考试（Java JS Python C C++）

题目描述

给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。 变换规则：交换字符串中任意两个不同位置的字符。

输入描述

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

输出描述

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

用例

输入

abcdef

输出

abcdef

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

输入

bcdefa

输出

acdefb

说明
a和b进行位置交换，可以得到最小字符串

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

题目解析

1. 遍历字符串：从左到右遍历字符串，找到第一个可以交换的位置。
2. 寻找最小字符：对于每个字符，从当前位置之后的字符中找到最小的字符。
3. 交换字符：如果找到的最小字符比当前字符小，则进行交换。
4. 返回结果：如果进行了交换，返回交换后的字符串；如果没有进行交换，返回原字符串。

JS算法源码

function getMinString(s) {let chars = s.split('');let n = chars.length;for (let i = 0; i < n - 1; i++) {let minChar = chars[i];let minIndex = i;for (let j = i + 1; j < n; j++) {if (chars[j] < minChar) {minChar = chars[j];minIndex = j;}}if (minIndex !== i) {[chars[i], chars[minIndex]] = [chars[minIndex], chars[i]];return chars.join('');}}return s;
}// 示例输入
const s = "acb";
console.log(getMinString(s)); // 输出 "abc"

java算法源码

public class Main {public static String getMinString(String s) {char[] chars = s.toCharArray();int n = chars.length;for (int i = 0; i < n - 1; i++) {char minChar = chars[i];int minIndex = i;for (int j = i + 1; j < n; j++) {if (chars[j] < minChar) {minChar = chars[j];minIndex = j;}}if (minIndex != i) {char temp = chars[i];chars[i] = chars[minIndex];chars[minIndex] = temp;return new String(chars);}}return s;}public static void main(String[] args) {String s = "acb";System.out.println(getMinString(s)); // 输出 "abc"}
}

python算法源码

def get_min_string(s):chars = list(s)n = len(chars)for i in range(n - 1):min_char = chars[i]min_index = ifor j in range(i + 1, n):if chars[j] < min_char:min_char = chars[j]min_index = jif min_index != i:chars[i], chars[min_index] = chars[min_index], chars[i]return ''.join(chars)return s# 示例输入
s = "acb"
print(get_min_string(s))  # 输出 "abc"

c算法源码

#include <stdio.h>
#include <string.h>char* getMinString(char* s) {int n = strlen(s);for (int i = 0; i < n - 1; i++) {char minChar = s[i];int minIndex = i;for (int j = i + 1; j < n; j++) {if (s[j] < minChar) {minChar = s[j];minIndex = j;}}if (minIndex != i) {char temp = s[i];s[i] = s[minIndex];s[minIndex] = temp;return s;}}return s;
}int main() {char s[101];scanf("%s", s);printf("%s\n", getMinString(s));return 0;
}

c++算法源码

#include <iostream>
#include <string>
#include <algorithm>std::string getMinString(std::string s) {int n = s.length();for (int i = 0; i < n - 1; i++) {char minChar = s[i];int minIndex = i;for (int j = i + 1; j < n; j++) {if (s[j] < minChar) {minChar = s[j];minIndex = j;}}if (minIndex != i) {std::swap(s[i], s[minIndex]);return s;}}return s;
}int main() {std::string s;std::cin >> s;std::cout << getMinString(s) << std::endl;return 0;
}