顺义建设网站wordpress网站管理
交换字符 Problem Description
米小游拿到了一个仅由小写字母组成的字符串，她准备进行恰好一次操作：交换两个相邻字母，在操作结束后使得字符串的字典序尽可能大。
请你输出最终生成的字符串。input
一个仅由小写字母组成的字符串，长度不小于 2 ，不超过200000 。
ouput
操作后的字符串。
Sample Input
ba
Sample Output
ab
题目类型、难度、来源
- 类型：暴力
- 难度：简单
- 来源：米哈游春招算法岗-2023.03.19-第一题-交换字符
总体思路：
- 此题很简单，输入一个字符串，必须要交换一次，使得字符串的字典序尽可能大。
- ①首先从左到右遍历，如果遇到右边的字符比左边的字符大，马上交换，并break。
- ②如果第一种情况不存在，说明不能通过交换使字符串字典序变大，此时就要注意避免交换导致字典序减小。就要看字符串中是否有相邻的两个字符相同大小。如果存在，那么可以使用一次交换使字典序不变。
- ③如果上面两种情况都不存在，就要尽量让字典序减少得尽可能少。此时应该交换字符串最后的两个元素。
AC代码
#include <iostream>
#include <string>
using namespace std;
void swap(char &a, char &b){char t = a;a = b;b = t;
}
int main(){string s;cin >> s;int i, flag = 0;for (i = 0; i < s.size()-1; i++){if (s[i+1] > s[i]){swap(s[i], s[i+1]);break;}else if (s[i+1] == s[i]){flag = 1;}}if (i == s.size()-1){if (flag == 0){swap(s[s.size()-1], s[s.size()-2]);}}cout << s;return 0;
}
- 更多大厂真题可以看：2023实习、秋招互联网大厂技术岗算法真题-刷题（持续更新）