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不返回数组,没法连着用.

Day11 20. 有效的括号 ● 1047. 删除字符串中的所有相邻重复项 ● 150. 逆波兰表达式求值