面试:字符串字典序最大的子序列

时间:2021-08-05 21:15:33

字符串字典序最大的子序列

  • 首先要知道什么是字典序,顾名思义,就是字典上的顺序。两个字符串进行对比时, 一位一位的按照a, b, c等字典序比较,如果相同就顺位比较下一位,比如ba比ab大,如果哪一位已经不一样 就已经比较出来结果了,如果是abc, abcd这样的情况,长度长的大。
  • 子序列和子串的区别;这俩其实不一样,子串是连续的,比如字符串abcdef,它的子串是abc,abcd等这些连续的。而子序列是不连续的。比如ace这样的。
  • 最简单的想法,先遍历一遍,找到最大的一个字符,以及他的位置,然后从这个位置开始往后遍历,找到后面最大的字符串以及位置,再继续下去,很明显,这样的算法复杂度比较高,N^2的复杂度。
  • 这里提供一个解决方案。用一个变量保存遍历到当前的最大值,从后往前遍历,如果字符比变量大,就更新最大值。记录字符。最后逆向输出字符就ok;附上代码
char str[100000   10];
char ans[100000   10];
int main()
{
    cin>>str;
    int maxnum = -1;
    int pos = -1;
    int lenstr = strlen(str);
    int ansflag = 0;
    for(int i = lenstr - 1; i >= 0; i--){
        if(str[i] - '0' >= maxnum){
            maxnum = str[i] - '0';
             
            ans[ansflag  ] = str[i];
        }
    }
    for(int i = strlen(ans) - 1;i>=0;i--)
    cout<<ans[i];
    cout<<endl;
}

题目是有提交的地址,字典序最大的子序列

祝你成功~