【LeetCode】1047. 删除字符串中的所有相邻重复项(StringBuffer简单用法)

??今日学习的文章链接和视频链接

leetcode题目地址：1047. 删除字符串中的所有相邻重复项

?代码随想录题解地址：代码随想录

题目简介

给出由小写字母组成的字符串?S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

看到题目的第一想法(可以贴代码）

1. 利用Stack栈类，push每个元素之前先判定它和前一个元素（此时栈里的peek元素）是否一致，若一致则一起删除，否在push入栈。

public String removeDuplicates(String s) {
    Stack<Character> q = new Stack<>();
    for (char i : s.toCharArray()){
        if (q.empty() || q.peek() != i){
            q.push(i);
        }else {
            q.pop();
        }
    }
    String res = "";
    for (Character i : q){
        res += i;
    }
    return res;
}

实现过程中遇到哪些困难

无，就是时间复杂度和空间复杂度较大。

看完代码随想录之后的想法

【解题思路】直接用一个字符串去模拟栈的行为，可以省略一个栈到字符串类型的转换步骤。

看完视频自己写的ACC：

public String removeDuplicates(String s) {
    String q = "";
    for (char i : s.toCharArray()){
        if (q.isEmpty()){
            q = i + q;
            continue;
        }
        if (q.charAt(q.length()-1) != i){
            q = q + i;
        }
        else{
            q = q.substring(0, q.length() - 1);
        }
    }
    return q;
}

标准答案

class Solution {
    public String removeDuplicates(String S) {
        //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
        //参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < S.length(); i++) {
            ch = S.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }
        String str = "";
        //剩余的元素即为不重复的元素
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;
    }
}

class Solution {
    public String removeDuplicates(String s) {
        // 将 res 当做栈
        // 也可以用 StringBuilder 来修改字符串，速度更快
        // StringBuilder res = new StringBuilder();
        StringBuffer res = new StringBuffer();
        // top为 res 的长度
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
            if (top >= 0 && res.charAt(top) == c) {
                res.deleteCharAt(top);
                top--;
            // 否则，将该字符 入栈，同时top++
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }
}

学习时长

略

---

今日收获

1.?StringBuffer

初始化：StringBuffer res = new StringBuffer();

常用方法：

????????res.charAt(top)

????????res.deleteCharAt(top);

????????res.append(c);

????????res.toString();