402. Remove K Digits

  • 26.1%

https://leetcode.com/problems/remove-k-digits/description/

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

方法一:

https://discuss.leetcode.com/topic/59871/two-algorithms-with-detailed-explaination

Two algorithms with detailed explaination

The first algorithm is straight-forward. Let’s think about the simplest case: how to remove 1 digit from the number so that the new number is the smallest possible? Well, one can simply scan from left to right, and remove the first “peak” digit; the peak digit is larger than its right neighbor. One can repeat this procedure k times, and obtain the first algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string removeKdigits(string num, int k) {
while (k > 0) {
int n = num.size();
int i = 0;
while (i+1<n && num[i]<=num[i+1]) i++;
num.erase(i, 1);
k--;
}
// trim leading zeros
int s = 0;
while (s<(int)num.size()-1 && num[s]=='0') s++;
num.erase(0, s);

return num=="" ? "0" : num;
}

方法二:

我的代码实现:

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
31
32
class Solution {
public:
string removeKdigits(string num, int k) {
if(k>=num.size())
return "0";
if(k==0)
return num;
string res;
// k在后面发生了改变
int keep = num.size() - k;
for(auto c:num){
while(!res.empty() && res.back()>c && k>0){
res.pop_back();
k--;
}
res.push_back(c);
}
// 记得去掉后面长度过长的部分
if(res.size()>keep)
res.erase(keep);
// 牢记学习erase的用法
// sequence (1) 消除pos开始,长度为npos的一段
// string& erase (size_t pos = 0, size_t len = npos);
// character (2) 只消除p指向的位置
// iterator erase (const_iterator p);
// range (3) 消除first至last之间的一段
// iterator erase (const_iterator first, const_iterator last);
while(res.size()>1 && res[0]=='0')
res.erase(0, 1);
return res;
}
};

The above algorithm is a bit inefficient because it frequently remove a particular element from a string and has complexity O(k* n).

One can simulate the above procedure by using a stack, and obtain a O(n) algorithm. Note, when the result stack (i.e. res) pop a digit, it is equivalent as remove that “peak” digit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string removeKdigits(string num, int k) {
string res;
int keep = num.size() - k;
for (int i=0; i<num.size(); i++) {
while (res.size()>0 && res.back()>num[i] && k>0) {
res.pop_back();
k--;
}
res.push_back(num[i]);
}
// 此处要求keep必须<= res.size()
// 注意等于也可以
res.erase(keep, string::npos);

// trim leading zeros
int s = 0;
while (s<(int)res.size()-1 && res[s]=='0') s++;
res.erase(0, s);

return res=="" ? "0" : res;
}

https://discuss.leetcode.com/topic/59412/a-greedy-method-using-stack-o-n-time-and-o-n-space

A greedy method using stack, O(n) time and O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
public String removeKdigits(String num, int k) {
int digits = num.length() - k;
char[] stk = new char[num.length()];
int top = 0;
// k keeps track of how many characters we can remove
// if the previous character in stk is larger than the current one
// then removing it will get a smaller number
// but we can only do so when k is larger than 0
for (int i = 0; i < num.length(); ++i) {
char c = num.charAt(i);
while (top > 0 && stk[top-1] > c && k > 0) {
top -= 1;
k -= 1;
}
stk[top++] = c;
}
// find the index of first non-zero digit
int idx = 0;
while (idx < digits && stk[idx] == '0') idx++;
return idx == digits? "0": new String(stk, idx, digits - idx);
}
}

python

52ms, September 19, 2016

https://discuss.leetcode.com/topic/59380/short-python-one-o-n-and-one-regex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def removeKdigits(self, num, k):
"""
:type num: str
:type k: int
:rtype: str
"""
out = []
for d in num:
while k and out and out[-1] > d:
out.pop()
k -= 1
out.append(d)
return ''.join(out[:-k or None]).lstrip('0') or '0'

272ms, September 19, 2016

https://discuss.leetcode.com/topic/59380/short-python-one-o-n-and-one-regex

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def removeKdigits(self, num, k):
"""
:type num: str
:type k: int
:rtype: str
"""
sub = re.compile('1[0]|2[01]|3[0-2]|4[0-3]|5[0-4]|6[0-5]|7[0-6]|8[0-7]|9[0-8]|.$').sub
for _ in range(k):
num = sub(lambda m: m.group()[1:], num, 1)
return num.lstrip('0') or '0'

谢谢你,可爱的朋友。