1. 20.有效的符号

这题之前学校考过,看到已经忘记了.
看代码随想录的动画,很清楚了
要先把所有条件列出来,不要想的很复杂,我的思想里把左边缺,右边缺,左边多,右边多,不匹配,分成了5个,但是实际上缺或多是一种情况,比如左边多了其实就是右边少了.那样我们就只考虑一种情况,比如都考虑多的情况.这样真正的情况其实就是只有:

• 左边多了
• 右边多了
• 左右不匹配

1.1 思路

从头遍历,遇到一个左括号就往栈里塞一个

• 另一个思路:用map找,keywordin

1.2 tips

• 想到用switch了,但是还是写的特别麻烦
  我的解法:

  var isValid = function(s) {
    let stack = [];
    for(let i = 0;i<s.length;i++){
        // console.log(stack)
        switch (s[i]){
            case '{':
                stack.push('}');
                break;
            case '[':
                stack.push(']');
                break;
            case '(':
                stack.push(')');
                break;
            default:
                if(!stack.length && i <s.length) return false;
                else if(s[i]!== stack.pop()) return false;
                else continue;
        }
    }
    if(stack.length) return false;
    return true;
  };
  

  拿循环外的返回部分距离,就可以直接写成

  return !stack.length;
  

  • 其次,default那里只用判断返回值就行了,因为前面提到的三种情况,只有左边多的时候是循环完了判断,其他两种只需要判断数值是否匹配:右边多了的话,空数组pop出来的是undefined,自然不匹配;左右不匹配的话自然也不匹配.
  • 而且就算按我的写法else continue也是冗余代码
• switch的写法,我写成了

  switch s[i]:
        case '':
  

  正确写法:

  switch (){
  
  }
  

另一种解法:用map

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

• 题目
• 题解

另一个思路: 双指针来模拟栈

2.1 tips

• 这题虽然直接解出来了,但是还很多问题,比如split()是字符串的属性,得到的是数组,join()是数组的属性,加了“,”的意思是每个元素用,连接,得到的是字符串

  • 自己写的时候一是忘记用哪个属性,二是join('')返回的字符串又自己强转了一遍String(XX)

• 我的思路是先pop出来比较值,不一样再都塞回去.这样的开销肯定更大,更高效的思路应该是先判断和最后一个是不是一样,一样再pop.

  • js里最后一位不能用下标-1,只能用[length-1]

• 对于双指针思路,题解用到了

  s = [...s]
  

  这个叫扩展语法,可以用在数组/字符串上,用在字符串上的时候和.split(‘’)效果相同.

  用在数组上的时候,原始变量指向的数组实例会被替代,如

  let s = [1, 2, 3];
  console.log(s); // 输出: [1, 2, 3]
  
  let originalReference = s; // 保存对原数组的引用
  
  s = [...s];
  console.log(s); // 输出: [1, 2, 3]
  
  console.log(originalReference === s); // 输出: false
  

3. 150.逆波兰表达式求值

• 题目
• 题解

什么是逆波兰表达式:
就是后缀表达式,就是二叉树的后序遍历(左右中)

后序遍历二叉树

(人类看比较舒服的方式是中序表达式,左中右)
1+2 X 3 + 4,虽然看着舒服,但是想计算正确,必须得加上括号,但是后缀表达式直接从头到尾遍历就行了

3.1 思路

和前面两道题很像,这里是碰到数字就放到栈里,碰到操作符就拿两个数操作,结果再放回去.
因为后序遍历是左右中,所以先放进去的数永远在操作的前面

3.2 tips

• 我的担心是如果要拿两个元素,为什么不考虑两个栈里不足两个元素呢?
  • 因为题目默认你是符合规范的后缀表达式,所以下次遇到不要考虑这个
• js的number默认都是浮点型,所以除法要特别注意小数的问题
• 哪个在操作符号前,哪个在后的问题
• js的加法对string是直接拼接的,所以记得先转成Number()
• js里的取整技巧:

  • >>0右移运算符

  • XX | 0位或运算

  • Math.floor()和前两个不同,前两个是直接阶段小数位,这个是总向下取整
    没看题,人说了总是向下截断

console.log(3.7 | 0);      // 输出: 3
console.log(Math.floor(3.7));  // 输出: 3

console.log(-3.7 | 0);      // 输出: -3
console.log(Math.floor(-3.7));  // 输出: -4

• 最后不需要把结果pop出来,不然还要判断是不是最后一个值,没必要.直接放栈里就行了.
  -一开始还写出了个 stack.pop().pop().pop不返回数组,没法连着用.