最新华为OD机试真题-字符串变换(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 字符串变换(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🫐 字符串变换

问题描述

K小姐有一个由小写字母组成的字符串 。现在她想对字符串 进行变换，使得变换后的字符串字典序最小。

变换的规则是：在字符串中选择任意两个不同位置的字符，然后交换它们的位置。K小姐最多只能进行一次这样的变换。

请你帮助K小姐找到变换后字典序最小的字符串。

输入格式

输入一行，包含一个由小写字母组成的字符串 。

输出格式

输出一行，表示变换后字典序最小的字符串。

样例输入1

abcdef

样例输出1

abcdef

样例输入2

bcdefa

样例输出2

acdefb

数据范围

，其中 表示字符串 的长度。

题解

可以先将字符串 转换为字符数组，然后对该数组进行排序，得到字典序最小的字符串 。如果 和 相同，说明 已经是字典序最小的字符串，直接返回 即可。

否则，从左到右遍历字符串 ，找到第一个与 对应位置字符不同的位置 。然后在 中从右往左找到最后一个等于 的位置 ，交换 和 ，即可得到字典序最小的字符串。

时间复杂度为 ，空间复杂度为 。其中 为字符串 的长度。时间复杂度 ，空间复杂度 。其中 为字符串长度。

参考代码

• Python

s = input()

def getResult():
    min_s = sorted(s)
    
    if s == ''.join(min_s):
        return s
    
    s_list = list(s)
    
    for i in range(len(s)):
        if s_list[i] != min_s[i]:
            j = s.rindex(min_s[i])
            s_list[i], s_list[j] = s_list[j], s_list[i]
            break
    
    return ''.join(s_list)

print(getResult())

• Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(getResult(s));
    }
    
    private static String getResult(String s) {
        char[] minArr = s.toCharArray();
        Arrays.sort(minArr);
        String minStr = new String(minArr);
        
        if (s.equals(minStr)) {
            return s;
        }
        
        char[] sArr = s.toCharArray();
        
        for (int i = 0; i < s.length(); i++) {
            if (sArr[i] != minArr[i]) {
                int j = s.lastIndexOf(minArr[i]);
                swap(sArr, i, j);
                break;
            }
        }
        
        return new String(sArr);
    }
    
    private static void swap(char[] arr, int i, int j) {
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

• Cpp

#include <iostream>
#include <algorithm>
using namespace std;

string getResult(string s) {
    string minStr = s;
    sort(minStr.begin(), minStr.end());
    
    if (s == minStr) {
        return s;
    }
    
    for (int i = 0; i < s.length(); i++) {
        if (s[i] != minStr[i]) {
            int j = s.find_last_of(minStr[i]);
            swap(s[i], s[j]);
            break;
        }
    }
    
    return s;
}

int main() {
    string s;
    cin >> s;
    cout << getResult(s) << endl;
    return 0;
}