[LintCode] Delete Digits [Greedy]

張漢慶發布于2019-08-14 15:21 / 1892人閱讀

摘要：題意為取刪去個字符后最小的值，仍以返回。所以無論刪除個元素之后的元素放入順序如何，此時棧內元素從底到頂的排列一定是滿足條件的最小值。這種情況下，就要從堆棧頂部刪除剩下的兩個元素和然后，將棧內的元素放入，并將頂部的全部去掉，然后以返回。

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

云服務器 GPU云服務器 Greedy Digits LintCode LintCode134_LRU

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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