leetcode 402. Remove K Digits 贪心算法 + DFS深度优先遍历 + stack

矫情吗；* 2022-06-04 07:29 165阅读 0赞

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:  
The length of num is less than 10002 and will be ≥ k.  
The given num does not contain any leading zero.  
Example 1:

Input: num = “1432219”, k = 3  
Output: “1219”  
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.  
Example 2:

Input: num = “10200”, k = 1  
Output: “200”  
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.  
Example 3:

Input: num = “10”, k = 2  
Output: “0”  
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

题意很简单，就是去掉k个bit，然后求剩下的值的所有可能中的最小值，第一个想到的方法就是和上一道题的DFS深度优先遍历的做法，但是会超时，我隐隐约约感觉到可能使用stack等来解决，但是不会做，于是网上找了个做法，

这道题和[leetcode 321. Create Maximum Number 根据两个整数创造一个有k位的最大的数 + 贪心算法][leetcode 321. Create Maximum Number _k_ _]  
如思路有点类似，果n是num的长度，我们要去除k个，那么需要剩下n-k个，我们开始遍历给定数字num的每一位，对于当前遍历到的数字c，进行如下while循环，如果res不为空，且k大于0，且res的最后一位大于c，那么我们应该将res的最后一位移去，且k自减1。当跳出while循环后，我们将c加入res中，最后我们将res的大小重设为n-k。根据题目中的描述，可能会出现”0200”这样不符合要求的情况，所以我们用一个while循环来去掉前面的所有0，然后返回时判断是否为空，为空则返回“0”

建议和[leetcode 738. Monotone Increasing Digits 最大单调递增数字][leetcode 738. Monotone Increasing Digits] 一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <bitset>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        string removeKdigits(string num, int k)
        {
            if (k >= num.size())
                return "0";
            string res = "";
            int count = k;
            for (char c : num)
            {
                while (count > 0 && res.size() > 0 && res.back() > c)
                {
                    res.pop_back();
                    count--;
                }
                res.push_back(c);
            }
    
            res = res.substr(0,num.length()-k);
            while (res.empty()== false && res[0] == '0') 
                res.erase(res.begin());
            return res.length()<=0 ? "0" : res;
        }
    
    
        //和上一道题一样，就是一个DFS做法，但是会超时
        vector<int> all;
        string removeKdigitsByDFS(string num, int k) 
        {
            if (k >= num.length())
                return "0";
            vector<int> bit(num.length(), 0);
            vector<int> flag(num.length(), 0);
            for (int i = 0; i < bit.size(); i++)
                bit[i] = (int)(num[i] - '0');
    
            getAll(0,k, flag, bit);
    
            int minRes = numeric_limits<int>::max();
            for (int one : all)
                minRes = min(minRes, one);
            return to_string(minRes);
        }
    
        void getAll(int begin,int k,vector<int>& flag,vector<int>& bit)
        {
            if (k == 0)
            {
                int a = 0;
                for (int i = 0; i < bit.size(); i++)
                {
                    if (flag[i] == 0)
                        a = a * 10 + bit[i];
                }
                all.push_back(a);
            }
            else if (begin >= flag.size())
                return;
            else
            {
                getAll(begin + 1, k, flag, bit);
    
                flag[begin] = 1;
                getAll(begin + 1, k - 1, flag, bit);
                flag[begin] = 0;
            }
        }
    };

[leetcode 321. Create Maximum Number _k_ _]: http://blog.csdn.net/jackzhang_123/article/details/78150508
[leetcode 738. Monotone Increasing Digits]: http://blog.csdn.net/jackzhang_123/article/details/78894361