算法学习打卡day41｜栈和队列：栈和队列相互实现、括号匹配、逆波兰表达式、滑动窗口最大值问题、求前 K 个高频元素

2023-11-08 01:36
文章标签 算法 实现 问题 学习 元素 打卡 队列 括号 表达式 波兰 最大值 窗口 匹配 滑动 高频 相互 day41 求前

本文主要是介绍算法学习打卡day41｜栈和队列：栈和队列相互实现、括号匹配、逆波兰表达式、滑动窗口最大值问题、求前 K 个高频元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

栈和队列相互实现

力扣题目链接：用栈实现队列、用队列实现栈
题目描述：

  • 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
    实现 MyQueue 类：
    void push(int x) 将元素 x 推到队列的末尾
    int pop() 从队列的开头移除并返回元素
    int peek() 返回队列开头的元素
    boolean empty() 如果队列为空，返回 true ；否则，返回 false
  • 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
    实现 MyStack 类：
    void push(int x) 将元素 x 压入栈顶。
    int pop() 移除并返回栈顶元素。
    int top() 返回栈顶元素。
    boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路：

  • 用栈实现队列的思路是遇到 push 就放到stk1里，如果遇到pop那么就把stk1的元素一次存到stk2里，然后从stk2的栈顶pop，就可以实现先入先出了。
  • 用队列实现栈的思路是一个队列que1用来存储元素，用另外一个队列que2来备份元素，但要pop元素时，就把que1的元素都存到que2的元素里，然后把que1最后一个元素删掉就行。

代码实现：

  • 用栈实现队列
class MyQueue {
public:MyQueue() {}void push(int x) {stack1.push(x);}int pop() {int x = 0;if (!stack2.empty()) {x = stack2.top();stack2.pop();return x;}while (!stack1.empty()) {x = stack1.top();stack1.pop();stack2.push(x);}x = stack2.top();stack2.pop();return x;}int peek() {int result = this->pop();//降低代码耦合度stack2.push(result);return result;}bool empty() {return stack1.empty() && stack2.empty();}
private:stack<int> stack1; //用来压栈stack<int> stack2;  //从stack1出占，压入stack2就是栈顶元素了
};
  • 用队列实现栈
class MyStack {
public:queue<int> que1;MyStack() {}void push(int x) {que1.push(x);}int pop() {int size = que1.size();int x = 0;while (--size) {x = que1.front();que1.pop();que1.push(x);}int result = que1.front();que1.pop();return result;}int top() {int result = pop();que1.push(result);return result;}bool empty() {return que1.empty();}};

括号匹配

力扣题目链接

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

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

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

思路：

