316. Remove Duplicate Letters

chunquedong 發布于2019-08-19 10:45 / 2389人閱讀

摘要：以及枚舉的做法，因為這題只有個字母，枚舉的復雜度是，參考博客還有先把排序，然后從小到大取字母的寫法，參考

316. Remove Duplicate Letters

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

用一個stack來做，stack里面的字母按增序來排，出現top>cur的時候要把top給pop出來，注意一點是如果后面沒有top的話，就不能pop出來，所以先要用個hashmap來保存每個字母出現的次數，次數到0說明后面沒有這個字母了，還需要一個visited數組來保存已經在stack里面的字母

pop: while top > cur && map[top] > 0

push: when !visited[cur]

loop invariant是(0, i)是到i為止最小的字母order結果。

public class Solution {
    public String removeDuplicateLetters(String s) {
        // count the number of each character
        int[] map = new int[26];
        for(char c : s.toCharArray()) {
            map[c - "a"]++;
        }
        // stack to store the smallest lexi order
        char[] stack = new char[s.length()];
        // visited to record already added letter
        boolean[] visited = new boolean[26];
        int i = 0;
        for(char c : s.toCharArray()) {
            map[c - "a"]--;
            if(visited[c - "a"]) continue;
            // pop top character if it is > c && there are remains in the right
            while(i > 0 && stack[i-1] > c && map[stack[i-1] - "a"] > 0) {
                visited[stack[i-1] - "a"] = false;
                i--;
            }
            stack[i++] = c;
            visited[c-"a"] = true;
        }
        
        return new String(stack, 0, i);
    }
}

以及枚舉的做法，因為這題只有26個字母，枚舉的復雜度是O(26*N)，參考博客：
http://bookshadow.com/weblog/...

還有先把string排序，然后從小到大取字母的寫法，參考discussion：
https://discuss.leetcode.com/...

云服務器 GPU云服務器 Letters DUPLICATE remove remove()方法

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/76400.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 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
[LeetCode]Remove Duplicate Letters

摘要：首先要求就是得保證在原來的字符串中存在當前字符的順序，即要保證每次的字符的次數大于。讀字符的過程中，把字符存到里，當發現之前存的字符中比當前字符大而且頻率還大于就可以把那個字符出去。基本思想就是在一定的限制條件下出比當前選擇差的元素。 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
數據結構-鏈表

摘要：猶太士兵決定寧可自殺也不做俘虜，于是商量出了一個自殺方案。他們圍成一個圈，從一個人開始，數到第三個人時將第三個人殺死，然后再數，直到殺光所有人。使用循環鏈表解決該問題。首先我們看到他們圍成一個圈判斷應該使用循環鏈表來處理改問題完整代碼前移本章將討論另一種列表: 鏈表 . 解釋為什么有時鏈表優于數組, 還會實現一個基于對象的鏈表. 數組的缺點數組不總是組織數據的最佳數據結構, 原因如...

stormzhang 2019-08-26 12:20 評論0 收藏0