代码随想录算法训练营第十一天|20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

【参考链接】

20. 有效的括号

【注意】

1.括号匹配是使用栈解决的经典问题。

2.这个命令最后进入a目录，系统是如何知道进入了a目录呢 ，这就是栈的应用（其实可以出一道相应的面试题了）。

3.有三种不匹配的情况，第一种情况，字符串里左方向的括号多余了 ；第二种情况，括号没有多余，但是 括号的类型没有匹配上；第三种情况，字符串里右方向的括号多余了。

【代码】

1.剪枝操作：字符串如果是奇数，直接就是不匹配。

 1 class Solution(object):
 2     def isValid(self, s):
 3         """
 4         :type s: str
 5         :rtype: bool
 6         """
 7         #方法1，仅使用栈
 8         stack = []
 9 
10         for item in s:
11             if item == '(':
12                 stack.append(')')
13             elif item == '{':
14                 stack.append('}')
15             elif item == '[':
16                 stack.append(']')
17             elif not stack or stack[-1] != item: #栈为空的话，或和右括号不匹配的时候，对应2，3情况
18                 return False
19             else:
20                 stack.pop()
21         
22         return True if not stack else False #s遍历完之后，如果栈不为空，对应第1种情况
23 
24         #方法2.使用字典
25         stack = []
26         mapping = {
27             '(':')',
28             '[':']',
29             '{':'}'
30         }
31 
32         for item in s:
33             if item in mapping.keys():
34                 stack.append(mapping[item])
35             elif not stack or stack[-1] != item:
36                 return False
37             else:
38                 stack.pop()
39         
40         return True if not stack else False

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

【注意】

1.栈帮助我们记录了 遍历数组当前元素时候，前一个元素是什么。

2.字符串模拟栈。

【代码】

 1 class Solution(object):
 2     def removeDuplicates(self, s):
 3         """
 4         :type s: str
 5         :rtype: str
 6         """
 7         #方法1.使用栈
 8         res = list()
 9 
10         for item in s:
11             if res and res[-1] == item:
12                 res.pop()
13             else:
14                 res.append(item)
15         
16         return ''.join(res) #字符串拼接
17 
18         #方法2.使用双指针模拟栈
19         res = list(s) #字符串转成列表
20         slow = fast = 0 #双指针
21         n = len(res)
22 
23         while fast < n:
24             #如果一样直接换，不一样会把后面的填在slow的位置
25             res[slow] = res[fast]
26 
27             #如果发现和前一个一样，就退一格指针
28             if slow > 0 and res[slow] == res[slow-1]:
29                 slow -= 1
30             else:
31                 slow += 1
32             fast += 1
33         
34         return ''.join(res[0:slow])

150. 逆波兰表达式求值

【注意】

1.逆波兰表达式就是一种后缀表达式。计算机进行顺序处理，不用关心优先级。

2.遇见数字就存放在栈里，遇见运算符就从栈里取数字，做一个计算，再把计算完的数字存放在栈里。

【代码】

 1 class Solution(object):
 2     op_map = {'+':add, '-':sub, '*':mul, '/':lambda x,y: int(x/y)}
 3     def evalRPN(self, tokens):
 4         """
 5         :type tokens: List[str]
 6         :rtype: int
 7         """
 8         # stack = []
 9         # for token in tokens:
10         #     if token not in {'+','-','*','/'}:
11         #         stack.append(int(token))
12         #     else:
13         #         op1 = stack.pop()
14         #         op2 = stack.pop()
15         #         stack.append(self.op_map[token](op1,op2))
16         
17         # return stack.pop()
18 
19         #方法2.使用eval 对字符串进行计算
20         stack = []
21         for item in tokens:
22             if item not in {'+','-','*','/'}:
23                 stack.append(item)
24             else:
25                 first_num, second_num = stack.pop(), stack.pop()
26                 # 第一个出来的在运算符后面
27                 stack.append(int(eval(f"{second_num}{item}{first_num}"))) #力扣上提示该语句语法错误，为什么？
28         
29         # 如果一开始只有一个数，那么会是字符串形式的
30         return int(stack.pop())