Leetcod面试经典150题刷题记录 —— 栈篇

1. 有效的括号

题目链接：有效的括号 - leetcode
题目描述：
给定一个只包括 ( ，)，{，}，[，] 的字符串 s ，判断字符串是否有效。有效字符串需满足：
(1)左括号必须用相同类型的右括号闭合。
(2)左括号必须以正确的顺序闭合。
(3)每个右括号都有一个对应的相同类型的左括号。
题目归纳：
经典面试题，一定要掌握

解题思路：
(1) 解法： 有效的括号 - leetcode官方题解

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {")":"(", "]":"[", "}":"{"}

        # (1)左括号入栈，遇到右括号就出栈
        s_len = len(s)
        stack = list()
        for i in range(s_len):
            ch = s[i]
            if ch in dic and len(stack) > 0 and dic[ch] == stack[-1]: # (2)右括号，且匹配正确
                stack.pop(-1)
            else: # (3)左括号需入栈
                stack.append(ch)


        # (4)最后栈空即是有效括号的字符串
        if len(stack) == 0:
            return True
        return False

2. 简化路径

题目链接：简化路径 - leetcode
题目描述：
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能 以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
返回简化后得到的 规范路径 。
题目归纳：

解题思路：
(1) 解法： 简化路径 - leetcode官方题解

class Solution:
    def simplifyPath(self, path: str) -> str:
        # 使用栈结构
        # (1)将字符串path根据/分割成字符串数组paths，paths共包含以下元素
        #    (a)空字符串。分割多个连续的///时出现。无需处理
        #    (b). 无需处理
        #    (c)..
        #    (d)dir_name
        paths = path.split('/')
        print(paths)
        
        # (2)建栈
        stack = list()
        for i in range(len(paths)):
            path = paths[i]
            if path == "..": # 遇到.. ，栈顶元素出栈
                if stack:    # 允许/../../../../这种反复cd到根目录的情况，相当于在stack空的时候丢弃了..
                    stack.pop()
            elif path == ".":
                continue
            elif path != "": # 遇到dir_name ，元素入栈            
                stack.append(path)
                
        # (3)最后用/，从栈底到栈顶依次连接栈内元素，并在最前面加上/表示根目录，即为规范路径
        return "/" + "/".join(stack)

3. 最小栈

题目链接：最小栈 - leetcode
题目描述：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

-2³¹ <= val <= 2³¹ - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, getMin最多被调用 3 * 104 次

题目归纳：
首先，只靠一个单独的普通的栈，无法做到这点，即便做到也需要O(n)的时间，所以一定会需要额外空间，这确定了本题的方向与思路，即开辟额外的空间去记录信息作为辅助

解题思路：
(1) 解法： 简化路径 - leetcode官方题解

# 首先，只靠一个单独的普通的栈，无法做到这点，即便做到也需要O(n)的时间
# 所以一定会需要额外空间，这确定了本题的方向与思路，即开辟额外的空间去记录信息作为辅助
# 空间复杂度：存储 信息的开销。
# 时间复杂度：计算 信息的开销。
# 由于存储设备RAM相对比较低廉，主要考虑的都是空间换时间

# 一边往正常的stack压元素，一边往min_stack压当前的最小值
# 当一个元素入栈时，取当前辅助栈栈顶存储的min_value，与当前元素比较得出min_value，将这个min_value插入辅助栈中；


class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = [math.inf] # 若取到math.inf说明栈空

    def push(self, val: int) -> None:
        self.stack.append(val)
        self.min_stack.append(min(self.min_stack[-1], val))

    def pop(self) -> None:
        self.stack.pop(-1)
        self.min_stack.pop(-1)

    def top(self) -> int:
        return self.stack[-1]


    def getMin(self) -> int:
        return self.min_stack[-1]



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

4. 逆波兰表达式求值

题目链接：逆波兰表达式求值 - leetcode
题目描述：
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

题目归纳：
向零取整：正数向下取整，负数向上取整。

解题思路：
(1) 解法： 逆波兰表达式求值 - leetcode官方题解
(2) 解法： 逆波兰表达式求值 - 负雪明烛民间题解

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for token in tokens:
            if token == "+":    
                num2 = stack.pop(-1)
                num1 = stack.pop(-1)
                stack.append(num1 + num2)
            elif token == "-":
                num2 = stack.pop(-1)
                num1 = stack.pop(-1)
                stack.append(num1 - num2)
            elif token == "*":
                num2 = stack.pop(-1)
                num1 = stack.pop(-1)
                stack.append(num1 * num2)
            elif token == "/":
                num2 = stack.pop(-1)
                num1 = stack.pop(-1)
                stack.append(int(num1 / num2)) # 向0取整
            else: # number
                stack.append(int(token))

        return stack[0]

5. 基本计算器

题目链接：基本计算器 - leetcode
题目描述：
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例：
输入：s = “(1+(4+5+2)-3)+(6+8)”
输出：23

题目归纳：
向零取整：正数向下取整，负数向上取整。

解题思路：
(1) 解法： 逆波兰表达式求值 - leetcode官方题解
(2) 解法： 逆波兰表达式求值 - 负雪明烛民间题解

class Solution:
    def calculate(self, s: str) -> int:
        # 括号展开+符号栈

        # 括号展开：将表达式中所有的括号展开，得到新表达式
        # 维护一个栈ops，其栈顶元素记录了当前位置所处的每个括号所共同形成的符号
        # 如：对于 1+2+(3-(4+5))
        # (1)扫描到1+2时，当前位置没有被任何括号所包含，ops栈顶元素为初始值+1
        # (2)扫描到1+2+(3时，当前位置被一个括号所包含，该括号前面的符号为 + 号，因此ops栈顶元素依然 +1；
        # (3)扫描到1+2+(3-(4时，当前位置被两个括号所包含，分别对应着 + 号和 ? 号，由于 + 号和 ? 号合并的结果为 ? 号，因此栈顶元素变为 ?1。
        # 由于只有加减，所以不需要考虑乘除对优先级的影响

        s = s.replace(" ","") # 去除空格
        ops = []
        ops.append(1) # +号
        sign = 1

        ret = 0
        n = len(s)
        i = 0
        while i < n:
            if s[i] == "+":
                sign = ops[-1] # top()
                i += 1
            elif s[i] == "-":
                sign = -ops[-1]
                i += 1
            elif s[i] == "(": 
                ops.append(sign)
                i += 1
            elif s[i] == ")":
                ops.pop(-1)
                i += 1
            else: # 遇到了number的最高位，如"123"，但还需要把"123"变成真正的数值123
                num = 0
                while i < n and ord("0") <= ord(s[i]) and ord(s[i]) <= ord("9"):
                    num = num*10 + ord(s[i]) - ord("0")
                    i += 1
                ret += sign * num
        return ret