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

本文主要是介绍算法打卡 Day13(栈与队列)-滑动窗口最大值 + 前 K 个高频元素 + 总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 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,其内存分布不连续。

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

这篇关于算法打卡 Day13(栈与队列)-滑动窗口最大值 + 前 K 个高频元素 + 总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1002530

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

Windows Docker端口占用错误及解决方案总结

《WindowsDocker端口占用错误及解决方案总结》在Windows环境下使用Docker容器时,端口占用错误是开发和运维中常见且棘手的问题,本文将深入剖析该问题的成因,介绍如何通过查看端口分配... 目录引言Windows docker 端口占用错误及解决方案汇总端口冲突形成原因解析诊断当前端口情况解

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.