316. Remove Duplicate Letters and 402. Remove K Di

novo 發布于2019-08-14 18:01 / 3212人閱讀

摘要：每個字母只留一個，而且保證字典序最小。從前往后掃描，還要往前看一個檢出是否刪除的，要用解。需要一個數據結構記錄是否使用這個字母，可以用。結構也可以用數組加頂點指針模擬。

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"

每個字母只留一個，而且保證字典序最小。
從前往后掃描，還要往前看一個檢出是否刪除的，要用stack解。stack里記錄的就是待用的字母。
首先要有一個counter記錄下每個字母的總個數，stack刪除字母的時候如果后面還有余量，則可以放心刪除。
還有個關鍵詞: once and only once。需要一個數據結構記錄是否使用這個字母，可以用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結構也可以用數組加頂點指針模擬。用法如下。

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

GPU云服務器云服務器 remove remove()方法 remove功能 Remove legacy webrtc

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

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

LeetCode[316] Remove Duplicate Letters

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

tomorrowwu 2019-08-14 15:04 評論0 收藏0
316. Remove Duplicate Letters

摘要：以及枚舉的做法，因為這題只有個字母，枚舉的復雜度是，參考博客還有先把排序，然后從小到大取字母的寫法，參考 316. Remove Duplicate Letters 題目鏈接：https://leetcode.com/problems... 用一個stack來做，stack里面的字母按增序來排，出現top>cur的時候要把top給pop出來，注意一點是如果后面沒有top的話，就不能po...

chunquedong 2019-08-19 10:45 評論0 收藏0
[LeetCode]Remove Duplicate Letters

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

gaosboy 2019-08-14 15:08 評論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 2019-08-15 18:01 評論0 收藏0
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