LeetCode刷题——栈（python语言）

一、栈

1.1 定义

栈（Stack）：也称堆栈。一种线性表数据结构，是一种只允许在表的一端进行插入和删除操作的线性表。

我们把栈中允许插入和删除的一端称为[栈顶(top)];另一端则称为[栈底(bottom)]。当表中没有任何数据元素时，称之为[空栈]。
栈的特点：

1. 线性表
2. 后进先出
   栈的存储方式有顺序栈和链式栈。

1.2 栈的基本操作

1. 初始化空栈
2. 判断栈是否为空
3. 判断栈是否已满
4. 插入元素
5. 删除元素
6. 获取栈顶元素

1.3 栈的顺序存储实现代码

class Stack:
	#初始化空栈
	def __init__(self,size=100):
		self.stack = []
		self.size = size
		self.top = -1
	
	#判断栈是否为空
	def is_empty(self):
		return self.top == -1
	
	#判断栈是否已满
	def is_full(self):
		return self.top + 1 == self.size
	
	#入栈操作
	def push(self,value):
		if self.is_full():
			raise Exception('Stack is full')
		else:
			self.stack.append(value)
			self.top += 1
	
	#出栈操作
	def pop(self):
		if self.is_empty():
			raise Exception('Stack is empty')
		else:
			self.top -= 1
			self.stack.pop()
		
	#获取栈顶元素
	def peek(self):
		if self.is_empty():
			raise Exception('Stack is empty')
		else:
			return self.stack(self.top)

1.4 栈的链式存储实现代码

class Node:
	def __init__(self,value):
		self.value = value
		self.next = next
	
class Stack:
	#初始化空栈
	def __init__(self):
		self.top = None

	#判断栈是否为空
	def is_empty(self):
		return self.top == None
	
	#入栈操作（类似于头插法）
	def push(self,value):
		cur = Node(value)
		cur.next = self.top
		self.top = cur

	#出栈操作
	def pop(self):
		if self.is_empty():
			raise Exception('Stack is empty')
		else:
			cur = self.top
			self.top = self.top.next
			del cur #删除栈顶元素

	#获取栈顶元素
	def peek(self):
		if self.is_empty():
			raise Exception('Stack is empty')
		else:
			return self.top.value

二、刷题

2.1 有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：
输入：s = “()”
输出：true

示例 2：
输入：s = “()[]{}”
输出：true

示例 3：
输入：s = “(]”
输出：false

示例 4：
输入：s = “([)]”
输出：false

示例 5：
输入：s = “{[]}”
输出：true

提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

#首先计算字符串长度，如果是奇数，返回False。首先，找到左侧括号，入栈，右括号且在栈顶，出栈。
class Solution:
    def isValid(self, s: str) -> bool:
        if(len(s)%2==1):
            return False
        stack = []
        for ch in s:
            if(ch == '(' or ch == '{' or ch=='['):
                stack.append(ch)
            elif(ch == ')'):
                if(len(stack)!=0 and stack[-1]=='('):
                    stack.pop()
                else:
                    return False
            elif(ch=='}'):
                if(len(stack)!=0 and stack[-1]=='{'):
                    stack.pop()
                else:
                    return False
            elif(ch==']'):
                if(len(stack)!=0 and stack[-1]=='['):
                    stack.pop()
                else:
                    return False
        if(len(stack)==0): #长度为0，说明全部匹配，成功匹配
            return True
        else:
            return False

