leetCode-412:Remove K Digits

问题描述

给定一个包含非负整数的字符串 numnum 中没有前置 0)和一个数字 k,要求在 num 中剔除 k 个字符,使得剩下的字符串代表的数字最小。题目链接:点我

样例输入输出

输入:num = “1432219”, k = 3

输出:”1219”

输入:num = “10200”, k = 1

输出:”200”

解释:删除第一个 1,剩下 0200,去除前置 0,返回 200

问题解法

用一个字符串来存储剔除后剩下的字符,遍历原有字符串,对当前字符进行判断,如果当前字符是 0,则判断存储的结果字符串中的第一个和最后一个字符串,哪个大则剔除哪个,如果当前字符比存储结果字符串的最后一位小,则剔除存储结果字符串的最后一位,直到当前字符比存储结果的最后一位大时为止,然后将当前字符加入到结果字符串中。当然,为了不多删字符,每次剔除字符时需要计数并与 k 进行比较,只有剔除的数量小于 k 才能剔除。最后,当遍历完字符串后,如果剔除的字符数量还是小于 k ,则从结果字符串中末尾剔除直到剔除数量等于 k 为止。然后再剔除结果字符串的前置 0,最后判断是否是空字符串,如果是则返回 “0”,否则返回当前的结果字符串。代码如下

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
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution
{
public String removeKdigits(String num, int k)
{
int count = 0;
StringBuilder result = new StringBuilder();
for (int i = 0; i < num.length(); i++)
{
char ch = num.charAt(i);
if (ch == '0')
{
while (result.length() > 0 && count < k)
{
// 比较结果字符串中第一个和最后一个的字符,哪个大则删除哪个
int index = 0;
if (result.charAt(0) < result.charAt(result.length() - 1))
{
index = result.length() - 1;
}

// 0 只会出现在最前面,此时剔除 0 不用计数
if (result.charAt(index) != '0')
{
count++;
}
result.deleteCharAt(index);
}
}
else
{
while (result.length() > 0 && result.charAt(result.length() - 1) > ch && count < k)
{
result.deleteCharAt(result.length() - 1);
count++;
}
}

result.append(ch);
}

// 到这里是,结果字符串中已经是递增的序列了,如果还有需要剔除的,只删除末尾部分即可
while (count < k)
{
result.deleteCharAt(result.length() - 1);
count++;
}

// 剔除前置 0
while (result.length() > 0 && result.charAt(0) == '0')
{
result.deleteCharAt(0);
}

if (result.length() == 0)
{
return "0";
}

return result.toString();
}
}