题目描述
给定一个包含 n 个小写字母的字符串 s。
现在,你可以将其中的最多一个字符移除(也可以不移除任何字符),你的目标是使这个字符串在字典序上尽可能小。
输出你可以得到的字典序上最小的字符串。
样例
输入样例:
2
3
aaa
5
abcda
输出样例:
aa
abca
算法1
(暴力枚举) $O(n)$
求的是最小字典序列字符串,首先题目要求最多删除一个(也可以不删除)–》一定是删除一个之后字符序列更小.
要求最小字典序列,则应该从前往后遍历,当a0>a1时,则删除a0之后,此时的字符串一定是结果。
如果a0=a1,则不必考虑a0,往后遍历,考虑a1是否需要删除即可。
从前往后遍历 前面的字符序列越小,则该字符串字典序列越小。
知识盲区: 把一个字符数组中的一个字符置为0 等价于’\0’结束字符
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5+5;
char a[N];
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d", &n);
scanf("%s", a);
for (int i = 0; i < n; i ++ ){
if(i==n-1)//所有字符都相等,则删除最后一个字符
{
a[i]=0;
printf("%s\n",a);
}
else if(a[i]>a[i+1]){
a[i]=0;
printf("%s%s\n",a,a+i+1);
break;
}
}
}
return 0;
}