# Leetcode402——Remove K Digits

## 1. 问题描述

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:

```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.```

## 2. 求解

```public class Solution {
public String removeKdigits(String num, int k) {
String min = remove(num, k);
if(min.equals("")) {
return "0";
}
while(min.charAt(0) == '0') {
if(min.length() == 1) {
break;
}
min = min.substring(1, min.length());
}
return min;
}

public String remove(String num, int k) {
if(k == 0) {
return num;
}
int n = num.length();
String minString = num.substring(0, num.length() - 1);
for(int i = 0; i < n; i++) {
String temp = num.substring(0, i) + num.substring(i + 1, n);
if(temp.compareTo(minString) < 0) {
minString = temp;
}
}
return remove(minString, k - 1);
}
}```

Leetcode超时。

```public class Solution {
public String removeKdigits(String num, int k) {
//用StringBuilder是因为StringBuilder有删除指定字符的功能
StringBuilder min = new StringBuilder(num);
for(int m = 0; m < k; m++) {
int index = 0;
int n = min.length();
for(int i = 0; i < n; i++) {

if((i == n -1) || min.charAt(i) > min.charAt(i + 1)) {
index = i;
break;
}
}
min = min.deleteCharAt(index);
}
//判断字符串为空的情况
if(min.length() == 0) {
return "0";
}
//去掉字符串前面的“0”
while(min.charAt(0) == '0') {
if(min.length() == 1) {
break;
}
min = min.deleteCharAt(0);
}
return min.toString();
}
}```

440 篇文章56 人订阅

0 条评论