字符串变换最小字符串
字符串变换最小字符串
给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。
变换规则：交换字符串中任意两个不同位置的字符。
输入描述:
一串小写字母组成的字符串s
输出描述:
按照要求进行变换得到的最小字符串
示例1
输入
abcdef
输出
abcdef
说明
abcdef已经是最小字符串，不需要交换
示例2
输入
bcdefa
输出
acdefb
说明
a和b进行位置交换，可以得到最小字符串
备注:
- s是都是小写字符组成
- 1<=s.length<=1000
C++
#include <bits/stdc++.h>
using namespace std;
void quickSort(string &str,int left,int right);
int main() {
string str;
getline(cin,str);
quickSort(str,0,str.length() - 1);
system("pause");
return 0;
}
void quickSort(string &str,int left,int right)
{
if (left >= right)
{
return;
}
//选取中间节点为种子节点
int mid = left + (right - left) / 2;
int i = left;
int j = right;
char normal = str[mid];
while(i <= j)
{
if(str[i] < normal && i <= j)
{
i++;
continue;
}
if(str[j] > normal && i <= j)
{
j--;
continue;
}
char temp = str[i];
str[i] = str[j];
str[j] = temp;
i++;
j--;
}
quickSort(str, left, j);
quickSort(str, i, right);
}
投递字节跳动等公司9个岗位 >
