Leetcode402——Remove K Digits

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

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. 求解

每移除一个字符，找出移除一个字符串后得到的字符串中最小的那个，作为下一次移除字符的输入，这样每次移除字符后得到子串都是最小子串。这里必须要明确每次移除字符的最优解必定是下一次移除字符最优解的输入，即f(n)的最优解必定是求解f(n-1)的最优解的一部分。问题的最优解解中包含了子问题的最优解。

方法一：

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();
    }
}