2.2 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：
输入：tokens = [“2”,“1”,"+",“3”,"*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：
输入：tokens = [“4”,“13”,“5”,"/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：
输入：tokens = [“10”,“6”,“9”,“3”,"+","-11","","/","",“17”,"+",“5”,"+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：
1 <= tokens.length <= 104
tokens[i] 是一个算符（"+"、"-"、"*" 或 “/”），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

#根据逆波兰式，一次一次计算结果
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for ch in tokens:
            if(ch == '+'):
                stack.append(stack.pop() + stack.pop())
            elif(ch == '-'):
                stack.append(-stack.pop() + stack.pop())
            elif(ch == '*'):
                stack.append(stack.pop()*stack.pop())
            elif(ch=='/'):
                stack.append(int(1/stack.pop()*stack.pop()))
            else:
                stack.append(int(ch))
        return stack.pop()

2.3 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例:
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

提示：
pop、top 和 getMin 操作总是在 非空栈 上调用。

#用列表模拟栈，取最小值的时候选取排序后列表的第一个元素。
class MinStack:

    def __init__(self):
        self.stack = []
        
    def push(self, val: int) -> None:
        self.stack.append(val)

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

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

    def getMin(self) -> int:
        if(len(self.stack)>0):
            return sorted(self.stack)[0]
        else:
            return None
#340 ms	18.1 MB
#3 2
#不用sorted，可以把每次找的最小值记录在一个栈里min_stack.大小和stack一样。
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = [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()
        self.min_stack.pop()#最小数的栈的大小与栈的大小相同，统一删除
    def top(self) -> int:
        return self.stack[-1]
    def getMin(self) -> int:

        return self.min_stack[-1]
#48 ms	18.2 MB

2.4 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。

示例 1：
输入：s = “3+2*2”
输出：7

示例 2：
输入：s = " 3/2 "
输出：1

示例 3：
输入：s = " 3+5 / 2 "
输出：5

提示：
1 <= s.length <= 3 * 105
s 由整数和算符 (’+’, ‘-’, ‘*’, ‘/’) 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

#通过第一位的加号对符号处理，最后求和
class Solution:
    def calculate(self, s: str) -> int:
        n = len(s)
        stack = []
        preSigh = '+' #第一个数的前面自带一个加号。
        num = 0
        for i in range(n):
            if(s[i]!=' ' and s[i].isdigit()):
                num = num*10 - ord('0') + ord(s[i]) #处理多位数字符
            if(i == n-1 or s[i] in '+-*/'):#遍历到符号，或者最后分别处理
                if (preSigh == '+'): 
                    stack.append(num)
                elif (preSigh =='-'):
                    stack.append(-num)
                elif (preSigh == '*'):
                    stack.append(stack.pop()*num)
                else:
                    stack.append(int(stack.pop()/num))
                preSigh = s[i]
                num =0 
        return sum(stack)
#72 ms	16.9 MB

2.5 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
注意：如果对空文本输入退格字符，文本继续为空。

示例 1：
输入：s = “ab#c”, t = “ad#c”
输出：true
解释：S 和 T 都会变成 “ac”。

示例 2：
输入：s = “ab##”, t = “c#d#”
输出：true
解释：s 和 t 都会变成 “”。

示例 3：
输入：s = “a##c”, t = “#a#c”
输出：true
解释：s 和 t 都会变成 “c”。

示例 4：
输入：s = “a#c”, t = “b”
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。

提示：
1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 ‘#’

进阶：
你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

#1：用两个栈，分别根据#对列表处理，然后比较是否相等
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        stack_s = []
        stack_t = []
        for ch in s:
            if(ch != '#'):
                stack_s.append(ch)
            elif(len(stack_s)!=0):
                stack_s.pop()
        for ch in t:
            if(ch != '#'):
                stack_t.append(ch)
            elif(len(stack_t)!=0):
                stack_t.pop()
        if(len(stack_s)!=len(stack_t)):
            return False
        for i in range(len(stack_s)):
            if(stack_s[i]!=stack_t[i]):
                return False
        return True
#36 ms	15.2 MB
#2 
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        stack_s = []
        stack_c = []
        for i in s:
            if i != '#':
                stack_s.append(i)
            else:
                if not stack_s:
                    continue
                stack_s.pop()


        for i in t:
            if i != '#':
                stack_c.append(i)
            else:
                if not stack_c:
                    continue
                stack_c.pop()
        

        return True if ''.join(stack_s)==''.join(stack_c) else False #直接连接起来比较
#36 ms	15.2 MB