Leetcode402——Remove K Digits

Tyan

发布于 2019-05-25 23:14:46

3290

发布于 2019-05-25 23:14:46

文章被收录于专栏：SnailTyanSnailTyan

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017年04月09日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度