网站403错误,wordpress 文章 相册,中国建设监理协会化工监理协会网站,网站开发工作方向栈和队列
栈和队列基础#xff08;Python#xff09;
栈一种先进后出#xff0c;队列先进后出。 Python中可以用list实现栈#xff0c;用append()模拟入栈#xff0c;用pop()模拟出栈。 也可以用list实现队列#xff0c;但是效率较低#xff0c;一般用collections.deq…栈和队列
栈和队列基础Python
栈一种先进后出队列先进后出。 Python中可以用list实现栈用append()模拟入栈用pop()模拟出栈。 也可以用list实现队列但是效率较低一般用collections.deque模拟双端队列。 5. 数据结构 — Python 3.11.5 文档
使用list进行栈的操作
stack [3, 4, 5]
stack.append(6)
stack.append(7)
stack
[3, 4, 5, 6, 7]
stack.pop()
7
stack
[3, 4, 5, 6]使用collections.dequez进行队列操作
from collections import deque
queue deque([Eric, John, Michael])
queue.append(Terry) # Terry arrives
queue.append(Graham) # Graham arrives
queue.popleft() # The first to arrive now leaves
Eric
queue.popleft() # The second to arrive now leaves
John
queue # Remaining queue in order of arrival
deque([Michael, Terry, Graham])232.用栈实现队列
#模拟 请你仅使用两个栈实现先入先出队列。
思路 使用两个栈stackin和stackout分别进行入队和出队。 出队时如果stackout为空将stackin 倒入 stackout。
class MyQueue:def __init__(self):self.stackin []self.stackout []def push(self, x: int) - None:self.stackin.append(x)def pop(self) - int:if self.empty():return Noneif not self.stackout:while self.stackin:self.stackout.append(self.stackin.pop())return self.stackout.pop()def peek(self) - int:res self.pop()self.stackout.append(res)return resdef empty(self) - bool:return not (self.stackin or self.stackout)
225. 用队列实现栈
#模拟
重点还是pop。使用队列弹出元素时需要先把之前的n-1个元素弹出才能弹出第n个元素。 所以这里先弹出n-1个元素并添加到队列末尾然后第n个元素就到了队列的开头。 这题没法仿照232的思路。注意队列和栈的区别栈是反转元素进出顺序的两次反转则变为先进先出。而队列是保持顺序的进出两次队列后顺序不变。 class MyStack:def __init__(self):self.que deque()def push(self, x: int) - None:self.que.append(x)def pop(self) - int:if self.empty():return Nonefor i in range(len(self.que)-1):self.que.append(self.que.popleft())return self.que.popleft()def top(self) - int:if self.empty():return Nonereturn self.que[-1]def empty(self) - bool:return not self.que20. 有效的括号
#栈 给定一个只包括 (){}[] 的字符串 s 判断字符串的括号是否有效。
栈的应用使用栈来存储左括号遇到右括号则弹出左括号进行匹配。
class Solution:def isValid(self, s: str) - bool:stack []d_k {(: ), {: }, [: ]}for c in s:if c in d_k.keys():stack.append(c)else:if len(stack) 0:return Falseleft stack.pop()if c ! d_k[left]:return Falsereturn len(stack) 01047. 删除字符串中的所有相邻重复项
删除字符串的相邻重复字母可以重复多次直到没有没有相邻重复项。
#模拟 #栈
class Solution:def removeDuplicates(self, s: str) - str:stack []for c in s:if len(stack) 0 and stack[-1] c:stack.pop()else:stack.append(c)return .join(stack)150. 逆波兰表达式求值
#栈 逆波兰表达式又叫后缀表达式运算符在操作数的后面如1 2 我们一般写的是中缀表达式运算符在操作数的中间如 1 2 输入 tokens [“2”,“1”,“”,“3”,“*”] 输出 9 解释 该算式转化为常见的中缀算术表达式为((2 1) * 3) 9
借助栈比较容易计算后缀表达式遇到操作数就入栈遇到运算符就弹出前面两个数然后计算并将计算结果入栈。
class Solution:def evalRPN(self, tokens: List[str]) - int:stack []res 0for i in tokens:if i :a stack.pop()b stack.pop()stack.append(ba)elif i - :a stack.pop()b stack.pop()stack.append(b-a)elif i * :a stack.pop()b stack.pop()stack.append(b*a)elif i /:a stack.pop()b stack.pop()stack.append(int(b/a))else :stack.append(int(i))return int(stack[-1])看起来有点重复可以简化一下
class Solution:def evalRPN(self, tokens: List[str]) - int:stack []res 0op_map {: add, -: sub, *: mul, /: lambda x, y: int(x / y)}for i in tokens:if i in op_map.keys():a stack.pop() # 后b stack.pop() # 前stack.append(op_map[i](b,a)) # 注意顺序 b op aelse :stack.append(int(i))return int(stack[-1])239. 滑动窗口最大值
#单调队列 #队列 整体思路希望有一个队列在滑动窗口的时候用push添加新的元素用pop弹出被删除的元素并且能直接获取队列的最大元素。 也就是说我们希望实现一个队列存储可能成为窗口中最大值的元素。称为单调队列
为了方便添加和删除元素使用双端队列存储数据。 self.queue deque()添加操作 push 添加元素value时如果队列末尾比value小就pop掉然后添加value。也就意味着队列中的元素都比新加入的value大。push操作很关键保证了队列中的元素是单调递减的因此后面可以用self.queue[0]获取最大值
def push(self, value):while self.queue and value self.queue[-1]:# 队列末尾比value小则删除self.queue.pop() # pop弹出队列末尾元素self.queue.append(value)删除操作 pop删除元素value时如果value等于队首元素que[0]则弹出队首popleft()。
def pop(self, value):if self.queue and value self.queue[0]:self.queue.popleft() # 弹出队首元素获取最大值
def front(self):return self.queue[0]使用单调队列来解决滑动窗口最大值就比较简单了不断地调用pop和push和 front。
class MyQueue:def __init__(self):self.queue deque()# 删除value 如果value 在队首则删除def pop(self, value):if self.queue and value self.queue[0]:self.queue.popleft()# 添加value valuea前面的比value小的都删除def push(self, value):while self.queue and value self.queue[-1]:self.queue.pop()self.queue.append(value)def front(self):return self.queue[0]class Solution:def maxSlidingWindow(self, nums: List[int], k: int) - List[int]:que MyQueue()res []for i in range(k):que.push(nums[i])res.append(que.front())for i in range(k, len(nums)):que.pop(nums[i-k])que.push(nums[i])res.append(que.front())return res347.前 K 个高频元素
#优先级队列 #堆 给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。
最容易想到的是用字典统计频率然后排序。
class Solution:def topKFrequent(self, nums: List[int], k: int) - List[int]:mmap Counter(nums)sort sorted(zip(mmap.values(),mmap.keys()), reverseTrue)res []for i in range(k):res.append(sort[i][1])return res用堆排序我们只需要维护一个大小为k的堆优先级队列。 在Python中可以用heapq或queue.PriorityQueue 实现。 heapq — 堆队列算法 — Python 3.11.5 文档 queue — 一个同步的队列类 — Python 3.11.5 文档
使用heapq
import heapq
class Solution:def topKFrequent(self, nums: List[int], k: int) - List[int]:#要统计元素出现频率map_ Counter(nums)#对频率排序#定义一个小顶堆大小为kpri_que [] #小顶堆#用固定大小为k的小顶堆扫描所有频率的数值for key, freq in map_.items():heapq.heappush(pri_que, (freq, key))if len(pri_que) k: #如果堆的大小大于了K则队列弹出保证堆的大小一直为kheapq.heappop(pri_que)#找出前K个高频元素因为小顶堆先弹出的是最小的所以倒序来输出到数组result [0] * kfor i in range(k-1, -1, -1):result[i] heapq.heappop(pri_que)[1]return result使用PriorityQueue
class Solution:def topKFrequent(self, nums: List[int], k: int) - List[int]:#要统计元素出现频率map_ Counter(nums)#对频率排序from queue import PriorityQueue as PQpri_que PQ(k1) #优先级队列(相当于小根堆) 最多放k1个元素#用固定大小为k的小顶堆扫描所有频率的数值for key, freq in map_.items():pri_que.put((freq, key))if pri_que.qsize() k:pri_que.get()print(pri_que.queue)#找出前K个高频元素因为小顶堆先弹出的是最小的所以倒序来输出到数组result [0] * kfor i in range(k-1, -1, -1):result[i] pri_que.get()[1]return result栈和队列小结
栈主要用来处理相邻匹配问题队列可以处理滑动窗口的最值问题单调队列前k个最值问题优先级队列/小根堆。
python中栈可以用list实现队列用colelctions.deque实现。
stack [3, 4, 5]
stack.append(6)
stack.append(7)
stack.pop()import collections
queue collections.deque()
queue.append(1) # 入队
queue.append(2)
queue.popleft() # 出队此外还用到了优先级队列堆默认实现的是小根堆堆顶元素最小。
import heapq
pri_que [] #小顶堆
heapq.heappush(pri_que, 1) # 入队
heapq.heappush(pri_que, 2)
heapq.heappop(pri_que) # 出队
