前言今天学习了优先队列和哈希的相关知识并解决了以下题目,大部分题目都不难只有牛客上Masha与老鼠这道题相当难费了我九牛二虎之力也看不到废了废了题目来源优先队列力扣506703215264acwing106牛客NC14847哈希力扣217389 3139详细解答:优先队列:1.506. 相对名次法一排序哈希映射这道题主要是对成绩排序不改变输入的顺序前三名对应一个称号其他的依次输出名次即可class Solution { public: vectorstring findRelativeRanks(vectorint score) { int nscore.size(); vectorintsortscorescore; sort(sortscore.begin(),sortscore.end());//成绩从低到高排序 mapint,intmp; int t1;//名次从1到最后 for(int in-1;i0;i--){ mp[sortscore[i]]t;//给每个人的成绩附上排名 t; } vectorstringans;//储存结果 for(int s:score){ int amp[s]; if(a1)ans.push_back(Gold Medal); else if(a2)ans.push_back(Silver Medal); else if(a3)ans.push_back(Bronze Medal); else ans.push_back(to_string(a));//除前三名之外后面只输出名次即可 } return ans; } };法二优先队列priority_queuepairint,int默认是大根堆优先把第一个元素更大的放在顶堆顶永远是当前剩余最大元素解题步骤把所有 (分数,下标) 扔进大根堆依次弹出堆内最大值按弹出顺序分配名次 1,2,3,4…根据下标直接把结果填入答案数组对应位置class Solution { public: vectorstring findRelativeRanks(vectorint score) { int nscore.size(); priority_queuepairint,inthp;//pair优先把大元素放在堆顶 for(int i0;in;i){ hp.push({score[i],i});//储存分数和原数组下标 } int rank1;//分配名次从第一名开始 vectorstringans(n); while(!hp.empty()){ auto[val,idx]hp.top();//取出堆顶val分数idx原始下标 hp.pop(); if(rank1)ans[idx]Gold Medal; else if(rank2)ans[idx]Silver Medal; else if(rank3)ans[idx]Bronze Medal; else ans[idx]to_string(rank); rank;//下一个人 } return ans; } };2.703. 数据流中的第 K 大元素priority_queueint,vector,greater是小根堆堆顶是堆内所有元素的最小值这道题是找排过序之后的第k大元素同时伴有数据的插入我们可以利用小根堆堆内只保存最大的k个元素堆顶是堆内最小元素即第k个最大元素class KthLargest { int k; priority_queueint,vectorint,greaterinthp;// 小根优先队列只保存最大的k个数 public: KthLargest(int k, vectorint nums) { this-kk; // 初始化堆只保留k个最大元素 for(int num:nums){ hp.push(num); if(hp.size()k)hp.pop(); } } int add(int val) { hp.push(val); if(hp.size()k)hp.pop();// 堆顶就是数据流中第k大元素 return hp.top();// 堆顶就是数据流中第k大元素 } };3.215. 数组中的第K个最大元素这道题与上一道题同类型更简单没有什么可说的class Solution { public: int findKthLargest(vectorint nums, int k) { priority_queueint,vectorint,greaterinthp; for(int num:nums){ hp.push(num); if(hp.size()k)hp.pop(); } return hp.top(); } };4.264. 丑数 II法一小根堆哈希小根堆每次弹出堆顶就是当前最小丑数哈希集合 seen去重避免像 6(2×3 和3×2) 重复入堆取出最小丑数 curr 分别 ×2、×3、×5新数字存入堆循环执行 n 次第 n 次弹出的值就是答案class Solution { public: int nthUglyNumber(int n) { vectorint factors {2, 3, 5}; unordered_setlong long s; priority_queuelong long, vectorlong long, greaterlong long hp; s.insert(1); hp.push(1); int a 0; for (int i 0; i n; i) { long long curr hp.top(); hp.pop(); a (int)curr; for (int factor : factors) { long long next curr * factor; if (!s.count(next)) { s.insert(next); hp.push(next); } } } return a; } };法二三指针动态规划所有丑数一定是 前面某个丑数 ×2 / ×3 / ×5 ​三个指针 a,b,c 分别负责乘2、乘3、乘5每次选出三个乘积里最小的数存入数组作为下一个丑数 ​重点独立三个if不能写else if 遇到重复值比如62×33×2两个指针需要同时右移防止产生重复丑数class Solution { public: int nthUglyNumber(int n) { // a,b,c 三个指针分别指向要 ×2、×3、×5 的丑数位置 int a 0, b 0, c 0; // f[i]代表第 i1 个丑数 int f[2000]; f[0] 1; // 第一个丑数是1 for(int i 1; i n; i) { // 生成三个候选丑数 int n2 f[a] * 2; int n3 f[b] * 3; int n5 f[c] * 5; // 选取最小值作为下一个丑数 f[i] min({n2, n3, n5}); // 谁被选中对应的指针向后移动 if(f[i] n2) a; if(f[i] n3) b; if(f[i] n5) c; } // f[n-1] 就是第n个丑数 return f[n-1]; } };5.106.动态中位数这道题是求中位数当读入的元素个数是奇数是要求出当前元素中的中位数可以利用大根堆小根堆实现思路分析大根堆储存前半段较小的数栈顶是前半部分最大值小根堆储存后半段较大的数栈顶是后半部分最小值每次读入新数时每次读入新数时​ 如果新数 ≤ 大根堆堆顶加入大根堆否则加入小根堆​ 调整两个堆的大小保持大根堆的元素个数比小根堆多 1或相等​ 当已读入的数的个数为奇数时大根堆的堆顶就是当前序列的中位数记录下来#includebits/stdc.h using namespace std; #define endl \n void solve(){ int n,m; cinnm; priority_queueintmaxhp;//大根堆左半部分 priority_queueint,vectorint,greaterintminhp;//小根堆右边部分 vectorintres; for(int i1;im;i){ int x; cinx; if(maxhp.empty()||xmaxhp.top()) maxhp.push(x); else minhp.push(x); //平衡两个堆 if(maxhp.size()minhp.size()1){ minhp.push(maxhp.top()); maxhp.pop(); } else if(maxhp.size()minhp.size()){ maxhp.push(minhp.top()); minhp.pop(); } //当元素个数时奇数时记录中位数 if(i%21){ res.push_back(maxhp.top()); } } coutn res.size()endl; for(int i0;ires.size();i){ if(i!0i%100)coutendl; if(i%10!0)cout ; coutres[i]; } coutendl; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int p; cinp; while(p--)solve(); return 0; }6.NC14847还没弄懂先省略吧…#includebits/stdc.h #define int long long using namespace std; typedef pairint,int PII; const int N 2000006; PII arr[N]; priority_queueint,vectorint,greaterint p1; priority_queuePII,vectorPII,greaterPII p2; signed main () { int n,m; cin n m; int sum n; for(int i 1; i n; i) { cinarr[i].first; } for(int i 1; i m; i) { n; cinarr[n].firstarr[n].second; sum - arr[n].second; } if(sum 0) { cout-1endl; return 0; } sort(arr1,arr1n); int res 0; for(int i 1; i n; i) { int x arr[i].first; if(arr[i].second) { while(!p1.empty() arr[i].second x p1.top() 0) { int a x p1.top(); res a; p1.pop(); arr[i].second--; p2.push({-a-x,0}); } if(arr[i].second) { arr[i].second--; p2.push({-x,i}); } } else{ int a 1ll32; if(!p2.empty()) { int b p2.top().second; a x p2.top().first; p2.pop(); if(arr[b].second) { arr[b].second--; p2.push({-arr[b].first,b}); } } res a; p1.push(-a-x); } } cout res endl; return 0; }哈希1.[217. 存在重复元素](ht3. 无重复字符的最长子串tps://leetcode.cn/problems/contains-duplicate/)有元素重复输出true,没有输出false法一:哈希class Solution { public: bool containsDuplicate(vectorint nums) { unordered_setintst; for(int x:nums){ if(st.count(x))return true;//说明集合里已经存在x,有重复返回true st.insert(x); } return false; } };法二排序排序后遍历当有相邻元素相同时即找到class Solution { public: bool containsDuplicate(vectorint nums) { sort(nums.begin(), nums.end()); for(int i 1; i nums.size(); i) { if(nums[i] nums[i-1]) return true; } return false; } };2.389. 找不同题意两个字符串s和t;t字符串是由s字符串随机在一个位置增加一个字符所得找出这个字符class Solution { public: char findTheDifference(string s, string t) { mapchar,intst; for(char c:s){ //统计s中每个字符出现的次数 st[c]; } for(char m:t){ //当前字符用完了或不存在就是答案 if(st[m]0) return m; st[m]--; } return ;//满足编译要求 } };3.3. 无重复字符的最长子串这道题是找最长无重复字符的子串长度采用滑动窗口双指针哈希解题思路l 窗口左边界固定不动只有出现重复字符才右移r逐个遍历字符串作为窗口右边界不断右移当 s[r] 已经在集合中说明窗口内出现重复删除 left 位置字符left直到重复字符被移出窗口窗口 [l,r] 永远是一段无重复字符的子串长度 r-l1 记录窗口的最大长度即可。class Solution { public: int lengthOfLongestSubstring(string s) { setcharst; int mx0; int l0; for(int r0;rs.size();r){ while(st.count(s[r])){ st.erase(s[l]);//从左删除直到无重复为止 l; } st.insert(s[r]); mxmax(mx,r-l1);//更新最大长度 } return mx; } };4.139. 单词拆分看单词能不能由所给的字符串拼接而成解题思路哈希作用把所有单词放进 unordered_set h.count(字符串) 可以判断一段子串是不是字典里的单词。DP状态dp[i] 字符串 前 i 位 s[0] ~ s[i-1] 可以被拆分。dp[0]true 空字符串合法是推导起点。转移逻辑对每个结尾位置 i 尝试所有分割点 j 前半段 0~j-1 合法 dp[j]true后半段 j~i-1 是字典单词哈希查询满足两条 → dp[i]trueclass Solution { public: bool wordBreak(string s, vectorstring wordDict) { unordered_setstringh; for(string str:wordDict){ // 哈希集合存储字典快速查询单词是否存在 h.insert(str); } int ls.size(); // dp[i]s 的前 i 个字符能否拆分成功 vectorbooldp(l1,false); dp[0]true;//空串作为初始条件 for(int i1;il;i){ //枚举分割点j for(int j0;ji;j){ // 前j个字符合法 [j,i]这段子串在哈希集合中 if(dp[j]h.count(s.substr(j,i-j))){ dp[i]true; break; } } } return dp[l]; } };