消除重复数字

[华为编程题]消除重复数字

• 时间限制：3s
• 空间限制：32768K
• 题目描述：
  给定一个正整数，给出消除重复数字以后最大的整数
• 输入描述：
  正整数，注意考虑长整数
  输出描述：
  消除重复数字以后的最大整数
• 示例
  输入：423234
  输出：432

分析

• 注意考虑长整数，空间限制为32768K，提示我们只能利用数字字符串来实现
• 可以视为双指针问题：
  指针i，j 从数字字符串的首地址开始遍历，j作为查重的指针（在 [0,i] 之间的字符子串）
  如果出现重复数字，即str[j] = str[i]，那么根据题目要求，是消除重复数字以后的最大整数，就要做一个比较，判断是移除i位置的数字还是j位置的数字，如果str[j+1] > str[j]，应该移除j位置的重复数字，否则移除i位置的重复数字以保证局部最大整数（这里当然包括使用什么样的结构体，在移除数据时可以迅速恢复）

举个图例

伪代码：

for (int i = 0; i<len; i++)
   for (int j = 0; j < i; j++)
   {
       if (a[i] == a[j])
       {
           if (a[j+1] > a[j])
           {
               移除 j 位置数字;
               i --;        // i 回退
               break;
           }
           else
           {
               移除 i 位置数字;
               i --;        // i 回退
               break;
           }
       }
   }

以上，可以采用双向链表的结构存储数字

实现完整Code：

#include <iostream>
#include <string>
using name space std;

int main()
{
    string s;
    while(cin>>s)
    {
        1. 数字字符串合法性检查
        
        2. 
        string res;
        res = s[0];
        for (int i = 1; i < s.size(); i++)
        {
            if (res.find(s[i]) == string :: npos)
            {
                res + = s[i];
            }
            else
            {
                int t = res.find(s[i]);
                if ((t+1) < res.size())
                {
                    if (res[t] < res[t+1])
                    {
                        res.erase(t, 1);          // 移走并且调整
                        res + = s[i];
                    }
                }
            }
        }
        cout<< res <<endl;
    }
    return 0;
}