- 思路
- example
- 用list实现stack (FILO), 用dict记录配对。
- 最后return的时候注意判断stack是否非空。
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def isValid(self, s: str) -> bool:
n = len(s)
if n % 2 == 1:
return False
pairs = {')': '(',
']': '[',
'}': '{'}
stack = list()
for ch in s:
if ch not in pairs:
stack.append(ch)
else:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
return not stack
class Solution:
def isValid(self, s: str) -> bool:
n = len(s)
mapping = {'(': ')', '[': ']', '{': '}'}
stack = []
for i in range(n):
if s[i] in mapping:
stack.append(s[i])
else:
if stack == [] or mapping[stack.pop()] != s[i]:
return False
if stack == []:
return True
else:
return False
class Solution:
def isValid(self, s: str) -> bool:
pairs = {'(' : ')', '[': ']', '{': '}'}
stack = []
for ch in s:
if ch in pairs:
stack.append(ch)
else:
if stack == []: # !!!
return False
else:
ch0 = stack.pop()
if pairs[ch0] != ch: # !!!
return False
if stack: # !!!
return False
return True
- 思路
- example: "abbaca" --> "ca"
- list: stack (FILO)
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = list()
for ch in s:
if not stack or stack[-1] != ch:
stack.append(ch)
else:
stack.pop()
return ''.join(stack)
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = []
for ch in s:
if stack == [] or stack[-1] != ch:
stack.append(ch)
else:
stack.pop()
return ''.join(stack)
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = []
for ch in s:
if stack == []:
stack.append(ch)
else:
if stack[-1] == ch:
stack.pop()
else:
stack.append(ch)
return ''.join(stack)
- 思路
- example
- list: stack
- 字符串与数字的转化。
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
opes = ['+', '-', '*', '/']
for ch in tokens:
if ch not in opes:
stack.append(int(ch))
else:
num2 = stack.pop()
num1 = stack.pop()
if ch == '+':
stack.append(num1 + num2)
elif ch == '*':
stack.append(num1 * num2)
elif ch == '-':
stack.append(num1 - num2)
elif ch == '/':
# stack.append(num1 // num2) # 6 // (-132) = -1
stack.append(int(num1 / num2))
return stack[0]
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
n = len(tokens)
stack = []
# opes = set('+', '-', '*', '/')
opes = ['+', '-', '*', '/']
for ch in tokens:
if ch not in opes:
stack.append(int(ch))
else:
second = stack.pop()
first = stack.pop()
if ch == '+':
stack.append(first + second)
elif ch == '-':
stack.append(first - second)
elif ch == '*':
stack.append(first * second)
else:
# stack.append(first // second)
stack.append(int(first / second))
return stack[0]
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
set1 = {'+', '-', '*', '/'}
stack = []
for ch in tokens:
if ch not in set1:
stack.append(int(ch))
else:
num2 = stack.pop()
num1 = stack.pop()
if ch == '+':
stack.append(num1+num2)
elif ch == '-':
stack.append(num1-num2)
elif ch == '*':
stack.append(num1*num2)
else:
stack.append(int(num1/num2))
return stack[-1]
