[LintCode] Delete Digits [Greedy]

107 查看

Problem

Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.

Find the smallest integer after remove k digits.

N <= 240 and k <= N,

Example

Given an integer A = "178542", k = 4

return a string "12"

Note

题意为取String A删去k个字符后最小的值,仍以String返回。
使用Greedy的解法如下:
首先通过用字符与'0'相减的结果int cur进行数值大小的比较。然后遍历整个字符串,将较小的元素替换栈内较大元素并放在栈底,形成一个从底部到顶端逐渐增大的堆栈。例如0812743456(不考虑删除元素个数k),堆栈的排列从下到上就变成123456了。又例如087123654,k = 2,那么放入堆栈后就变成0123654
那么,现在就有两种情况:删掉的元素数目小于或等于k。
如果在for循环中正好删除了k个元素,这k个元素一定是从原字符串A的高位(栈底)开始删除的。所以无论删除k个元素之后的元素放入顺序如何,此时栈内元素从底到顶的排列一定是满足条件的最小值。
如果在for循环删除的元素少于k个,一定是这样的情况:081234567, k = 3, 在for循环结束的时候只删除了元素8,因为剩下的元素是一个完全上升序列01234567。这种情况下,就要从堆栈顶部删除剩下的两个元素6和7.
然后,将栈内的元素放入StringBuilder,并将StringBuilder顶部的'0'全部去掉,然后以.toString()返回String

Solution

public class Solution {
    public String DeleteDigits(String A, int k) {
        if (A == null || A.length() < k) return null;
        Stack<Integer> stack = new Stack<Integer>();
        int deleted = 0;
        for (int i = 0; i < A.length(); i++) {
            int cur = A.charAt(i) - '0';
            while (!stack.isEmpty() && stack.peek() > cur && deleted < k) {
                stack.pop();
                deleted++;
            }
            stack.push(cur);
        }
        while (deleted++ < k) stack.pop();
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.insert(0, stack.pop());
        while (sb.charAt(0) == '0') sb.deleteCharAt(0);
        return sb.toString();
    }
}

2019 - 知识虫 - 我的知识库 重庆启连科技有限公司 渝ICP备16002641号-2

渝公网安备 50010702501581号