【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【贪心/栈】2024D-变换最小字符串【欧弟算法】全网注释最详细分类最全的华为OD真题题解

有LeetCode算法/华为OD考试扣扣交流群可加 948025485

可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题

绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

文章目录

• 题目描述与示例
• • 题目描述
  • 输入描述
  • 输出描述
  • 补充说明
  • 示例一
  • • 输入
    • 输出
    • 说明
    • 示例二
    • • 输入
      • 输出
      • 说明
      • 解题思路
      • • 暴力法
        • 为什么是贪心
        • 一个带图的例子
        • 代码
        • • 解法一：暴力法
          • • python
            • java
            • cpp
            • 时空复杂度
            • 解法二：贪心
            • • python
              • java
              • cpp
              • 时空复杂度
              • 华为OD算法/大厂面试高频题算法练习冲刺训练

                从2024年4月15号开始，OD机考全部配置为2024D卷。

                注意两个关键点：

                1. 会遇到C卷复用题。虽然可能存在幸存者偏差，但肯定还会有一大部分的旧题。
                2. 现在又支持做完题目之后倒回去改了。就是可以先做200的再做100的，然后可以反复提交。

                题目描述与示例

                题目描述

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

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

                输入描述

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

                输出描述

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

                补充说明

                s是都是小写字符组成

                1  lst[stack[-1]]:            lst[i], lst[stack[-1]] = lst[stack[-1]], lst[i]            ans = "".join(lst)            break        else:            continue    else:        stack.pop()

                一个带图的例子

                再举一个例子，s = "aabcbcdcd"，答案应该为ans = "aabbccdcd"，可以做出如下图

                逆序遍历字符串s，构建栈stack = [8, 7, 4, 1]，为可能进行交换的那些对应字符字典序较小且靠后的位置。

                正序遍历i，反复拿出栈顶索引对应的元素s[stack[-1]]对应的字符和i对应的元素s[i]进行比较。会经历如下过程。

                i

                i

                代码

                解法一：暴力法

                python

                # 题目：【贪心】2023C-变换最小字符串# 分值：100# 作者：闭着眼睛学数理化# 算法：暴力# 代码看不懂的地方，请直接在群上提问# 输入原字符串s = input()# 初始化答案ans为sans = s# 获得字符串s的长度nn = len(s)# 将s转化列表，方便交换操作lst = list(s)# 枚举下标i和下标jfor i in range(n-1):    for j in range(i+1, n):        # 令下标对(i, j)对应的两个字符进行交换        lst[i], lst[j] = lst[j], lst[i]        # 把交换后得到的字符串和ans进行比较，更新ans        ans = min("".join(lst), ans)        # 判断完毕后，下标对(i, j)对应的两个字符重新交换回去        lst[i], lst[j] = lst[j], lst[i]print(ans)

                java

                import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        String s = scanner.nextLine();        char[] ans = s.toCharArray();        int n = s.length();        for (int i = 0; i  
                cpp
                 
                #include #include int main() {    std::string s;    std::cin >> s;    std::string ans = s;    int n = s.length();    for (int i = 0; i  lst[stack.peek()]) {                    char temp = lst[i];                    lst[i] = lst[stack.peek()];                    lst[stack.peek()] = temp;                    ans = new String(lst).toCharArray();                    break;                }                // 否则，考虑下一个i            }            // 如果当前下标i不位于栈顶元素stack.peek()的左边            // 则弹出栈顶元素，考虑下一个字典序较大但是位于较右位置的字符            else {                stack.pop();            }        }        System.out.println(new String(ans));    }}
                 
                cpp
                 
                #include #include #include int main() {    std::string s;    std::cin >> s;    std::vector ans(s.begin(), s.end());    int n = s.length();    std::vector lst(s.begin(), s.end());    std::stack stack;    // 逆序遍历字符串s    for (int i = n - 1; i >= 0; i--) {        // 如果栈是空栈，或者当前下标i对应的字符lst[i]小于栈顶下标对应的字符lst[stack.top()]        // 则将坐标i加入stack        if (stack.empty() || lst[i]  lst[stack.top()]) {                std::swap(lst[i], lst[stack.top()]);                ans = lst;                break;            }            // 否则，考虑下一个i        }        // 如果当前下标i不位于栈顶元素stack.top()的左边        // 则弹出栈顶元素，考虑下一个字典序较大但是位于较右位置的字符        else {            stack.pop();        }    }    std::cout