402. Remove K Digits

sf190404 發(fā)布于2019-08-14 17:26 / 2249人閱讀

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

402. Remove K Digits

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

根據(jù)題目的描述，移掉k個(gè)數(shù)字然后得到最小值，肯定是greedy。那么greedy的feature是什么呢？
看例子，首先是1432219，k = 3，不去掉1的原因是后面接的是4，當(dāng)前這一步，看到下一個(gè)數(shù)比自己大的時(shí)候移掉是不劃算的，因?yàn)橐频暨@個(gè)數(shù)之后最高位變成4，是不如保留1小的。所以可以看出規(guī)律實(shí)際上是從msb開(kāi)始只要發(fā)現(xiàn)比之前有比當(dāng)前位大的數(shù)字，那肯定要移掉之前的數(shù)字，這樣當(dāng)前最高位的數(shù)字就變小了。后面的3和2需要移掉也是同理。用個(gè)Stack來(lái)保存之前遞增的數(shù)字。
再看1223，k = 1，從左往右掃一遍發(fā)現(xiàn)沒(méi)有出現(xiàn)nums[i-1] > nums[i]的情況，所以第一次掃的時(shí)候刪了0個(gè)，這時(shí)候就從最大值開(kāi)始移。
注意10200這個(gè)例子，去掉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);
    }
}

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

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66638.html

相關(guān)文章

leetcode402. Remove K Digits

摘要：當(dāng)我們用盡了所有刪除時(shí)，就保留后面所有的數(shù)字，不再進(jìn)行任何比較。因?yàn)槲覀円呀?jīng)盡可能獲得了最小的最高位，因此無(wú)論后面的數(shù)字如何取值，其最高位上的數(shù)字一定是可以獲得的最小的這個(gè)數(shù)字。題目要求 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 評(píng)論0 收藏0
316. Remove Duplicate Letters and 402. Remove K Di

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

novo 2019-08-14 18:01 評(píng)論0 收藏0
[LintCode] Delete Digits [Greedy]

摘要：題意為取刪去個(gè)字符后最小的值，仍以返回。所以無(wú)論刪除個(gè)元素之后的元素放入順序如何，此時(shí)棧內(nèi)元素從底到頂?shù)呐帕幸欢ㄊ菨M(mǎn)足條件的最小值。這種情況下，就要從堆棧頂部刪除剩下的兩個(gè)元素和然后，將棧內(nèi)的元素放入，并將頂部的全部去掉，然后以返回。 Problem Given string A representative a positive integer which has N digits,...

張漢慶 2019-08-14 15:21 評(píng)論0 收藏0
前端每日實(shí)戰(zhàn)：164# 視頻演示如何用原生 JS 創(chuàng)作一個(gè)數(shù)獨(dú)訓(xùn)練小游戲（內(nèi)含 4 個(gè)視頻）

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

Heier 2019-08-23 13:57 評(píng)論0 收藏0
前端每日實(shí)戰(zhàn)：164# 視頻演示如何用原生 JS 創(chuàng)作一個(gè)數(shù)獨(dú)訓(xùn)練小游戲（內(nèi)含 4 個(gè)視頻）

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

OBKoro1 2019-08-30 15:54 評(píng)論0 收藏0