【最新华为OD机试E卷】字符串变换最小字符串(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

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

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目正在持续上线中~

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

✨ 字符串变换最小字符串

问题描述

给定一个由小写字母组成的字符串 ，你可以最多进行一次变换操作。变换操作的规则是：交换字符串中任意两个不同位置的字符。请返回经过变换后能得到的字典序最小的字符串。

输入格式

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

输出格式

输出一行，表示经过最多一次变换后得到的字典序最小的字符串。

样例输入

abcdef

样例输出

abcdef

样例解释

字符串 "abcdef" 已经是字典序最小的，不需要进行任何交换操作。

样例输入

bcdefa

样例输出

acdefb

样例解释

将 'a' 和 'b' 交换位置，可以得到字典序最小的字符串 "acdefb"。

数据范围

• 字符串 仅由小写字母组成。
• ，其中 表示字符串 的长度。

题解

这道题目的核心思想是找到字符串中第一个不在正确位置上的字符，然后将它与后面最小的字符交换。

具体步骤如下：

1. 首先，将输入的字符串 排序，得到一个新的字符串 。这个排序后的字符串就是理论上能得到的字典序最小的字符串。

2. 比较原字符串 和排序后的字符串 。如果它们相同，说明原字符串已经是字典序最小的，直接返回原字符串。

3. 如果不同，那么我们需要进行一次交换操作。从左到右遍历原字符串 ，找到第一个与 中对应位置不同的字符。

4. 在原字符串 中，从右向左找到与这个字符相等的字符（即 中对应位置的字符）。

5. 交换这两个字符的位置。

参考代码

• Python

def solve(s):
    # 将输入字符串转换为列表，方便操作
    s_list = list(s)
    # 对字符串进行排序，得到理论上的最小字符串
    sorted_s = sorted(s)
    
    # 如果原字符串已经是最小的，直接返回
    if s_list == sorted_s:
        return s
    
    # 找到第一个不在正确位置的字符
    for i in range(len(s)):
        if s_list[i] != sorted_s[i]:
            # 从右向左找到要交换的字符
            j = s.rindex(sorted_s[i])
            # 交换字符
            s_list[i], s_list[j] = s_list[j], s_list[i]
            break
    
    # 将列表转换回字符串并返回
    return ''.join(s_list)

# 读取输入
s = input().strip()

# 输出结果
print(solve(s))

• C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LEN 1001

// 比较函数，用于qsort
int cmp(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}

// 解决问题的函数
void solve(char *s) {
    int len = strlen(s);
    char sorted_s[MAX_LEN];
    strcpy(sorted_s, s);
    
    // 对sorted_s进行排序
    qsort(sorted_s, len, sizeof(char), cmp);
    
    // 如果原字符串已经是最小的，直接