  • 这道题因为所有的元素都是括号，所以，我们直接把符号压入栈中，然后遇到右括号就和栈顶元素比较，如果匹配不到（不匹配或栈为空都是无效）那么肯定是无效的。当字符串遍历完后如果栈非空，那么字符串也是无效的。
  • 另外奇数一定是无法匹配的，可以在开头判断一下。

代码实现：

bool isValid(string s) {if (s.size() % 2)   return false;   //奇数一定无法匹配stack<char> stk;for (char& i : s) {if (i == '{' || i == '(' || i == '[') {stk.push(i);//左括号入栈} else {if (stk.empty())    return false;//如果是右括号，但是此时栈空，说明右边多了直接returnif (i == ')') {if (stk.top() != '(')   return false;//匹配不到就return} else if (i == ']') {if (stk.top() != '[')   return false;} else {if (stk.top() != '{')   return false;}stk.pop();//匹配到了，别忘了pop}}return stk.empty();//不用单独if判断了，直接在这里判断就行}
  • 代码实现进行了一定的优化，遇到左括号可以直接存对应右括号，那么遇到右括号可以直接进行比较是否相同了。
bool isValid(string s) {if (s.size() % 2)   return false;   //奇数一定无法匹配stack<char> stk;for (char& i : s) {if (i == '{')   stk.push('}');//换个思路，存右括号，那么遇到右括号直接比较是否相等就行了else if (i == '(') stk.push(')');else if (i == '[')  stk.push(']');else if (stk.empty() || stk.top() != i) return false;//右边多了或者没匹配到else stk.pop();//匹配到了，别忘了pop}return stk.empty();//不用单独if判断了，直接在这里判断就行}
  • 应用场景：
    • 编译器在词法分析的过程中处理括号、花括号等这个符号的逻辑，就是使用了栈来进行匹配的。
    • linux的cd命令也涉及到栈对路径处理。
    • 函数调用时的调用栈。
    • 递归也会借助栈来实现，每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中。

1047. 删除字符串中的所有相邻重复项

力扣题目链接
题目描述：
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：
输入：“abbaca”
输出：“ca”
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

思路：

  • 这道题有两种写法，栈的实现思路比较简单。
  • 借助栈：如果栈为空或者当前元素和栈顶元素不相等，就入栈，如果相等就把栈顶元素删除，遍历结束后就得到了最终结果。注意：字符串和数组是天然的栈！！！
  • 双指针法： 双指针法就是原地移除元素了，定义一个left和right指针，别激动和普通的删除重复项还不一样，是慢指针和快指针一起走，而且不是right和left比较，而是right和left-1去比较。！ 而一般双指针法是left在从0走，right从1走，
    • 只有当慢指针的前一个元素和当前值相等时再退一格，只有这样才能保证奇数时留一个，偶数时都干掉（奇数时和前一个元素不一样了）。
    • 然后赋值时不是++left而是left++了，因为如果是偶数，那就是回退，然后偶数序列右边界下一个元素一定和左边界前一个不相等，这时就left就直接覆盖都给删了，如果是奇数那在右边界的时候已经和左边界前一个元素不相等了，可以留一个

代码实现：

string removeDuplicates(string s) {string result;for (char& i : s) {if (result.empty() || i != result.back()) {result.push_back(i);continue;}  result.pop_back();}return result;}
  • 双指针法
string removeDuplicates(string s) {int left = 0, right = 0;for (right; right < s.size(); ++right) {if (left > 0 && s[left - 1] == s[right]) {left--;} else {s[left++] = s[right];}}s.resize(left);return s;}

逆波兰表达式

力扣题目链接
题目描述：
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。

注意：
有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

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

思路：

  • 这个题很简单，遇到加减乘除就从栈里取两个元素，然后将计算结果再放入栈里即可，没有遇到运算符就把其他元素放入栈。

代码实现：

int evalRPN(vector<string>& tokens) {stack<int> stk;int num1, num2;for (string& s : tokens) {if (s == "+" || s == "-" || s == "*" || s == "/") {num1 = stk.top();stk.pop();num2 = stk.top();stk.pop();if (s == "+")   stk.push(num2 + num1);if (s == "-")   stk.push(num2 - num1);if (s == "*")   stk.push(num2 * num1);if (s == "/")   stk.push(num2 / num1);} else {stk.push(stoi(s));}}return stk.top();}

滑动窗口最大值问题

力扣题目链接
题目描述：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1:
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
在这里插入图片描述

思路：

  • 这道题涉及到单调队列的应用，需要自己实现一个单调队列，什么是单调队列？ 即让队列里的元素单调递增或者递减。
  • 我们这道题需要实现一个单调递减的队列，最大值在队列头部，这里采用deque实现，C++底层默认也是deque实现的，主要涉及到push和pop两个操作：
    • push：push的时候如果需要push的值比栈尾大时，就把尾部的值删掉（如果不用删除的情况，就存到另一个栈里，push后再放进去）直到push的value比尾部值小停止删除。
    • pop：pop的话，需要和队列的front元素比较，如果相等就pop（），否则不需要进行操作，因为最大值没有发生改变，不需要执行pop操作（其实在push的时候已经给它干掉了）。
    • front：这个就是返回队列开始的元素，记录窗口最大值。

代码实现:

class Solution {
public://定义单调队列class MyQueue {public:void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}int front() {return que.front();}private:deque<int> que;};vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue my_que;//先放入k - 1个元素for (int i = 0; i < k - 1; ++i) {my_que.push(nums[i]);}int i = k - 1;vector<int> results;//依次取最大值while (i < nums.size()) {my_que.push(nums[i]);results.push_back(my_que.front());my_que.pop(nums[i - k + 1]);i++; }return results;}
};

求前 K 个高频元素

力扣题目链接
题目描述：
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]

思路：

  • 一般遇到前k个或者k个元素合并之类的都可以试着用优先级队列来解题，本题也是使用优先级队列。
  • 分为以下三步：
    1. 首先先统计数组所有元素出现的次数，使用哈希map
    2. 建立小根堆，一直维持k个最大元素即可，既然是要求高频元素为啥不用大根堆？ 因为使用大根堆需要比较map中的所有元素，而我们本题只需要维持最大的k个元素即可，每次利用小根堆把最小的元素干掉。
    3. 输出优先级队列的元素。
  • 另外本体需要自定义优先级队列的cmp，由于第三个参数是个类参数，所以我们需要自己定义一个类。
  • 还有为什么左大于右就会建立小顶堆，而不是建立大顶堆?

例如我们在写快排的cmp函数的时候，return left>right 就是从大到小，return left<right 就是从小到大，优先级队列的定义正好反过来了，可能和源码实现有关。

代码实现：

class mycomparison {public:bool operator () (const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;}}; vector<int> topKFrequent(vector<int>& nums, int k) {//统计次数unordered_map<int, int> maps;for (int& i : nums) {maps[i]++;}//建堆priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;for (auto& i : maps) {pri_que.push(i);if (pri_que.size() > k) {pri_que.pop();}}//输出结果vector<int> results;while (k--) {results.push_back(pri_que.top().first);pri_que.pop();}return results;}

这篇关于算法学习打卡day41｜栈和队列：栈和队列相互实现、括号匹配、逆波兰表达式、滑动窗口最大值问题、求前 K 个高频元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/367155。

相关文章

PostgreSQL中rank()窗口函数实用指南与示例

PostgreSQL中rank()窗口函数实用指南与示例

《PostgreSQL中rank()窗口函数实用指南与示例》在数据分析和数据库管理中,经常需要对数据进行排名操作,PostgreSQL提供了强大的窗口函数rank(),可以方便地对结果集中的行进行排名... 目录一、rank()函数简介二、基础示例：部门内员工薪资排名示例数据排名查询三、高级应用示例1. 每
阅读更多...
Linux下删除乱码文件和目录的实现方式

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》：本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录
阅读更多...
SpringBoot+EasyExcel实现自定义复杂样式导入导出

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定，动态列2、动态下拉3、自定义锁定行/列，添加密码4、合并
阅读更多...
mybatis执行insert返回id实现详解

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID：1. ​​useGeneratedKeys+keyProperty（推
阅读更多...
Spring Boot集成Druid实现数据源管理与监控的详细步骤

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控
阅读更多...
Linux在线解压jar包的实现方式

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》：本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
Qt使用QSqlDatabase连接MySQL实现增删改查功能

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构
阅读更多...
基于Python实现一个图片拆分工具

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片，默认是输出到项目文件夹中，可以自己选择其他的文件夹，选择需要拆分的行数和列数，可以通过
阅读更多...
Python中将嵌套列表扁平化的多种实现方法

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表（即列表中包含列表）转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2