leetcode解题: Remove K Digits (402)

发表于 | 分类于

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:

1
2
3
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:

1
2
3
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:

1
2
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.

解法1： 贪心算法

这题用贪心的算法, 观察可以发现如果每次remove的时候满足if (num[i] > num[i + 1]), 那么得到的数一定是最小的.
这里可以用一个string来存储当前扫描的结果,如果发现现在的字符比string的最后一个字符小,那么就把string的最后一个字符去掉. (目的是维护一个递增的数列)
最后呢,我们只需要去前num.size() - k个数即可.要注意的是因为每次去除数字的时候k数会变,所以一开始需要用一个变量存储初值.
最后返回的时候要去掉leading zero.
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string removeKdigits(string num, int k) {
        if (k >= num.size()) {
            return "0";
        }
        string res = "";
        int n = k;
        
        for (auto ch : num) {
            while (!res.empty() && res.back() > ch && k > 0) {
                k--;
                res.pop_back();
            }
            res.push_back(ch);
        }
        
        int start = 0;
        while (res[start] == '0') {start++;}
        
        // Take first num.size() - k elements
        
        if (start >= res.size()) {
            return "0";
        } else {
            return res.substr(start, min(start + num.size() - n, res.size()));
        }
        
    }
};

Java

1