成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

316. Remove Duplicate Letters and 402. Remove K Di

novo / 3218人閱讀

摘要：每個(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 every letter appear once and 
only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"
每個(gè)字母只留一個(gè)，而且保證字典序最小。
從前往后掃描，還要往前看一個(gè)檢出是否刪除的，要用stack解。stack里記錄的就是待用的字母。
首先要有一個(gè)counter記錄下每個(gè)字母的總個(gè)數(shù)，stack刪除字母的時(shí)候如果后面還有余量，則可以放心刪除。
還有個(gè)關(guān)鍵詞: once and only once。需要一個(gè)數(shù)據(jù)結(jié)構(gòu)記錄是否使用這個(gè)字母，可以用boolean。

public class Solution {
    public String removeDuplicateLetters(String s) {
        ArrayDeque stk = new ArrayDeque();
        int[] counter = new int[26];
        boolean[] visited = new boolean[26];
        char[] chs = s.toCharArray();
        
        for(char c: chs){
            counter[c - "a"]++;
        }
        
        
        for(char c : chs){
            counter[c - "a"]--;
            if(visited[c - "a"]) continue;
            
            while(!stk.isEmpty() && stk.peekLast() > c && counter[stk.peekLast() -"a"] > 0){
                visited[stk.peekLast() - "a"] = false;
                stk.pollLast();
            }
            stk.addLast(c);
            visited[c-"a"] = true;
        }
        
        StringBuilder sb = new StringBuilder();
        for(char c: stk){
            sb.append(c);
        }
        
        return sb.toString();
    }
}
402 Remove K Digits
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

stk結(jié)構(gòu)也可以用數(shù)組加頂點(diǎn)指針模擬。用法如下。

public class Solution {
    public String removeKdigits(String num, int k) {
        int digit = num.length() - k;
        char[] stk = new char[num.length()];
        int top = 0;
        for(char c: num.toCharArray()){
            while(top > 0 && stk[top-1] > c && k > 0){
                k--;
                top--;
            }
            stk[top++] = c;
        }
        
        int idx = 0;
        while(idx < digit && stk[idx] == "0") idx++;
        
        return idx == digit ? "0" : new String(stk, idx, digit-idx);
    }
}

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

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

相關(guān)文章

  • LeetCode[316] Remove Duplicate Letters

    摘要：復(fù)雜度思路用一個(gè)每次考慮當(dāng)前的字符大小和的頂端字符的大小，如果當(dāng)前字符比較小的話，則可以出頂端的字符，將當(dāng)前的字符放進(jìn)中。需要維持了一個(gè)判斷當(dāng)前字符在剩余字符串中的出現(xiàn)次數(shù)，考慮能否將這個(gè)字符從棧中彈出。 LeetCode[316] Remove Duplicate Letters Given a string which contains only lowercase letter...

    tomorrowwu 評(píng)論0 收藏0

  • 316. Remove Duplicate Letters

    摘要：以及枚舉的做法，因?yàn)檫@題只有個(gè)字母，枚舉的復(fù)雜度是，參考博客還有先把排序，然后從小到大取字母的寫(xiě)法，參考 316. Remove Duplicate Letters 題目鏈接：https://leetcode.com/problems... 用一個(gè)stack來(lái)做，stack里面的字母按增序來(lái)排，出現(xiàn)top>cur的時(shí)候要把top給pop出來(lái)，注意一點(diǎn)是如果后面沒(méi)有top的話，就不能po...

    chunquedong 評(píng)論0 收藏0

  • [LeetCode]Remove Duplicate Letters

    摘要：首先要求就是得保證在原來(lái)的字符串中存在當(dāng)前字符的順序，即要保證每次的字符的次數(shù)大于。讀字符的過(guò)程中，把字符存到里，當(dāng)發(fā)現(xiàn)之前存的字符中比當(dāng)前字符大而且頻率還大于就可以把那個(gè)字符出去?；舅枷刖褪窃谝欢ǖ南拗茥l件下出比當(dāng)前選擇差的元素。 Remove Duplicate Letters Given a string which contains only lowercase lette...

    gaosboy 評(píng)論0 收藏0

  • [LintCode/LeetCode] Remove Duplicate Letters

    Problem Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical...

    wanghui 評(píng)論0 收藏0

  • 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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<