[LintCode] Delete Digits [Greedy]

张汉庆发布于2019-08-14 15:21 / 1784人阅读

摘要：题意为取删去个字符后最小的值，仍以返回。所以无论删除个元素之后的元素放入顺序如何，此时栈内元素从底到顶的排列一定是满足条件的最小值。这种情况下，就要从堆栈顶部删除剩下的两个元素和然后，将栈内的元素放入，并将顶部的全部去掉，然后以返回。

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 stack = new Stack();
        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();
    }
}

服务器托管私有云 Greedy Digits LintCode LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65677.html

[LintCode/LeetCode] Jump Game I & II

摘要：建立动规数组，表示从起点处到达该点的可能性。循环结束后，数组对所有点作为终点的可能性都进行了赋值。和的不同在于找到最少的步数。此时的一定是满足条件的最小的，所以一定是最优解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

rose 2019-08-14 15:27 评论0 收藏0
[LeetCode/LintCode] Plus One

Problem Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list. Example Given [1,2...

sunsmell 2019-08-14 15:17 评论0 收藏0
402. Remove K Digits

摘要：题目链接根据题目的描述，移掉个数字然后得到最小值，肯定是。后面的和需要移掉也是同理。用个来保存之前递增的数字。注意这个例子，去掉之后，最高位是，也得去掉。 402. Remove K Digits 题目链接：https://leetcode.com/problems... 根据题目的描述，移掉k个数字然后得到最小值，肯定是greedy。那么greedy的feature是什么呢？看例子，...

sf190404 2019-08-14 17:26 评论0 收藏0
[LintCode] Add Digits

Problem Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. Example Given num = 38.The process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one dig...

QiShare 2019-08-15 13:42 评论0 收藏0
[LeetCode/LintCode] Is Subsequence

Problem Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) ...

terasum 2019-08-19 11:05 评论0 收藏0