【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为s
                ans = s
                # 获得字符串s的长度n
                n = len(s)
                # 将s转化列表，方便交换操作
                lst = list(s)
                # 枚举下标i和下标j
                for 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