20. 有效的括号 - 力扣（LeetCode）
解题思路
一共三种情况：左括号多了，左右不匹配，右括号多了；左括号变成右括号的样子先入栈，等遍历到右括号的时候就可以直接消掉了
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
for ch in s:
if ch == '(':
stack.append(')')
elif ch == '[':
stack.append(']')
elif ch =='{':
stack.append('}')
elif stack == [] or stack[-1] !=ch: #判断右边多和不匹配
return False
else:
stack.pop()
if stack == []:# 判断左边括号多
return True
else:
return False
方法二 双指针 很绝
class Solution(object):
def removeDuplicates(self, s):
"""
:type s: str
:rtype: str
"""
# 双指针
slow = fast = 0
s = list(s)
while fast < len(s):
s[slow] = s[fast]
if slow>0 and s[slow] == s[slow-1]: #如果和前一个一样，退一个指针
slow -= 1
else:
slow += 1
fast += 1
return "".join(s[:slow])
- 指针也可以回退
150. 逆波兰表达式求值 - 力扣（LeetCode）
解题思路
从头到尾遍历，数字压入栈，遇到运算符就pop出两个元素做运算，得到结果再压入栈，最后pop出栈中最后一个元素
class Solution(object):
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
op_map = {'+':add, '-':sub, '*':mul, '/':lambda x, y: int(x/float(y))}
stack = []
for ch in tokens:
if ch not in op_map:
stack.append(int(ch))
else:
op2 = stack.pop()
op1 = stack.pop()
stack.append(op_map[ch](op1,op2))
return stack.pop()
-
有几个坑注意
2、python中除法：
1、数字元素要变成int型
image.png
