402. Remove K Digits

sf190404 發布于2019-08-14 17:26 / 2239人閱讀

摘要：題目鏈接根據題目的描述，移掉個數字然后得到最小值，肯定是。后面的和需要移掉也是同理。用個來保存之前遞增的數字。注意這個例子，去掉之后，最高位是，也得去掉。

402. Remove K Digits

題目鏈接：https://leetcode.com/problems...

根據題目的描述，移掉k個數字然后得到最小值，肯定是greedy。那么greedy的feature是什么呢？
看例子，首先是1432219，k = 3，不去掉1的原因是后面接的是4，當前這一步，看到下一個數比自己大的時候移掉是不劃算的，因為移掉這個數之后最高位變成4，是不如保留1小的。所以可以看出規律實際上是從msb開始只要發現比之前有比當前位大的數字，那肯定要移掉之前的數字，這樣當前最高位的數字就變小了。后面的3和2需要移掉也是同理。用個Stack來保存之前遞增的數字。
再看1223，k = 1，從左往右掃一遍發現沒有出現nums[i-1] > nums[i]的情況，所以第一次掃的時候刪了0個，這時候就從最大值開始移。
注意10200這個例子，去掉1之后，最高位是0，也得去掉。

public class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder sb = new StringBuilder();
        int n = num.length();
        char[] stack = new char[n];
        int count = 0;
        // remove the digit that larger than digit after it
        for(int i = 0; i < n; i++) {
            while(count != 0 && k > 0 && num.charAt(i) < stack[count-1]) {
                count--;
                k--;
            }
            stack[count++] = num.charAt(i);
        }
        // remove 0 at the beginning
        int start = 0;
        while(start < count && stack[start] == "0") start++;
        
        // remove from lsb
        return start >= count - k ? "0" : new String(stack, start, count - start - k);
    }
}

云服務器 GPU云服務器 v402 Digits remove remove()方法

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66638.html

leetcode402. Remove K Digits

摘要：當我們用盡了所有刪除時，就保留后面所有的數字，不再進行任何比較。因為我們已經盡可能獲得了最小的最高位，因此無論后面的數字如何取值，其最高位上的數字一定是可以獲得的最小的這個數字。題目要求 Given a non-negative integer num represented as a string, remove k digits from the number so that t...

paraller 2019-08-16 15:38 評論0 收藏0
316. Remove Duplicate Letters and 402. Remove K Di

摘要：每個字母只留一個，而且保證字典序最小。從前往后掃描，還要往前看一個檢出是否刪除的，要用解。需要一個數據結構記錄是否使用這個字母，可以用。結構也可以用數組加頂點指針模擬。 316 Remove Duplicate Given a string which contains only lowercase letters, remove duplicate letters so that e...

novo 2019-08-14 18:01 評論0 收藏0
[LintCode] Delete Digits [Greedy]

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

張漢慶 2019-08-14 15:21 評論0 收藏0
前端每日實戰：164# 視頻演示如何用原生 JS 創作一個數獨訓練小游戲（內含 4 個視頻）

摘要：第部分第部分第部分第部分源代碼下載每日前端實戰系列的全部源代碼請從下載代碼解讀解數獨的一項基本功是能迅速判斷一行一列或一個九宮格中缺少哪幾個數字，本項目就是一個訓練判斷九宮格中缺少哪個數字的小游戲。 showImg(https://segmentfault.com/img/bVbkNGa?w=400&h=300); 效果預覽按下右側的點擊預覽按鈕可以在當前頁面預覽，點擊鏈接可以全屏預...

Heier 2019-08-23 13:57 評論0 收藏0
前端每日實戰：164# 視頻演示如何用原生 JS 創作一個數獨訓練小游戲（內含 4 個視頻）

摘要：第部分第部分第部分第部分源代碼下載每日前端實戰系列的全部源代碼請從下載代碼解讀解數獨的一項基本功是能迅速判斷一行一列或一個九宮格中缺少哪幾個數字，本項目就是一個訓練判斷九宮格中缺少哪個數字的小游戲。 showImg(https://segmentfault.com/img/bVbkNGa?w=400&h=300); 效果預覽按下右側的點擊預覽按鈕可以在當前頁面預覽，點擊鏈接可以全屏預...

OBKoro1 2019-08-30 15:54 評論0 收藏0