力扣20题、1047（括号合法性，删除字符串中的所有相邻重复项）

20、括号合法性

基本思想：

栈（用deque实现的栈）

具体实现：

在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单

情况1：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

情况2：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

情况3：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

代码：

class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++){
            ch = s.charAt(i);

            //碰到左括号，就把相应的右括号入栈
            if (ch == '('){  
                deque.push(')');
            }else if (ch == '{') {
                deque.push('}');
            }else if (ch == '[') {
                deque.push(']');
            }else if (deque.isEmpty() || deque.peek() != ch) {//peek,返回栈顶
                return false;
            }else {//如果是右括号判断是否和栈顶元素匹配
                deque.pop();
            }
        }
        return deque.isEmpty();
    }
}

1047、删除字符串中的所有相邻重复项

基本思想：

栈，字符串，双指针

具体实现：

ArrayDeque会比LinkedList在除了删除元素这一点外会快一点

代码：

class Solution {
    public String removeDuplicates(String s) {
        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) {
        StringBuffer res = new StringBuffer();
        int top = -1;
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if ( top >= 0 && res.charAt(top) == c){
                res.deleteCharAt(top);
                top--;
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }
}

双指针

class Solution {
    public String removeDuplicates(String s) {
        char[] ch = s.toCharArray();
        int fast = 0;
        int slow = 0;
        while (fast < s.length()){
            ch[slow] = ch[fast];//直接用fast指针覆盖slow指针的值
            if (slow > 0 && ch[slow] == ch[slow - 1]){
                // 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
                slow--;
            } else {
                slow++;
            }
            fast++;
        }
        return new String(ch,0,slow);
    }
}