leetcode1047. 删除字符串中的所有相邻重复项

1.题目描述：

给出由小写字母组成的字符串S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在S上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

2.使用栈：刚开始写的时候用了两个栈，用来入栈与出栈。。。

class Solution {
    public String removeDuplicates(String s) {
        //借助两个栈
        char[] arr = s.toCharArray();
        Stack stackIn = new Stack<>();
        Stack stackOut = new Stack<>();
        for (char i : arr) {
            stackIn.push(i);
        }
        while (!stackIn.isEmpty()) {
            char temp = stackIn.pop();
            if (stackOut.isEmpty()) stackOut.push(temp);
            else if (stackOut.peek() == temp) stackOut.pop();
            else stackOut.push(temp); 
        }
        char[] res = new char[stackOut.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = stackOut.pop();
        }
        return new String(res);
    }
}

3.使用一个队列：这里需要用到deque（要操作最后加入的也就是队尾元素）。

class Solution {
    public String removeDuplicates(String s) {
        char[] arr = s.toCharArray();
        Deque deque = new LinkedList<>();
        for (char ele : arr) {
            if (deque.isEmpty()) deque.offer(ele);
            else if (deque.peekLast() == ele) deque.pollLast();//queue无这些方法
            else deque.offer(ele);
        }
        char[] res = new char[deque.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = deque.poll();
        }
        return new String(res);
    }
}

4.使用一个栈：最后stack弹出顺序需要反过来。

class Solution {
    public String removeDuplicates(String s) {
        char[] arr = s.toCharArray();
        Stack stack = new Stack<>();
        for (char ele : arr) {
            if (stack.isEmpty()) stack.push(ele);
            else if (stack.peek() == ele) stack.pop();
            else stack.push(ele);
        }
        char[] res = new char[stack.size()];
        for (int i = res.length - 1; i >= 0; i--) {//逆序遍历
            res[i] = stack.pop();
        }
        return new String(res);
    }
}

5.直接使用StringBuilder：

class Solution {
    public String removeDuplicates(String s) {
        char[] arr = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (char ele : arr) {
            if (sb.length() == 0) sb.append(ele);
            else if (sb.charAt(sb.length() - 1) == ele) sb.deleteCharAt(sb.length() - 1);
            else sb.append(ele);
        }
        return sb.toString();
    }
}