代码随想录算法训练营第十一天 | 150.逆波兰表达式求值 239.滑动窗口最大值 347.前 K 个高频元素

news/2024/10/19 21:17:16/

LeetCode 150.逆波兰表达式求值：

文章链接
题目链接：150.逆波兰表达式求值

思路：

① 使用栈进行运算，遇到操作数入栈，遇到运算符出栈两个元素后入栈
② 需要注意的是：所给的算式为string类型，需要转换为 int / long long类型后入栈；且题目要求除法为向零截断，操作数可能为负数(-2 / 3 = -1)，因此除法需要先判断操作数的正负后再进行除法运算
逆波兰表达式：

  • 是一种后缀表达式，也就是运算符写在后面的表达式。比如(1 + 2) * (3 + 4) 转换为逆波兰表达式即 ( ( 1 2 + ) ( 3 4 + ) * )。
  • 优点如下：
  • 去掉括号后无歧义，即去掉括号后也可以按照次序计算出正确结果
  • 使用用栈运算：遇到数字则入栈；遇到运算符弹出栈顶两个数字进行计算，并将结果压入栈中。（第二个弹出的是第一个操作数）
python">"""
方法1：遇到运算符后逐个判断并进行运算
"""
def div(op1, op2):return op1 // op2 if op1 * op2 > 0 else -(abs(op1) // abs(op2))
class Solution(object):def evalRPN(self, tokens):""":type tokens: List[str]:rtype: int"""stack = []op_set = {'+', '-', '*', '/'}for token in tokens:if token not in op_set:stack.append(int(token))else:op2 = stack.pop()op1 = stack.pop()	# 第二个弹出的为第一个操作数if token == '+': stack.append(op1 + op2)elif token == '-': stack.append(op1 - op2)elif token == '*' : stack.append(op1 * op2)else:stack.append(div(op1, op2))return stack.pop()
"""
方法2：借用operator库和字典实现字符运算符到实际的函数运算
"""
from operator import add, sub, mul
def div(op1, op2):return int(op1 / op2) if op1 * op2 > 0 else -(abs(op1) // abs(op2))class Solution(object):op_map = {'+':add, '-':sub, '*':mul, '/':div}def evalRPN(self, tokens):stack = []for token in tokens:if token not in self.op_map:stack.append(int(token))else:op2 = stack.pop()op1 = stack.pop()   # 后出现的为第一个操作数stack.append(self.op_map[token](op1, op2))return stack.pop()

感悟：

需要注意细节：将操作数转换为整数类型，第二个弹出的为第一个操作数，正负数的向零截取除法

LeetCode 239.滑动窗口最大值：

文章链接
题目链接：239.滑动窗口最大值

思路：

使用队列保存窗口中的元素，那么滑动窗口的最大值由队列中得到，那么维持一个单调队列，最大值为队首元素，但是push和pop需要对队列进行调整比较麻烦。
那么维持一个“单调双端队列”
① push (value)，若队尾元素 < value，出队队尾元素直到其值 >= value，从而维持了队列的单调。且需要返回的为滑动窗口最大值，要么出队的元素中没有队首最大值，对返回值无影响；要么出队元素中有队首最大值，那么value成为队首最大值。
② pop(value)，队首出队，由于push时将 < push_value的值全部出队了，且出队只能出队首元素，因此value == 队首元素时才出队。（若value < queue.front()，那么该元素在push时已经出队，且对于滑动窗口的最大值无影响；value > queue.front()，这种情况不存在）

python">from collections import deque
class Myqueue(object):def __init__ (self):self.queue = deque() # 使用双端队列构造单调队列，左队头，右队尾def pop(self, value):# 当弹出元素为队首元素时才弹出if self.queue and value == self.front():self.queue.popleft()def push(self, value):# push元素到队尾，为了保持单调队列；一直弹出队尾元素直到队尾元素 >= valuewhile self.queue and self.queue[-1] < value:self.queue.pop()self.queue.append(value)# 队首元素即窗口的最大元素def front(self):return self.queue[0]
class Solution(object):def maxSlidingWindow(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""queue = Myqueue()result = []# 将前k个加入单调队列中for i in range(k):queue.push(nums[i])result.append(queue.front())    # 保存每个窗口的最大值for i in range(k, len(nums)):queue.pop(nums[i - k])queue.push(nums[i])result.append(queue.front())return result

感悟：

“单调”双端队列的一种实现和利用

LeetCode 347.前K个高频元素：

文章链接
题目链接：347.前K个高频元素

思路：

① 统计并记录元素的频率和元素本身：map
② 对元素频率进行排序
③ 根据排序后的元素频率得到前 k 个高频元素
采用大小为 k 的优先级队列，其中优先级为频率。使用大小为 k 的小根堆实现该优先级队列（每次压入元素时，直接从堆顶弹出最小值，然后压入元素，从而留下的 k 个元素为频率前 k 的元素）。
需要注意的是python中使用heapq包来实现小根堆。heapqpush(pri_que, value)只能根据value元素建立小根堆（想建立大根堆的话使用value的负值建立小根堆，输出元素时再取负值）。建立优先级队列为heappush(pri_que, (pri, value))，根据 pri 在 pri_que中建立最小堆

python">import heapq
class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""# 统计频率map_num = {}for num in nums:map_num[num] = map_num.get(num, 0) + 1# 构造大小为k的小根堆得到频率前 k 高的元素pri_que = []for num, fre in map_num.items():if len(pri_que) < k:heapq.heappush(pri_que, (fre, num))elif fre > pri_que[0][0]:heapq.heappop(pri_que)heapq.heappush(pri_que, (fre, num))# 倒序存储堆弹出的元素result = [0] * kfor i in range(k - 1, -1, -1):result[i] = heapq.heappop(pri_que)[1]return result
"""
方法2：转换字典为fre_num，然后单独对频率进行排序并取排序后前 k 个高频元素
"""
from collections import defaultdict
class Solution(object):def topKFrequent(self, nums, k):# 统计频率map_num = {}for num in nums:map_num[num] = map_num.get(num, 0) + 1# 反转字典 (fre: num)fre_num = defaultdict(list)for num, fre in map_num.items():fre_num[fre].append(num)# 对频率进行排序fre_key = list(fre_num.keys())fre_key.sort(reverse=True)# 取出现频率前 k 高的元素result = []cnt, i = 0, 0while cnt < k:result += fre_num[fre_key[i]]cnt += len(fre_num[fre_key[i]])i += 1return result

感悟：

优先级队列的实现和字典的反转

学习收获：

① 学会了使用小根堆实现优先级队列
② 学会了“单调”双端队列的一种实现


http://www.ppmy.cn/news/1540341.html

相关文章

Leetcode 字符串解码

Leetcode 字符串解码

该代码的算法思想可以分为以下几个步骤&#xff1a; 1. 使用栈来处理嵌套结构&#xff1a; 我们需要处理像 k[encoded_string] 这种格式&#xff0c;其中的 encoded_string 可能是嵌套的&#xff0c;即像 3[a2[c]] 这样的输入。因此&#xff0c;我们可以借助 栈&#xff08;S…
阅读更多...
QJniObject--Qt中的Java交互类

QJniObject--Qt中的Java交互类

QJniObject QJniObject 是 Qt for Android 中用于与 Java 代码进行交互的一个类。它提供了一个方便的接口&#xff0c;使得 C 代码可以调用 Java 方法、访问 Java 对象和处理 Java 数据。以下是 QJniObject 的一些主要用途&#xff1a; 1. 调用 Java 方法 QJniObject 允许你…
阅读更多...
闯关leetcode——125. Valid Palindrome

闯关leetcode——125. Valid Palindrome

大纲 题目地址内容 解题代码地址 题目 地址 https://leetcode.com/problems/valid-palindrome/description/ 内容 A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads …
阅读更多...
专业学习｜马尔可夫链（概念、变体以及例题）

专业学习｜马尔可夫链（概念、变体以及例题）

一、马尔可夫链的概念及组成 &#xff08;一&#xff09;学习资料分享 来源&#xff1a;024-一张图&#xff0c;但讲懂马尔可夫决策过程_哔哩哔哩_bilibili 马尔可夫链提供了一种建模随机过程的方法&#xff0c;具有广泛的应用。在实际问题中&#xff0c;通过转移概率矩阵及初…
阅读更多...
从零开始学PHP之安装开发环境

从零开始学PHP之安装开发环境

前言 不整那些虚的&#xff0c;直接开始上干货&#xff0c;争取让小白也看得懂 环境选择 php开发环境一般分为集成环境和编译环境&#xff0c;由于编辑环境费时费力&#xff08;我没搞明白&#xff09;直接使用集成环境&#xff0c;市面上php的集成环境很多我这里用的是phps…
阅读更多...
leetcode计数排序

leetcode计数排序

计数排序&#xff08;counting sort&#xff09;通过统计元素数量来实现排序&#xff0c;通常应用于整数数组。 给定一个长度为 的数组 nums &#xff0c;其中的元素都是“非负整数” def counting_sort(nums: list[int]):"""计数排序"""# 完整实…
阅读更多...
Libevent源码剖析之reactor

Libevent源码剖析之reactor

1 简介 reactor 是一种事件驱动的并发处理模式&#xff0c;常用于网络服务器和事件循环系统中。它主要的功能是通过单线程或者多线程处理I/O操作&#xff0c;避免阻塞&#xff0c;并且能够高效处理大量并发的事件。 one loop per thread or process&#xff0c;以下摘自 reacto…
阅读更多...
泛微E-Cology系统 CptInstock1Ajax SQL注入漏洞复现

泛微E-Cology系统 CptInstock1Ajax SQL注入漏洞复现

0x01 产品描述&#xff1a; ‌ 泛微E-Cology是一款专为中大型组织设计的数字化办公系统&#xff0c;旨在创建高效协同的办公环境。‌ 该系统集成了智能化、平台化和全程数字化的特点&#xff0c;通过智能语音交互、与其他异构系统的集成以及电子印章、电子签名等技术的应用&a…
阅读更多...
最新文章

Copyright @ 2022~2023