20. 有效的括號 - 力扣（LeetCode）
解題思路
一共三種情況：左括號多了慈鸠，左右不匹配，右括號多了灌具；左括號變成右括號的樣子先入棧青团，等遍歷到右括號的時(shí)候就可以直接消掉了
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]: #如果和前一個(gè)一樣譬巫，退一個(gè)指針
slow -= 1
else:
slow += 1
fast += 1
return "".join(s[:slow])
- 指針也可以回退
150. 逆波蘭表達(dá)式求值 - 力扣（LeetCode）
解題思路
從頭到尾遍歷，數(shù)字壓入棧督笆，遇到運(yùn)算符就pop出兩個(gè)元素做運(yùn)算芦昔，得到結(jié)果再壓入棧，最后pop出棧中最后一個(gè)元素
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()
-
有幾個(gè)坑注意
2咕缎、python中除法：
1娃肿、數(shù)字元素要變成int型
image.png
