316. Remove Duplicate Letters and 402. Remove K Di

novo 发布于2019-08-14 18:01 / 3094人阅读

摘要：每个字母只留一个，而且保证字典序最小。从前往后扫描，还要往前看一个检出是否删除的，要用解。需要一个数据结构记录是否使用这个字母，可以用。结构也可以用数组加顶点指针模拟。

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

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

转载请注明本文地址：https://www.ucloud.cn/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

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