‍♂️个人主页进击的荆棘作者其它专栏《数据结构与算法》《算法》《C起始之路》相关题解1.最后一块石头的重量算法思路其实就是一个模拟的过程●每次从石堆中拿出最大的元素以及次大的元素然后将它们粉碎●若还有剩余就将剩余的石头继续放在原始的石堆里。重复上面的操作直到石堆里只剩下一个元素或没有元素因为所有的石头可能全部抵消了那么主要解决的问题是●如何顺利的拿出最大的石头以及次大的石头●并且将粉碎后的石头放入石堆中之后也能快速找到下一轮粉碎的最大石头和次大石头。这正好满足堆的特性●可以创建一个大根堆●然后将所有的石头放入大根堆中●每次拿出前两个堆顶元素粉碎一下若还有剩余就将剩余的石头继续放入堆中这样就能快速的模拟出这个过程。class Solution { public: int lastStoneWeight(vectorint stones) { priority_queueint heap; for(auto e:stones) heap.push(e); while(heap.size()2){ int y0,x0; yheap.top(); heap.pop(); xheap.top(); heap.pop(); if(yx) heap.push(y-x); } return heap.size()1?heap.top():0; } };2.数据流中的第 K 大元素算法思路Topk是堆的经典问题可以想到用堆来模拟。class KthLargest { //创建一个大小为k的小根堆 priority_queueint,vectorint,greaterint heap; int _k; public: KthLargest(int k, vectorint nums) { _kk; for(auto e:nums){ heap.push(e); if(heap.size()_k) heap.pop(); } } int add(int val) { heap.push(val); if(heap.size()_k) heap.pop(); return heap.top(); } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj new KthLargest(k, nums); * int param_1 obj-add(val); */3.前K个高频单词算法思路●稍微处理一下原数组a.需要知道每一个单词出现的频次因此可以先使用哈希表统计出每一个单词出现的频次b.然后在哈希表中选出前k大的单词为什么不再原数组中选因为原数组中存在重复的单词哈希表里没有重复单词并且还有每一个单词出现的频次●如何使用堆拿出前k大元素a.先定义一个自定义排序需要的是前k大因此需要一个小根堆。但是当两个字符串频次相同的时候需要的是字典序较小的因此是一个大根堆的属性在定义比较器的时候需要注意▢当两个字符串出现频次不同的时候需要的是基于频次比较的小根堆▢当两个字符串出现频次相同的时候需要的是基于字典序比较的大根堆b.定义好比较器之后依次将哈希表中的字符串插入到堆中维持堆中的元素不超过k个c.遍历完整个哈希表后堆中剩余的元素就是前k大的元素。class Solution { typedef pairstring,int PSI; struct Compare{ bool operator()(const PSI p1,const PSI p2){ if(p1.secondp2.second){//频次相同按照大根堆的方式存 return p1.firstp2.first; } return p1.secondp2.second; } }; public: vectorstring topKFrequent(vectorstring words, int k) { //1.统计每个单词的频次 unordered_mapstring,int hash; for(auto str:words) hash[str]; //2.创建一个大小为k的堆 priority_queuePSI,vectorPSI,Compare pq; //topk的主逻辑 for(auto psi:hash){ pq.push(psi); if(pq.size()k) pq.pop(); } //提取结果 vectorstring ret(k); for(int ik-1;i0;i--){ ret[i]pq.top().first; pq.pop(); } return ret; } };4.数据流的中位数算法思路利用两个堆这是一道关于【堆】这种数据结构的一个【经典应用】。可以将整个数组【按照大小】平分为两部分若不能平分就让较小部分的元素多一个较小部分称为左侧部分较大部分称为右侧部分●将左侧部分放入【大根堆】中然后将右侧部分放入【小根堆】中●这样就能在O1时间内拿到中间的一个数或两个数进而求平均数。若下图于是问题就变成了【如何将一个一个从数据流中过来的数据动态调整到大根堆或小根堆中并且保证两个堆的元素一致或左侧堆的元素比右侧堆的元素多一个】为了方便叙述将左侧的【大根堆】记为_left右侧的【小根堆】记为_right数据量中来的数据记为num。其实就是一个【分类讨论】的过程1.若左右堆的【数量相同】_left.size()_right.size()a.若两个堆都是空的直接将数据num放入到_left中b.若两个堆非空i.若元素要放入左侧也就是num_left.top()就直接放因为不会影响我们制定的规则ii.若放入右侧●可以先将num放入_right中●然后把_right的堆顶元素放入_left中2.若左右堆的数量【不相同】就是_left.size()_right.size():a.此时问题是num是否会放入_left中导致_left变得过多i.若num放入_right中若num_right.top()直接放ii.反之就是需要放入_left中●可以先将num放入_left中●然后把_left的堆顶元素放入_right中只有每一个新来的元素按照【上述规则】执行就能保证_left中放着整数数组排序后的【左半部分】_right中放着整个数组排序后的【右半部分】就能在O1的时间内求出平均数。class MedianFinder { //用两个堆来维护数据流的中位数 //大根堆 priority_queueint _left; //小根堆 priority_queueint,vectorint,greaterint _right; public: MedianFinder() { } void addNum(int num) { //1.当_left.size()_right.size() if(_left.size()_right.size()){ //若num小于等于_left堆顶元素或_left为空时 if(_left.empty()||_left.top()num){ _left.push(num); } else{ //先将num压入_right,再将多出的元素压到_left _right.push(num); _left.push(_right.top()); _right.pop(); } } //2.当_left.size()_right.size()即_left.size()_right.size()1 else{ //若num小于等于_left堆顶元素时 if(_left.top()num){ //此时_left比_right个数多2先将num压入_left再将多出的元素入_right _left.push(num); _right.push(_left.top()); _left.pop(); } else{ _right.push(num); } } } double findMedian() { if(_left.size()_right.size()) return (_left.top()_right.top())/2.0; else{ return _left.top(); } } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj new MedianFinder(); * obj-addNum(num); * double param_2 obj-findMedian(); */