[LeetCode]Remove Duplicate Letters

gaosboy 发布于2019-08-14 15:08 / 1029人阅读

摘要：首先要求就是得保证在原来的字符串中存在当前字符的顺序，即要保证每次的字符的次数大于。读字符的过程中，把字符存到里，当发现之前存的字符中比当前字符大而且频率还大于就可以把那个字符出去。基本思想就是在一定的限制条件下出比当前选择差的元素。

Remove Duplicate Letters

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.

Example:
Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

分析 方法一

这道题可以采用Greedy的思想，因为最后想要的结果是最小值，所以我们在满足要求的情况下把不断append最小的字符, 最后便可得到最小的字符串.

关键点就是要满足什么要求以及怎么样去满足。首先要求就是得保证在原来的字符串中存在当前字符append的顺序，即要保证每次append的字符的次数大于0。我们可以用一个数组记录每个字符出现的次数，用一个指针从左到右扫，过程中减小对应字符次数，找当前最小字符, 找的过程中终止条件是发现某个字符次数等于0，因为继续扫的话最终结果很有可能缺那个字符.

方法二

其实跟上个方法差不多，但是可以优化下，用stack的话，最多每个字符过两遍就可以了。读字符的过程中，把字符存到stack里，当发现stack之前存的字符中比当前字符大而且频率还大于0就可以把那个字符pop出去。类似这种题目都可以用stack解决。基本思想就是在一定的限制条件下pop出比当前选择差的元素。

复杂度 方法一

time: O(kn), space: O(k), k表示原字符串中unique字符的个数

方法二

time: O(n), space: O(k)

代码 方法一

public class Solution {
    public String removeDuplicateLetters(String s) {
        if (s == null ||s.length() == 0)
            return s;
            
        // 记录每个字符出现的次数    
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - "a"]++;
        }
        
        // 找出当前最小字符
        int pos = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos))
                pos = i;
            
            // 避免无字符可用
            if (--cnt[s.charAt(i) - "a"] == 0)
                break;
        }
        
        // 除去字符串中已经append的字符的所有重复值
        return s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
    }
}

方法二

public class Solution {
    public String removeDuplicateLetters(String s) {
        int[] freqs = new int[256];
        
        // 统计字符频率
        for (int i = 0; i < s.length(); i++) {
            freqs[s.charAt(i)]++;
        }

        boolean[] visited = new boolean[256]; // 用来标记存在stack里的字符
        Deque q = new ArrayDeque<>();    
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            freqs[c]--;
            if (visited[c]) continue;

            // pop出stack当中比当前字符大但后面还存在的的字符，
            while (!q.isEmpty() && q.peek() > c && freqs[q.peek()] > 0) {
                visited[q.pop()] = false;
            }
            q.push(c);
            visited[c] = true;
        }

        StringBuilder sb = new StringBuilder();
        for (char c : q) {
            sb.append(c);
        }

        return sb.reverse().toString();
    }
}

GPU云服务器云服务器 Letters DUPLICATE LeetCode remove

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65332.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
[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
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
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] 609. Find Duplicate File in System

Problem Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms o...

sf190404 2019-08-19 11:11 评论0 收藏0