题目

设有一个正整数由n位数构成，删除其中的任意k位数后所得到的正整数最大

输入格式

输入要求：输入的第1行为该正整数，第2行为需要删除的位数k

输出格式

输出要求：输出删除k位数之后的最大的正整数。

输入样例

196857 2

输出样例

9857

解题思路

思路一 [ 贪心 ]

  1.      1. 每次从高位向低位数比较 [ **从左向右比较** ]
  2.         - 若**高位数字小**，则删除高位数字
  3.         - 若**高位数字大**，则继续向后比较
  4.      2. 从高位向低位依次比较结束，未找到高位小于低位的数字，则**删除末尾数字**
  5.         - **解释：**比较序列**下标**是从 **0 **开始到 **num.size() - 2**  结束

🍖实例说明
2319274 从高位向低位数比较

K=1 时，2<3 ，删除2，得到 319274**

K=2 时，2<3 ，删除2，得到** 319274**
3>1 ，略过
1<9， 删除1，得到 39274

K=3 时， 2<3 ，删除2，得到** 319274**
3>1 ，略过
1<9 ，删除1，得到 **39274**
3<9 ，删除3，得到** 9274**
**

思路二 [ 动态规划 ]

分析：

  1.      1. 假设** str** 为长度为** n **的数字字符串
  2.      1. **S[i][j] **表示删除 **str[0...i-1] **中** j **个数字后的**最大字符数字**
  3.      1. 如果删除第** i **个数
  4.         - 则 **S[i][j] **等于删除前 **i-1 **个字符中的 **j-1 **位的最优解
  5.         - 即 **S[i][j]=S[i-1][j-1]**
  6.      4. 如果不删除第 **i **个数
  7.         - 则** S[i][j]** 等于删除前** i-1 **个字符中** j **位的最优解+str[i]
  8.         - 即 **S[i][j]=S[i-1][j]+str[i-1]**
  9.      5. 即 **S[i][j]=max(S[i-1][j-1],S[i-1][j]+str[i-1])**
  10.      5. 初始状态为当** j=0** 时，不删除任何位的数字，即 **S[i][j]=str[0...i-1]**

状态转移方程如下

删除K位后使得数字最大 - 图1

时间复杂度：O( n×k )
空间复杂度：O( n×k )


优化：

  1.      1. 上述的转移方程** S[i][j]=max(S[i-1][j-1],S[i-1][j]+str[i-1])**
  2.      1. 可看出在**每次 i 循环**，**只与 i-1 相关**，因此只需要通过一个变量 **last **保存上一次的结果
  3.      1. 故状态转移方程可以简化为** S[j]=max(last,S[j]+str[i-1]）**

时间复杂度：O( n×k )
空间复杂度：O( k )

解题代码

贪心代码

  1. /***
  2. *   参数解释：
  3. *         i变量 : for循环基础变量
  4. *         k变量 : 存储要删除的位数个数
  5. *       num数组 : 用于存放正整数数字
  6. ****/
  7. #include<string>
  8. using namespace std;
  9. void Delete(string &num,int k) {
  10.     if (k > num.size())//排除异常输入
  11.         return;
  12.     while (k--) {
  13.         int i ;
  14.         for (i = 0; i < num.size() - 1; i++) {  //依次从左向右检查
  15.             if (num[i] < num[i + 1]) {            //高位数字小于低位数字
  16.                 num.erase(num.begin()+i);        //删除 i 下标，即高位数字
  17.                 break;
  18.             }
  19.         }
  20.         if(i== num.size() - 1)        //从左向右检查，高位数字均小于低位数字
  21.             num.erase(num.end()-1); //删除未位数字
  22.     }
  23.     if (!num.size())        //数组全删光,置零
  24.         num.push_back('0'); //🚩注意: num[0]='0' 赋值错误,原因不详
  25. }
  26. int main()
  27. {
  28.     string num;
  29.     int k;
  30.     cin >> num >> k;
  31.     Delete(num, k);
  32.     cout << num << endl;
  33.     system("pause");
  34.     return 0;
  35. }

动态规划代码

  1. #include<string>
  2. using namespace std;
  3. // dynamic programming
  4. // time complexity: O(n*k)
  5. // space complexity: O(n*k)
  6. string deleteKBits_2(string str,int k){
  7.     int tlen=str.length();
  8.     vector<vector<string> > nums(tlen+1,vector<string>(k+1));
  9.     string s1,s2;
  10.     for(int i=1;i<=tlen;i++){
  11.         for(int j=0;j<i && j<=k;j++){
  12.             if(j==0){
  13.                 nums[i][j]=str.substr(0,i);
  14.             }
  15.             else{
  16.                 s1=nums[i-1][j-1];
  17.                 s2=nums[i-1][j]+str[i-1];
  18.                 if(s1.compare(s2)<=0)
  19.                     nums[i][j]=s2;
  20.                 else
  21.                     nums[i][j]=s1;
  22.             }
  23.         }
  24.     }
  25.     return nums[tlen][k];
  26. }
  28. // dynamic programming
  29. // time complexity: O(n*k)
  30. // space complexity: O(k)
  31. string deleteKBits_3(string str,int k){
  32.     int tlen=str.length();
  33.     vector<string> nums(k+1);
  34.     string s1,s2,last;
  35.     for(int i=1;i<=tlen;i++){
  36.         for(int j=0;j<i && j<=k;j++){
  37.             if(j==0){
  38.                 last=nums[j];
  39.                 nums[j]=str.substr(0,i);
  40.             }
  41.             else{
  42.                 // s1=last
  43.                 s1=nums[j-1];
  44.                 s2=nums[j]+str[i-1];
  45.                 if(s1.compare(s2)<=0){
  46.                     last=nums[j];
  47.                     nums[j]=s2;
  48.                 }
  49.                 else{
  50.                     last=nums[j];
  51.                     nums[j]=s1;
  52.                 }
  53.             }
  54.         }
  55.     }
  56.     return nums[k];
  57. }
  59. // dynamic programming
  60. // time complexity: O(n*k)
  61. // space complexity: O(k)
  62. string deleteKBits_4(string str,int k){
  63.     int tlen=str.length();
  64.     vector<string> nums(k+1);
  65.     string tmp,s2,last;
  66.     for(int i=1;i<=tlen;i++){
  67.         for(int j=0;j<i && j<=k;j++){
  68.             if(j==0){
  69.                 last=nums[j];
  70.                 nums[j]=str.substr(0,i);
  71.             }
  72.             else{
  73.                 // s1=last
  74.                 // s1=nums[j-1];
  75.                 s2=nums[j]+str[i-1];
  76.                 if(last.compare(s2)<=0){
  77.                     last=nums[j];
  78.                     nums[j]=s2;
  79.                 }
  80.                 else{
  81.                     tmp=nums[j];
  82.                     nums[j]=last;
  83.                     last=tmp;
  84.                 }
  85.             }
  86.         }
  87.     }
  88.     return nums[k];
  89. }
  90. int main()
  91. {
  92.     string str="2319274";
  93.     int k=3;
  94.     cout <<deleteKBits_2(str,k)<< endl;
  95.     cout <<deleteKBits_3(str,k)<< endl;
  96.     cout <<deleteKBits_4(str,k)<< endl;
  97.     system("pause");
  98.     return 0;
  99. }