算法打卡 Day13(栈与队列)-滑动窗口最大值 + 前 K 个高频元素 + 总结

news/2024/7/21 10:38:15/文章来源:https://blog.csdn.net/Catherine121314/article/details/139126009

文章目录

  • Leetcode 239-滑动窗口最大值
    • 题目描述
    • 解题思路
  • Leetcode 347-前 K 个高频元素
    • 题目描述
    • 解题思路
  • 栈与队列总结

Leetcode 239-滑动窗口最大值

题目描述

https://leetcode.cn/problems/sliding-window-maximum/description/

在这里插入图片描述

解题思路

在本题中我们使用自定义的单调队列来实现:

pop:如果窗口移除的元素 value 等于单调队列的出口元素,那么队列弹出元素,否则不进行任何操作

push:如果 push 的元素 value 大于入口元素的数值,那么就将队列入口的元素弹出,直到 push 元素的数值小于队列入口元素的数值为止

返回当前窗口的最大值:调用 que.front()

class Solution {
private:class MyQueue {public:deque<int> que; //使用deque实现单调队列void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}int front() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;for (int i = 0; i < k; i++) {que.push(nums[i]);}result.push_back(que.front());for (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]);que.push(nums[i]);result.push_back(que.front());}return result;}
};

Leetcode 347-前 K 个高频元素

题目描述

https://leetcode.cn/problems/top-k-frequent-elements/description/

在这里插入图片描述

解题思路

这道题目需要解决三个部分的问题:

1. 统计元素的出现频率:
我们可以使用 unordered_map 来解决,其中 key 表示元素的值,value 表示值出现的次数
2. 对频率进行排序:
使用优先级队列,其是一个披着队列外衣的堆。优先级队列对外接口是从队头取元素,从队尾添加元素,其内部的元素自动依照元素的权值排列。优先级队列缺省情况下 priority_queue 利用 max-heap 大顶堆完成对元素的排列,大顶堆是以 vector 为表现形式的完全二叉树。

堆是完全二叉树,树中的每个结点都不小于(或不大于)其左右孩子的值。父亲结点大于等于左右孩子的是大顶堆,小于等于左右孩子的是小顶堆。

选用优先级队列而不是快排:我们只需要报告前 K 个高频元素而不是全部元素,因此只需要维护 K 个有序序列即可,当 n 非常大时,这样的方法可以降低时间复杂度。

使用小顶堆而不是大顶堆:因为要统计最大前 K 个元素,如果选用大顶堆会将最大的元素弹出不符合要求,而使用小顶堆可以每次将最小的元素弹出,最后小顶堆中积累的才是前 K 个最大元素。

3. 找出前 K 个高频元素

class Solution {
public://小顶堆class mycomparison{public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {//统计元素出现的频率unordered_map<int, int>map;for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}//根据频率进行排序//定义一个小顶堆,大小为kpriority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;//用固定大小为k的小顶堆,扫描所有频率的数值for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) {//如果堆的大小大于k,则从队列弹出pri_que.pop();}}//找出前k个高频元素,小顶堆先弹出最小的,所以使用倒序输出数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}};

栈与队列总结

栈和队列是容器适配器,底层容器使用不同的容器,那么栈内数据在内存中的分布就不一定连续。
在缺省状况下,栈和队列的默认底层容器时 deque,其内存分布不连续。

递归的实现是栈:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中,然后递归返回的时候,从栈顶弹出上一次递归的各项参数,所以这就是递归为什么可以返回上一层位置的原因。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ldbm.cn/p/430171.html

如若内容造成侵权/违法违规/事实不符,请联系编程新知网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】Linux的权限_2 + Linux环境基础开发工具_1

文章目录 三、权限3. Linux权限管理修改文件的拥有者和所属组 4. 文件的类型5. 权限掩码 四、Linux环境基础开发工具1. yumyum 工具的使用 未完待续 三、权限 3. Linux权限管理 修改文件的拥有者和所属组 在上一节我们讲到如何更改文件的访问权限&#xff0c;那我们需要更改…

ubuntu strace命令

strace 是 Linux 系统中的一个调试工具&#xff0c;用于跟踪并记录系统调用&#xff08;system calls&#xff09;和信号&#xff08;signals&#xff09;。在 Ubuntu 中&#xff0c;strace 命令可以帮助开发者和系统管理员了解一个程序在运行时如何与操作系统内核进行交互&…

【教程】利用API接口添加本站同款【每日新闻早早报】-每天自动更新,不占用文章数量

本次分享的是给网站添加一个每日早报的文章&#xff0c;可以看到本站置顶上面还有一个日更的日报&#xff0c;这是利用ALAPI的接口完成的&#xff01;利用接口有利也有弊&#xff0c;因为每次用户访问网站的时候就会增加一次API接口请求&#xff0c;导致文章的请求会因为请求量…

Pytorch 笔记

执行下面这段代码后&#xff0c;为什么返回的是 2 &#xff1f; vector torch.tensor([7, 7]) vector.shape为什么返回的是 torch.Size([2])&#xff1f; 当你创建一个PyTorch张量时&#xff0c;它会记住张量中元素的数量和每个维度的大小。在你的代码中&#xff0c;torch.t…

智慧城市运维可视化:透视未来城市高效管理的新视窗

行业痛点 现代城市运维是一个复杂而庞大的系统&#xff0c;涉及到诸多方面&#xff0c;包括交通、环境、能源等等。然而&#xff0c;在城市运维中&#xff0c;存在着一些现实的痛点&#xff0c;给城市管理者带来了不小的压力和困扰&#xff1a; 1、交通拥堵 随着城市化进程的…

【算法】位运算算法——只出现一次的数字Ⅱ

题解&#xff1a;只出现一次的数字Ⅱ(位运算算法) 目录 1.题目2.题解&#xff1a;3.代码示例4.总结 1.题目 题目链接&#xff1a;LINK 要求&#xff1a;时间复杂度&#xff1a;O(N)&#xff0c;空间复杂度&#xff1a;O(1) 2.题解&#xff1a; 3.代码示例 class Solution {…

微信小程序毕业设计-校车购票系统项目开发实战(附源码+论文)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;微信小程序毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计…

操作系统 - 输入/输出(I/O)管理

输入/输出(I/O)管理 考纲内容 I/O管理基础 设备&#xff1a;设备的基本概念&#xff0c;设备的分类&#xff0c;I/O接口 I/O控制方式&#xff1a;轮询方式&#xff0c;中断方式&#xff0c;DMA方式 I/O软件层次结构&#xff1a;中断处理程序&#xff0c;驱动程序&#xff0c;…

go语言初识别(五)

本博客内容涉及到&#xff1a;切片 切片 1. 切片的概念 首先先对数组进行一下回顾&#xff1a; 数组定义完&#xff0c;长度是固定的&#xff0c;例如&#xff1a; var num [5]int [5]int{1,2,3,4,5}定义的num数组长度是5&#xff0c;表示只能存储5个整形数字&#xff0c…

七个很酷的GenAI LLM技术性面试问题

不同于互联网上随处可见的传统问题库&#xff0c;这些问题需要跳出常规思维。 大语言模型(LLM)在数据科学、生成式人工智能(GenAI)和人工智能领域越来越重要。这些复杂的算法提升了人类的技能&#xff0c;并在诸多行业中推动了效率和创新性的提升&#xff0c;成为企业保持竞争…

java8以上版本

java9及其以上版本 一、JDK17 LTS 常用新特性1、switch语句的增强2、字符串拼接3、判断类型instanceof自动类型转换4、密封类 关键字 sealed permits5、record类6、优化空指针异常7、ZGC垃圾收集器 一、JDK17 LTS 常用新特性 1、switch语句的增强 在 Java 17中&#xff0c;sw…

外卖系统源码开发全攻略:外卖小程序与后台管理系统的设计与实现

今天&#xff0c;小编将详细介绍外卖系统源码的开发全攻略&#xff0c;从需求分析到设计与实现&#xff0c;为开发者提供全面指导。 一、需求分析 1.用户需求 用户是外卖系统的核心&#xff0c;需满足以下基本需求&#xff1a; -浏览菜单并下单 -实时追踪订单 -多种支付方…

【从零开始学习RabbitMQ | 第二篇】如何确保MQ的可靠性和消费者可靠性

目录 前言&#xff1a; MQ可靠性&#xff1a; 数据持久化&#xff1a; Lazy Queue&#xff1a; 消费者可靠性&#xff1a; 消费者确认机制&#xff1a; 消费失败处理&#xff1a; MQ保证幂等性&#xff1a; 方法一&#xff1a; 总结&#xff1a; 前言&#xff1a; …

这款网站测试工具,炫酷且强大!【送源码】

随着互联网的普及和发展&#xff0c;Web 应用程序的数量也越来越多&#xff0c;各种网络问题也是层出不穷&#xff0c;因而监测这些 Web 应用程序的性能和可用性变得非常重要。 今天的文章&#xff0c;了不起和大家分享一款十分好用的的网站分析项目 - Web-Check。 项目简介 …

谷歌浏览器安装devtools工具

在浏览器中输入极简插件&#xff0c;然后打开如下的网页&#xff0c;在搜素框中输入vue 出现下图 点击推荐下载 &#xff08;地址&#xff1a;https://chrome.zzzmh.cn/info/nhdogjmejiglipccpnnnanhbledajbpd&#xff09; 打开谷歌浏览器如图 选择“扩展程序” 点开之后&…

互联网的利

在互联网没发明之前&#xff0c;人类说话要近距离的说&#xff0c;玩游戏要近距离的玩&#xff0c;十分麻烦。于是&#xff0c;互联网解决了这个问题。聊天可以在电脑上聊&#xff0c;玩游戏可以用游戏软件查找玩家来玩&#xff0c;实现了时时可聊&#xff0c;时时可玩的生活。…

Spring - Spring Cache 缓存注解这样用,实在是太香了!

作者最近在开发公司项目时使用到 Redis 缓存&#xff0c;并在翻看前人代码时&#xff0c;看到了一种关于 Cacheable 注解的自定义缓存有效期的解决方案&#xff0c;感觉比较实用&#xff0c;因此作者自己拓展完善了一番后分享给各位。 Spring 缓存常规配置 Spring Cache 框架给…

C++ 常量和变量

1 常量 具体把数据写出来 2,3&#xff0c;4&#xff1b;1.2 1.3;“Hello world!”,“C” cout<<2015 常量&#xff1a;不能改变的量。 字面常量&#xff08;字面量、直接常量&#xff09;:直接写出的数据。 符号常量&#xff1a;用符号表示数据&#xff0c;但它一旦确定…

mysqldump提示Using a password on the command line interface can be insecured的解决办法

mysql数据库备份一句话执行命令 mysqldump --all-databases -h127.0.0.1 -uroot -p123456 > allbackupfile.sql 提示如下提示 [rootyfvyy5b2on3knb8q opt]# mysqldump --all-databases -h127.0.0.1 > allbackupfile.sql mysqldump: Couldnt execute SELECT COLUMN_NA…

Modbus TCP转Profinet网关测试配置案例

本案例采用XD-ETHPN20网关做为Modbus TCP通信协议设备与Profinet通信协议设备连接的桥梁。Modbus TCP是一种基于TCP/IP协议的工业通信协议&#xff0c;而Profinet则是用于太网通信的协议。Modbus TCP转Profinet网关可实现这两种不同协议之间的数据交换和传输&#xff0c;极大地…