当前位置：首页 > article >正文

米哈游春招算法岗-2023.03.19-第一题-交换字符-简单题

article 2025/1/11 2:20:18

交换字符

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;
}