算法学习打卡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。

相关文章

使用Java将DOCX文档解析为Markdown文档的代码实现

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown（MD）因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析
阅读更多...
Qt中QGroupBox控件的实现

Qt中QGroupBox控件的实现

《Qt中QGroupBox控件的实现》QGroupBox是Qt框架中一个非常有用的控件,它主要用于组织和管理一组相关的控件,本文主要介绍了Qt中QGroupBox控件的实现,具有一定的参考价值,感兴趣... 目录引言一、基本属性二、常用方法2.1 构造函数 2.2 设置标题2.3 设置复选框模式2.4 是否
阅读更多...
C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
springboot整合阿里云百炼DeepSeek实现sse流式打印的操作方法

springboot整合阿里云百炼DeepSeek实现sse流式打印的操作方法

《springboot整合阿里云百炼DeepSeek实现sse流式打印的操作方法》：本文主要介绍springboot整合阿里云百炼DeepSeek实现sse流式打印,本文给大家介绍的非常详细,对大... 目录1.开通阿里云百炼,获取到key2.新建SpringBoot项目3.工具类4.启动类5.测试类6.测
阅读更多...
pytorch自动求梯度autograd的实现

pytorch自动求梯度autograd的实现

《pytorch自动求梯度autograd的实现》autograd是一个自动微分引擎,它可以自动计算张量的梯度,本文主要介绍了pytorch自动求梯度autograd的实现,具有一定的参考价值,感兴趣... autograd是pytorch构建神经网络的核心。在 PyTorch 中，结合以下代码例子，当你
阅读更多...
如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

《如何解决idea的Module:‘:app‘platform‘android-32‘notfound.问题》：本文主要介绍如何解决idea的Module:‘:app‘platform‘andr... 目录idea的Module:‘:app‘pwww.chinasem.cnlatform‘android-32
阅读更多...
SpringBoot集成Milvus实现数据增删改查功能

SpringBoot集成Milvus实现数据增删改查功能

《SpringBoot集成Milvus实现数据增删改查功能》milvus支持的语言比较多,支持python,Java,Go,node等开发语言,本文主要介绍如何使用Java语言,采用springboo... 目录1、Milvus基本概念2、添加maven依赖3、配置yml文件4、创建MilvusClient
阅读更多...
JS+HTML实现在线图片水印添加工具

JS+HTML实现在线图片水印添加工具

《JS+HTML实现在线图片水印添加工具》在社交媒体和内容创作日益频繁的今天,如何保护原创内容、展示品牌身份成了一个不得不面对的问题,本文将实现一个完全基于HTML+CSS构建的现代化图片水印在线工具... 目录概述功能亮点使用方法技术解析延伸思考运行效果项目源码下载总结概述在社交媒体和内容创作日益频繁的
阅读更多...
kali linux 无法登录root的问题及解决方法

kali linux 无法登录root的问题及解决方法

《kalilinux无法登录root的问题及解决方法》：本文主要介绍kalilinux无法登录root的问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录kali linux 无法登录root1、问题描述1.1、本地登录root1.2、ssh远程登录root2、
阅读更多...
SpringBoot应用中出现的Full GC问题的场景与解决

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2