华为机试题:求最小数(移掉K位数字)

题目描述:

  • 给你一个以字符串表示的非负整数 num 和一个整数 k ,移除这个数中的 k 位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例:

输入:num = “1432219”, k = 3
输出:”1219”
解释:移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

题解:

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
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String s = sc.nextLine();
int k = sc.nextInt();
System.out.println(removeKnums(s, k));
}
}

public static String removeKnums(String num, int k) {
// write code here
Deque<Character> deque = new LinkedList<>();
int len = num.length();
//单调栈判断
for (int i = 0; i < len; ++i) {
char digit = num.charAt(i);
// 判断当前是否大于栈顶
while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
deque.pollLast();
k--;
}
//加入最后一个位置
deque.offerLast(digit);
}

for (int i = 0; i < k; ++i) {
deque.pollLast();
}
//返回最终结果
StringBuilder res = new StringBuilder();
boolean leadingZero = true;
while (!deque.isEmpty()) {
char digit = deque.pollFirst();
//是否遇到0
if (leadingZero && digit == '0') {
continue;
}
leadingZero = false;
res.append(digit);
}
return res.length() == 0 ? "0" : res.toString();
}
}
你的赞赏将是我创作输出的最大动力
0%