Leetcoder Day10｜栈与队列part02（栈的应用）

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

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

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

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

示例：

• 输入："abbaca"
• 输出："ca"
• 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

• 1 <= S.length <= 20000
• S 仅由小写英文字母组成。

因为本题涉及两个相邻且相同，转换思路就是，如果字符串里存在对称的结构，我们就会进行删除，实际上跟上一题有效括号匹配的题思路是一样的。只不过在括号里我们要判断的是不匹配的情况，而这里我们要删除匹配的情况因此可以将字符串遍历，先判断再入栈，如果当前字符与栈顶元素相同，则把栈顶元素弹出，如果不等，则放入栈中。随后将栈中剩余的元素依次弹出再把字符串进行翻转返回即可。如果是Java，使用StringBuilder类的reverse()方法来翻转字符串。

??使用栈的用时和内存都较高，因此使用ArrayDeque效率会更高，删除会更快而且节省了翻转操作。

//使用栈
class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
             char ch=s.charAt(i);
             if(stack.isEmpty()||stack.peek()!=ch) stack.push(ch);
             else stack.pop();
        }
        s = "";
        while(!stack.isEmpty()){
            s+=stack.pop(); 
        }
        StringBuilder sb = new StringBuilder();
        for(int i=s.length()-1;i>=0;i--){
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

//使用deque

class Solution {
    public String removeDuplicates(String s) {
        ArrayDeque<Character> deque = new ArrayDeque<>();
        for(int i=0;i<s.length();i++){
             char ch=s.charAt(i);
             if(deque.isEmpty()||deque.peek()!=ch) deque.push(ch);
             else deque.pop();
        }
        s = "";
        while(!deque.isEmpty()){
            s+=deque.pollLast();
        }
        return s;
        
    }
}

优化的方法还可以拿字符串直接作为栈，省去了栈还要转为字符串的操作。这样的话设置一个指针top，指向字符串末尾元素，即栈顶。

class Solution {
    public String removeDuplicates(String s) {
        StringBuffer str=new StringBuffer();
        int top=-1; //设置一个指针指向栈顶，即字符串尾部
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(top>=0 && str.charAt(top)==ch){
                str.deleteCharAt(top);
                top--;
            }
            else{
                // 将当前元素接入字符串，top指向最后一个元素
                str.append(ch);
                top++;
            }
        }
        return str.toString();
        
    }
}

150.?逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。

有效的运算符包括?+ ,? - ,? * ,? /?。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例?1：

• 输入: ["2", "1", "+", "3", " * "]
• 输出: 9
• 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例2:

• 输入：tokens = ["4","13","5","/","+"]
  输出：6
  解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

根据逆波兰的第二个优点其实本题的做法就已经呼之欲出了，数据结构中，后缀表达式往往可以用后序二叉树展现出来。本题思路可以简化为，遇到一个符号则把符号前面的拿出来进行符号对应的操作再压入栈中，很像上一题相邻重复项的思路，只不过这里的重复项定义为数字。

??本题有几个需要注意的语法事项：

1. 这里的tokens定义的是数组类型，因此不能用length()方法来提取长度而是使用length
2. 在进行减法操作时，不能简单的使用deque.pop() -?deque.pop()，不然如下图会变成’3-4‘，因为这个是栈，遵守先进后出原则，减数应该在被减数前被弹出来的，所以要用-?deque.pop()+deque.pop()才可以表达‘4-3’的结果。

   

3. 同理，除法操作也应该注意。
4. 将数字存入栈时，应该注意转换为整型

class Solution {
    public int evalRPN(String[] tokens) {
        ArrayDeque<Integer> deque=new ArrayDeque<>();
        for (int i = 0; i < tokens.length; i++) {
            String ch = tokens[i];
            if(ch.equals("+")) deque.push(deque.pop() + deque.pop());
            //因为是栈，被减数是在减数后被弹出的
            else if(ch.equals("-")) deque.push(-deque.pop() + deque.pop());
            else if(ch.equals("*")) deque.push(deque.pop() * deque.pop());
            else if(ch.equals("/")) {
                int temp1 = deque.pop();//因为是栈，被除数是在除数后被弹出的
                int temp2 = deque.pop();
                deque.push(temp2 / temp1);
            }
            else deque.push(Integer.valueOf(ch));
        }
        return deque.pop();
    }
}

今日总结

今天主要进行了对栈常规问题的练习，遇到对称消除，对称匹配时，首选栈进行操作，且操作时要注意压入，弹出的顺序，不可搞混。且递归就是用栈来实现。