美文网首页
【栈】316 去除重复字符,字典序最小

【栈】316 去除重复字符,字典序最小

作者: Spring_java | 来源:发表于2020-12-30 14:27 被阅读0次

题目:
给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

案例

输入:s = "bcabc"
输出:"abc"

输入:s = "cbacdcbc"
输出:"acdb"

分析: 使用栈来解决
样例:cbacdcbc

  • 1:一开始c 入栈,没啥大问题
  • 2:b开始入栈,但是b排在c前面。所以c要被弹出,但是为了要保证每个字母都出现,且出现一次,所以需要知道后续的字符中是否还有没有c。 因此需要一个数组来统计每一个字符的个数。
    从后面可以看到c 还有,所以可以c 出栈。
  • 3:现在栈中是 b ,然后a 来了,开始入栈,同样的道理,从数组中知道还有b元素,所以b弹出,栈中是a
  • 4: c开始入栈,c小于a 当前元素 大于 栈顶元素 可以进入 a--c
  • 5:d 开始入栈,d小于c 当前元素 大于 栈顶元素 可以进入 a--c--d
  • 6: c开始入栈,但是此时c已经在栈中了。所以不需要再次走下去, 因此 需要一个数组来查看栈中是否还有元素。
  • 7:b开始入栈,可以判断b 不再栈中,但是b 大于d。但是d在后面的数组中没有数据了,所以d不需要弹出。b入栈了。同时在标记是否存在的数组中标记b在栈中。
  • 8:c 开始入栈,但是c 已经在栈中了,所以不走下去了。

需要:

1:一个数组,遍历整个字符串,看看每个字符有多少个
2:还需要一个数组,默认字符不再栈中,如果放入,就标记为在栈中。
3:使用栈,如果栈顶元素小于当前元素,那么当前元素放入栈中,并且标记当前元素在栈
如果栈顶元素大于当前元素,那么先判断栈顶元素还有吗?没有就弹出栈顶元素,并且标记当前弹出的栈顶元素不再栈中。
4:每次遍历数据的时候,都要先从保持了字符个数的数组删除一个,因为数据从从前到后再处理中,不会再回退。每次其实要判断的当前数组中剩下的字符有几个。

private static void removeDuplicateLetters(String data) {

        int length = data.length();
        int[] charArr = new int[256];
        boolean[] inStack=new boolean[256];
        Stack<Character> stack = new Stack<>();
        if (length == 0) {
            return;
        }
        for (int i = 0; i < length; i++) {
            charArr[data.charAt(i)]++;
        }
        for (int i = 0; i < length; i++) {
            char temp = data.charAt(i);
            charArr[temp]--;
            if(inStack[temp]){
                continue;
            }
            // 会陷入死循环
            while (!stack.empty() && stack.peek() > temp ) {
                // 遍历的时候,已经减少了一个,所以此时应该判断是0
                if(charArr[stack.peek()]==0){
                    break;
                }
                // 出栈了,就把它设置为不再栈中
                inStack[stack.pop()]=false;
            }
            stack.push(temp);
            // 入栈了,就设置为在栈中
            inStack[temp]=true;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.empty()) {
            sb.append(stack.pop());
        }
        System.out.println(sb.reverse().toString());
    }


相关文章

  • 【栈】316 去除重复字符,字典序最小

    题目:给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求...

  • 数据结构与算法学习 (08)字符串去重

    给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要...

  • 数据结构与算法-去除重复字母

    给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要...

  • 去除重复字符串

    给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要...

  • 算法—去除重复字母

    给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要...

  • 去除重复字母问题

    给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要...

  • leetcode-0316[更新打印宏及CMakeLists.t

    题目: 316. 去除重复字母 关键词: 单调栈,哈希表。 思路: 入栈条件:未入栈,且出现次数为1;统计出现次数...

  • 316. 去除重复字母

    题目 316. 去除重复字母 给定一个仅包含小写字母的字符串,去除字符串中重复的字母,使得每个字母只出现一次。需保...

  • ZOJ 1729 & ZOJ 2006(最小表示法模板题)

    输出每个字符串的最小字典序字串的下标!

  • leetcode 316题(困难):去除重复字母(C语言答案)

    题目 给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最...

网友评论

      本文标题:【栈】316 去除重复字符,字典序最小

      本文链接:https://www.haomeiwen.com/subject/vuhhoktx.html