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

20. 有效的括号

思路

使用栈来存左括号，遇到对应的右括号就出栈。最后判断栈是否为空。

代码

写法一

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []

        for i in s:
            if i == "(":
                stack.append(")")
            elif i == "[":
                stack.append("]")
            elif i == "{":
                stack.append("}")
            elif stack and i == stack[-1]:
                stack.pop()
            else:
                return False

        return True if not stack else False

写法二

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        closeToOpen = {")":"(",
                        "}":"{",
                        "]":"["}
        
        for i in s:
            if i in closeToOpen:
                if stack and stack[-1] == closeToOpen[i]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(i)
        
        return True if not stack else False

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)

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

思路

把字母放入栈，遇到相同的就出栈，最后返回栈。

代码

写法一

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []

        for i in s:
            if stack and stack[-1] == i:
                stack.pop()
            else:
                stack.append(i)
            
        return "".join(stack)

• 时间复杂度: O(n)
• 空间复杂度: O(n)

写法二 用指针来模拟栈

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack_ind = 0
        s = list(s)

        for i in s:
        	# 模拟栈，push
            s[stack_ind] = i
			
			# pop
            if stack_ind > 0 and s[stack_ind] == s[stack_ind - 1]:
                stack_ind -= 1
            else:
            	# 指针前进一位，方便下一次push
                stack_ind += 1
        
        return "".join(s[:stack_ind])

• 时间复杂度: O(n)
• 空间复杂度: O(1)

150. 逆波兰表达式求值

思路

把数字存入栈，遇到算符便取出栈顶两位数字进行运算。

需要注意的是

• 从栈顶取出数字的顺序，a, b = stack.pop(), stack.pop()，那么[a, b, /] 就等同与b / a
• 因为整数间的除法是向零截断，所以我们需要使用int(a/b)。a // b是向负无穷截断。举个例子，int(-7 / 3) 为 -2，但是-7 // 3为-3。

代码

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        symbols = ["+", "-", "*", "/"]

        for i in tokens:
            if i not in symbols:
                stack.append(int(i))
            elif i == symbols[0]:
                a = stack.pop()
                b = stack.pop()
                stack.append(a + b)
            elif i == symbols[1]:
                a = stack.pop()
                b = stack.pop()
                stack.append(b - a)
            elif i == symbols[2]:
                a = stack.pop()
                b = stack.pop()
                stack.append(a * b)                          
            elif i == symbols[3]:
                a = stack.pop()
                b = stack.pop()
                stack.append(int(b/a))
        
        return stack[-1]

卡哥的代码更简洁：

from operator import add, sub, mul

class Solution:
    op_map = {'+': add, '-': sub, '*': mul, '/': lambda x, y: int(x / y)}
    
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token not in {'+', '-', '*', '/'}:
                stack.append(int(token))
            else:
                op2 = stack.pop()
                op1 = stack.pop()
                stack.append(self.op_map[token](op1, op2))  # 第一个出来的在运算符后面
        return stack.pop()

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)