【华为OD机试真题2023C&D卷Python&C++】字符串变换最小字符串

迷南。 2024-02-05 16:35 42阅读 0赞

> ## 华为OD2023（C&D卷）机试题库全覆盖，刷题指南点[这里][Link 1] ##

> ## 字符串变换最小字符串 ##
> 
> 知识点字符串
> 
> 时间限制：1s 空间限制：256MB 限定语言：不限
> 
> ### 题目描述： ###
> 
> **给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。**
> 
> **变换规则：交换字符串中任意两个不同位置的字符。**
> 
> ####    输入描述： ####
> 
> 一串小写字母组成的字符串s
> 
> #### 输出描述： ####
> 
> 按照要求进行变换得到的最小字符串
> 
> #### 补充说明： ####
> 
> s是都是小写字符组成
> 
> 1<=s.length<=1000

> ### 示例1 ###
> 
> #### 输入： ####
> 
>     abcdef
> 
> #### 输出： ####
> 
>     abcdef
> 
> #### 说明： ####
> 
> abcdef已经是最小字符串，不需要交换
> 
> ### 示例2 ###
> 
> #### 输入： ####
> 
>     bcdefa
> 
> #### 输出： ####
> 
>     acdefb
> 
> #### 说明： ####
> 
> a和b进行位置交换，可以等到最小字符串

> ### 解题思路： ###
> 
> 这个跟冒泡算法差不多，就是相邻两个进行比较，进行两两交换，将较小的字符放在前面

> ### 代码（Python）： ###
> 
>     import sys
>     
>     for line in sys.stdin:
>         s = line.strip()
>         res = s
>         n = len(s)
>         for i in range(n):
>             for j in range(i+1, n):
>                 c = list(s)
>                 t = c[i]
>                 c[i] = c[j]
>                 c[j] = t
>                 s2 = "".join(c)
>                 if res > s2:
>                     res = s2
>         print(res)

> ### 代码（C++）： ###
> 
>     #include <iostream>
>     #include <string>
>     using namespace std;
>     
>     int main() {
>         string s;
>         while (getline(cin, s)) {
>             string res = s;
>             int n = s.length();
>             for (int i = 0; i < n; i++) {
>                 for (int j = i+1; j < n; j++) {
>                     string c = s;
>                     char t = c[i];
>                     c[i] = c[j];
>                     c[j] = t;
>                     string s2 = c;
>                     if (res > s2) {
>                         res = s2;
>                     }
>                 }
>             }
>             cout << res << endl;
>         }
>         return 0;
>     }

[Link 1]: https://blog.csdn.net/qq_34465338/article/details/135077521