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

2024-01-03 13:59:02

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

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();

文章来源:https://blog.csdn.net/Leonardo_t/article/details/135338092
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。