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

文章目录

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

                题目描述与示例

                题目描述

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

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

                输入描述

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

                输出描述

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

                补充说明

                s是都是小写字符组成

                1  stack[-1]:        if lst[i] > 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));    }}
                 
                C++
                 
                #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