题目
结果
代码
递归
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
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public String removeKdigits(String num, int k) {
for (int i = 0; i < k; i++) {
num = removeOneDigit(num).toString();
}
if (allZero(num)) {
return "0";
} else if (num.startsWith("0")) {
return num.substring(indexOfZero(num));
}
return num;
}
private StringBuilder removeOneDigit(String num) {
if (num.length() < 2) {
return new StringBuilder();
}
if (num.charAt(0) > num.charAt(1)) {
return new StringBuilder(num.substring(1));
} else {
StringBuilder sb = new StringBuilder();
return sb.append(num.charAt(0)).append(removeOneDigit(num.substring(1)));
}
}
private boolean allZero(String num) {
for (char ch : num.toCharArray()) {
if (ch != '0') {
return false;
}
}
return true;
}
private int indexOfZero(String num) {
for (int i = 0; i < num.length(); i++) {
if (num.charAt(i) != '0') {
return i;
}
}
return -1;
}
}
|
我觉得这种递归的代码写起来很好看，可是超时了，主要原因是遍历num高达k遍，其实遍历一遍就够了。
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
public String removeKdigits(String num, int k) {
Deque<Character> stack = new LinkedList<>();
for (int i = 0; i < num.length(); i++) {
while (!stack.isEmpty() && k > 0 && stack.peek() > num.charAt(i)) {
stack.pop();
k--;
}
stack.push(num.charAt(i));
}
for (int i = 0; i < k; i++) {
stack.pop();
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pollLast());
}
String ans = sb.toString();
if (allZero(ans)) {
return "0";
} else if (ans.startsWith("0")) {
return ans.substring(indexOfZero(ans));
}
return ans;
}
private boolean allZero(String num) {
for (char ch : num.toCharArray()) {
if (ch != '0') {
return false;
}
}
return true;
}
private int indexOfZero(String num) {
for (int i = 0; i < num.length(); i++) {
if (num.charAt(i) != '0') {
return i;
}
}
return -1;
}
}
|
复杂度
时间复杂度：O（N），遍历一遍
空间复杂度：O（N），stack