代码随想录day11 【栈和队列】 有效的括号 删除字符串中的所有相邻重复项 逆波兰表达式求值

栈适合解决匹配类问题

我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？

所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素，然后再去做对应的消除操作。

有效的括号

力扣题目
考点：栈(对称匹配类的题目)
思路：遍历这个字符串，当栈为空或者栈顶元素和遍历元素不相等的话，则把遍历元素添加到栈中，如果栈顶元素=遍历元素，则pop掉栈顶元素。
代码：
时间复杂度：O(n)
空间复杂度：O(n)

var isValid = function(s) {
    //若为单数，直接返回false
    if(s.length % 2 !==0) return false
    let stack=[]
    for(let i=0;i<s.length;i++){
        if(s[i] === '(' || s[i] === '[' ||s[i] === '{' ){
            stack.push(s[i])
            continue
        }
        if((s[i]===')' && '('=== stack[stack.length-1]) ||( s[i]===']' && '['=== stack[stack.length-1] )||(s[i]==='}' && '{'=== stack[stack.length-1])){
            stack.pop()
        }else{
            return false
        }
    }
    return stack.length === 0
};

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

力扣题目

考点：栈（匹配问题）
代码：
时间复杂度：O(n)
空间复杂度:O(n)

var removeDuplicates = function(s) {
    let stack=[]
    for(let i=0;i<s.length;i++){
        // 相同就弹出，
        // 不同就压栈
        if(stack[stack.length-1] === s[i]){
            stack.pop()
            continue
        }
        stack.push(s[i])
    }
    return stack.join('')
};

逆波兰表达式求值

力扣题目

注意：

1. 数字做运算的顺序
2. 遇到除号；结果小于0时，向上取整，；结果大于0时，向下取整
3. 遇到减号，且被减数小于零，即2--3的情况；将符号转换为正号进行运算

时间复杂度：O(n)
空间复杂度：O(n)

var evalRPN = function(tokens) {
   //遇到数字放进去
   //遇到符号，出栈两个数字；再把结果放进去
   let stack=[]
   let sign= '+-*/'
    let res =0

   for(let i in tokens){
       if(sign.includes(tokens[i])){
           let n1=stack.pop()
           let n2=stack.pop()

           if(tokens[i] ==='/'){ //若为除法，特殊处理
               res = ((n2)/(n1)) < 0? Math.ceil((n2)/(n1)): Math.floor((n2)/(n1))
           }else if(tokens[i] ==='-' && n1<0){ //若出现类似2--3的情况，特殊处理
               res= eval(n2+'+'+Math.abs(n1))
           }else{
             res = eval((n2)+tokens[i]+(n1))
           }
            stack.push(res)
           continue
       }
       stack.push(tokens[i])
   }
   return Number(stack[0])
};

参考：
感觉参考的代码更优雅:
入栈时，直接放入数字类型；求除数那里利用了按位或运算，简化写法：

n1 / n2 | 0

var evalRPN = function (tokens) {
    const stack = [];
    for (const token of tokens) {
        if (isNaN(Number(token))) { // 非数字
            const n2 = stack.pop(); // 出栈两个数字
            const n1 = stack.pop();
            switch (token) { // 判断运算符类型，算出新数入栈
                case "+":
                    stack.push(n1 + n2);
                    break;
                case "-":
                    stack.push(n1 - n2);
                    break;
                case "*":
                    stack.push(n1 * n2);
                    break;
                case "/":
                    stack.push(n1 / n2 | 0);
                    break;
            }
        } else { // 数字
            stack.push(Number(token));
        }
    }
    return stack[0]; // 因没有遇到运算符而待在栈中的结果
};