1047. 删除字符串中的所有相邻重复项
题目描述
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca" 输出："ca"
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
思路分析
栈的使用
参考代码
string removeDuplicates(string s) { string res; stack<char> st; for(char ch : s){ if(!st.empty()&&st.top()==ch){//栈不为空,别切栈顶元素和遍历元素相当,则弹出栈 st.pop(); }else{//栈为空/栈顶元素和遍历元素 st.push(ch); } } while(!st.empty()){ res+=st.top(); st.pop(); } reverse(res.begin(),res.end()); return res; }
补充:直接拿字符串作为栈
string removeDuplicates(string s) { string res; for(char ch : s){ if(res.empty()|| res.back()!= ch){ res.push_back(ch); }else{ res.pop_back(); } } return res; }
STL中字符串常用方法总结
begin(),end()
size(),length()
resize()
empty()
back() :获取最后一个字符
front():获取第一个字符
push_back() 增加一个字符到末尾
pop_back() 删除最后一个字符
substr(pos,size)
150. 逆波兰表达式求值
题目描述
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"] 输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"] 输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] 输出：22
解释：
该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
逆波兰表达式介绍：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
思路分析
栈的使用
如果是数字则压入栈
如果是运算符,则从栈中弹出两个数字进行运算,运算结果再重新压入栈中
当数组遍历完毕后,返回栈中的最后一个数字即是结果.
参考代码
int evalRPN(vector<string>& tokens) { stack<int> st; for(int i = 0;i < tokens.size();i++) { if(tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*" || tokens[i]=="/"){ int num1 = st.top(); st.pop(); int num2 = st.top(); st.pop(); if(tokens[i]=="+") { st.push(num1+num2); } else if(tokens[i]=="-") { st.push(num1-num2); } else if(tokens[i]=="*") { st.push(num1*num2); } else { st.push(num1/num2); } }else{ st.push(stoi(tokens[i])); } } return st.top(); }
239. 滑动窗口最大值
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]
解释：
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1 输出：[1]
示例 3：
输入：nums = [1,-1], k = 1 输出：[1,-1]
示例 4：
输入：nums = [9,11], k = 2 输出：[11]
示例 5：
输入：nums = [4,-2], k = 2 输出：[4]
思路分析
单调队列的使用
这道题不复杂，难点在于如何在 O(1) 时间算出每个「窗口」中的最大值，使得整个算法在线性时间完成。就需要「单调队列」这种特殊的数据结构来辅助了。
C++普通队列:
class Queue { void push(int n); // 或 enqueue，在队尾加入元素 n void pop(); // 或 dequeue，删除队头元素 }
单调队列:
class MonotonicQueue { // 在队尾添加元素 n void push(int n); // 返回当前队列中的最大值 int max(); // 队头元素如果是 n，删除它 void pop(int n); }
实现单调队列数据结构
单调队列的 push 方法依然在队尾添加元素，但是要把前面比新元素小的元素都删掉; 要用到双端队列:deque
完整代码:
class MonotonicQueue { private: deque<int> Q; public: void push(int n) { while(!Q.empty() && Q.back() < n) { //把 < n的元素都压扁 Q.pop_back();//从后面弹出.. } Q.push_back(n); } int max() { return Q.front();//最大的便是对头元素 } void pop(int n) { if(!Q.empty()&& Q.front()==n) { //如果窗口移除的元素= 最大值, 则单调队列中删除该元素. Q.pop_front();//从前面弹出. } } };
功能演示:
**注:**关于单调栈的原理请看:LeetCode刷题day31
参考代码
#include<bits/stdc++.h> using namespace std; class MyQueue { //单调队列 public: deque<int> que;//使用deque来实现单调队列 //弹出元素,比较当前队列头部的值和窗口的最左边的值(即将移除窗口) 是否相等,如果相等则弹出. void pop(int value) { if(!que.empty()&& value == que.front()) { que.pop_front(); } } //push压入元素 (保证que中元素是从大到小排列的) //先将 <value的元素弹出,然后再压入value.这样que里面的顺序就是从小到大了 void push(int value) { while(!que.empty() && value > que.back()){ que.pop_back(); } que.push_back(value); } //查询当前队列里的最大值,直接返回队头元素 就OK了 int front() { return que.front(); } }; vector<int> maxSlidingWindow(vector<int>& nums, int k) { MyQueue que; vector<int> result; for(int i = 0;i < k;i++){//将前k个元素加入到单调队列中 que.push(nums[i]); } result.push_back(que.front());//记录前k个元素的 最大值 for(int i = k; i < nums.size(); i++) { que.pop(nums[i-k]);//弹出窗口最左边元素 注意这里是弹出之前的窗口最左边值所以不用+1了哦. que.push(nums[i]);//压入窗口右边的新元素 result.push_back(que.front()) ;//将当前窗口的最大值加入结果集 } return result; }
347. 前 K 个高频元素
题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
输入: nums = [1], k = 1 输出: [1]
思路分析
这个题考察内容:
要统计元素出现频率==>使用map
对频率排序=>使用优先队列
找出前K个高频元素
priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
什么是堆呢?
堆是一颗完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。
如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
所以我们可以用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。(当然如果是大根堆,那么弹出前k个元素就行.)
参考代码
//定义优先队列的排序规则(优先队列和常规的排序规则(如快排)正好相反 class mycomparison { public: bool operator(const pair<int,int>& l,const pair<int,int>& r) { return l.second > r.second; } }; class Solution { public: //小顶堆 vector<int> topKFrequent(vector<int>& nums, int k) { //要统计元素出现的频率 unordered_map<int,int> map; for(int i = 0;i < nums.size();i++){ map[nums[i]]++; } //对频率排序 //定义一个小根堆,大小为k priority_queue<pair<int,int>,vector<pair<int,int>>, mycomparison> Q; //用固定大小为k的小根堆,扫到所有频率的数值 for(unordered_map<int,int>::iterator it = map.begin(); it!= map.end(); it++){ Q.push(*it); if(Q.size()>k){ Q.pop(); } } //找出前k个高频元素,因为小根堆先弹出的是最小的. vector<int> res(k); for(int i = k-1; i>=0;i--){ res[i] = Q.top().first; Q.pop(); } return res; } };
注:pair可看做map的一个子元素模板,可以对map进行赋值,初始化等操作.
总结
OK，今天关于栈和队列算法整理就到这里的，希望本篇文章能够帮助到大家，同时也希望大家看后能学有所获！！！
好了，我们下期见~
