【数据结构】栈和队列、优先级队列、哈希表、数组
⭐️个人主页：@小羊⭐️所属专栏：算法很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~
目录
1、优先级队列
最后一块石头的重量
classSolution{public:intlastStoneWeight(vector<int>& stones){ priority_queue<int> pq;for(int e : stones) pq.push(e);while(pq.size()>1){int x = pq.top(); pq.pop();int y = pq.top(); pq.pop();if(x - y >0) pq.push(x - y);}return pq.empty()?0: pq.top();}};数据流中的第 K 大元素
classKthLargest{ priority_queue<int, vector<int>, greater<int>> pq;int _k;public:KthLargest(int k, vector<int>& nums){ _k = k;for(int e : nums){ pq.push(e);if(pq.size()> _k) pq.pop();}}intadd(int val){ pq.push(val);if(pq.size()> _k) pq.pop();return pq.top();}};前K个高频单词 *
classSolution{using psi = pair<string,int>;structcmp{booloperator()(const psi& p1,const psi& p2){if(p1.second == p2.second)return p1.first < p2.first;return p1.second > p2.second;}};public: vector<string>topKFrequent(vector<string>& words,int k){ vector<string>ret(k); unordered_map<string,int> hash;for(auto&str : words) hash[str]++; priority_queue<psi, vector<psi>, cmp> pq;for(auto&e : hash){ pq.push(e);if(pq.size()> k) pq.pop();}while(!pq.empty()){ ret[--k]= pq.top().first; pq.pop();}return ret;}};数据流的中位数 *
classMedianFinder{ priority_queue<int> left;// 大根堆 priority_queue<int, vector<int>, greater<int>> right;// 小根堆public:MedianFinder(){}voidaddNum(int num){if(left.size()== right.size()){if(left.size()&& num <= left.top()) left.push(num);else{ right.push(num); left.push(right.top()); right.pop();}}else{if(num >= left.top()) right.push(num);else{ left.push(num); right.push(left.top()); left.pop();}}}doublefindMedian(){if(left.size()== right.size())return(left.top()+ right.top())/2.0;return left.top();}};2、栈、队列
点击消除
这个题很容易想到用“栈”，但是创建一个stack最后还要转换成字符串，可以用string代替栈。string的接口很多且实用，常见的接口基本都有：
这个题比较坑的是它说如果字符串为空串则返回0，谁想到返回的是"0"，我试着返回0咋都过不去，最后吐了！都怪我太年轻了！
#include<iostream>usingnamespace std;intmain(){ string str, st; cin >> str;for(char ch : str){if(!st.empty()&& st.back()== ch){ st.pop_back();continue;} st.push_back(ch);} cout <<(st.empty()?"0": st);return0;}最小栈
定义一个主栈和辅助栈，主栈支持push、pop、top操作，辅助栈用于存相比于栈顶数据更小的或相等的数，主栈pop时如果栈顶数据和辅助栈栈顶数据相等，辅助栈也跟着pop，那么常数时间内检索到的最小元素就是辅助栈栈顶数据。
classMinStack{public:MinStack(){}voidpush(int val){ _st.push(val);if(_minst.empty()|| val <= _minst.top()){ _minst.push(val);}}voidpop(){if(_st.top()== _minst.top()){ _minst.pop();} _st.pop();}inttop(){return _st.top();}intgetMin(){return _minst.top();}private: stack<int> _st; stack<int> _minst;};栈的压入、弹出序列
定义一个栈用于压入数据，一个下标用于访问弹出序列。将压入序列依次放入栈中，期间如果某次压入的值和弹出序列的第一个数相等，那么就弹出刚压入的这个数，再++下标。
其中弹出栈中的数时要保证栈不为空，当访问完所有的压入数据后，检查栈是否为空，如果为空则返回真，否则返回假。
classSolution{public:boolIsPopOrder(vector<int>& pushV, vector<int>& popV){// write code hereint i =0;for(int e : pushV){ _st.push(e);while(!_st.empty()&& _st.top()== popV[i]){ _st.pop();++i;}}return _st.empty();}private: stack<int> _st;};用队列实现栈
栈的特点是后进先出，队列的特点是先进先出，用队列实现栈，必须有一个辅助队列在栈数据pop的时候用来导数据，将栈中需要pop的数据放到队列的队头pop。
也就是说用队列实现栈需要两个队列，一个存数据一个导数据，一个为空一个不为空，其中入栈时往不为空的队列中入数据，为空的队列只有一个作用，就是栈pop数据时导数据。
其中队列还有一个重要的特点，就是出队列不会改变数据的相对位置。
classMyStack{ queue<int> q;public:MyStack(){}voidpush(int x){int n = q.size(); q.push(x);while(n--){ q.push(q.front()); q.pop();}}intpop(){int res = q.front(); q.pop();return res;}inttop(){return q.front();}boolempty(){return q.empty();}};用栈实现队列
正是因为栈后进先出的特点，我们可以不用将导过来的数据再导回去，一个栈专门用来入数据，另一个栈专门用来出数据。 很显然这种方法更为简单。
classMyQueue{ stack<int> st1, st2;voidout(){while(st1.size()){ st2.push(st1.top()); st1.pop();}}public:MyQueue(){}voidpush(int x){ st1.push(x);}intpop(){if(st2.empty())out();int res = st2.top(); st2.pop();return res;}intpeek(){if(st2.empty())out();return st2.top();}boolempty(){return st1.empty()&& st2.empty();}};LCR 125. 图书整理 II
classCQueue{ stack<int> st1, st2;public:CQueue(){}voidappendTail(int value){ st1.push(value);}intdeleteHead(){if(st2.empty()){while(st1.size()){ st2.push(st1.top()); st1.pop();}}int res =-1;if(st2.size()){ res = st2.top(); st2.pop();}return res;}};设计循环队列
这里我们用数组来实现循环队列会相对简单一些，让head指向第一个位置，让tail指向最后一个元素的下一个位置。假设队列长度为K，我们开K + 1个空间，多开一个空间是为了方便区分队列为空和队列为满。也可以在结构体中多加一个变量用来计数。因为如果不多开一个空间，队列为空时是head == tail，队列为满时也是head == tail，无法区分。多开一个空间后，队列为满就是head == (tail + 1) % (k + 1).
当tail越界时我们对其模K+1，让tail指向下标为0的位置。
typedefstruct{int* a;int head;int tail;int k;} MyCircularQueue;boolmyCircularQueueIsEmpty(MyCircularQueue* obj){return obj->head == obj->tail;}boolmyCircularQueueIsFull(MyCircularQueue* obj){return obj->head ==(obj->tail +1)%(obj->k +1);} MyCircularQueue*myCircularQueueCreate(int k){ MyCircularQueue* pq =(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); pq->a =(int*)malloc(sizeof(int)*(k +1)); pq->head = pq->tail =0; pq->k = k;return pq;}boolmyCircularQueueEnQueue(MyCircularQueue* obj,int value){if(myCircularQueueIsFull(obj)){returnfalse;} obj->a[obj->tail++]= value; obj->tail %= obj->k +1;returntrue;}boolmyCircularQueueDeQueue(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj)){returnfalse;} obj->head++; obj->head %= obj->k +1;returntrue;}intmyCircularQueueFront(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj)){return-1;}return obj->a[obj->head];}intmyCircularQueueRear(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj)){return-1;}return obj->a[(obj->tail -1+ obj->k +1)%(obj->k +1)];}voidmyCircularQueueFree(MyCircularQueue* obj){free(obj->a);free(obj);}3、数组
删除有序数组中的重复项
示例：
可以用快慢指针，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标1，这是为了体现慢指针记录不重复的数据个数。
删除重复项和找不重复的项效果是一样的。
classSolution{public:intremoveDuplicates(vector<int>& nums){int slow =1;for(int fast =1; fast < nums.size();++fast){if(nums[fast]!= nums[fast -1]){ nums[slow++]= nums[fast];}}return slow;}};数组中出现次数超过一半的数字
方法一：候选法
- 时间复杂度：O(N)
- 空间复杂度：O(1)
初始化一个候选目标val和得票数count，遍历数组，如果当前的得票数count为0的话就选当前在数组中拿到的元素为目标，如果得票数count不为0，有和val相等的元素就给它投一票，遇到不相等的就减一票。 遍历完数组后val就是出现次数超过数组长度一般的数。
- 我们暂且将出现次数超过数组长度一半的数称作众数。数组中如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数
classSolution{public:intMoreThanHalfNum_Solution(vector<int>& numbers){int val =0;int count =0;for(int e : numbers){if(0== count){ val = e;++count;}else{ count = val == e ?++count :--count;}}return val;}};方法二：排序法
- 时间负责度：O(N*logN)
- 空间负责度：O(1)
既然众数的个数超过了数组长度的一半，那有序数组中间位置的数一定就是众数。
classSolution{public:intMoreThanHalfNum_Solution(vector<int>& numbers){sort(numbers.begin(), numbers.end());return numbers[numbers.size()/2];}};4、哈希表
两数之和
这又是多少人梦开始的地方~
方法一：万能两层for循环暴力枚举。
classSolution{public: vector<int>twoSum(vector<int>& nums,int target){for(int i =1; i < nums.size(); i++)for(int j =0; j < i; j++)if(nums[i]+ nums[j]== target)return{i, j};return{};}};方法二：哈希表快速查找。
classSolution{public: vector<int>twoSum(vector<int>& nums,int target){ unordered_map<int,int> hash;for(int i =0; i < nums.size(); i++){if(hash.count(target - nums[i]))return{i, hash[target - nums[i]]};else hash[nums[i]]= i;}return{};}};面试题 01.02. 判定是否互为字符重排
注意题目信息，仅存在小写字符。
方法一：排序然后比较。
classSolution{public:boolCheckPermutation(string s1, string s2){if(s1.size()!= s2.size())returnfalse;sort(s1.begin(), s1.end());sort(s2.begin(), s2.end());return s1 == s2;}};方法二：哈希表。
classSolution{public:boolCheckPermutation(string s1, string s2){if(s1.size()!= s2.size())returnfalse;int hash[26]={};for(auto e : s1) hash[e -'a']++;for(auto e : s2){if(hash[e -'a']) hash[e -'a']--;elsereturnfalse;}returntrue;}};存在重复元素
方法一：利用set的去重特点。
classSolution{public:boolcontainsDuplicate(vector<int>& nums){ set<int>s(nums.begin(), nums.end());return s.size()!= nums.size();}};方法二：排序后比较相邻元素是否相等。
classSolution{public:boolcontainsDuplicate(vector<int>& nums){sort(nums.begin(), nums.end());for(int i =1; i < nums.size(); i++)if(nums[i]== nums[i -1])returntrue;returnfalse;}};方法三：哈希表。
classSolution{public:boolcontainsDuplicate(vector<int>& nums){ unordered_set<int> hash;for(auto e : nums){if(hash.count(e))returntrue;else hash.insert(e);}returnfalse;}};存在重复元素 II
哈希表。
classSolution{public:boolcontainsNearbyDuplicate(vector<int>& nums,int k){ unordered_map<int,int> hash;for(int i =0; i < nums.size(); i++){if(hash.count(nums[i])&&abs(i - hash[nums[i]])<= k)returntrue;else hash[nums[i]]= i;}returnfalse;}};字母异位词分组
classSolution{public: vector<vector<string>>groupAnagrams(vector<string>& strs){ unordered_map<string, vector<string>> hash;for(auto& s : strs){ string tmp = s;sort(tmp.begin(), tmp.end()); hash[tmp].push_back(s);} vector<vector<string>> ret;for(auto&[a, b]: hash) ret.push_back(b);return ret;}};本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
