6031. 找出数组中的所有 K 近邻下标
题意
给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。K 近邻下标 是 nums 中的一个下标 i ，并满足至少存在一个下标 j 使得 |i - j| <= k 且 nums[j] == key 。以列表形式返回按 递增顺序 排序的所有 K 近邻下标。
1 < = n u m s . l e n g t h < = 1000
思路
数组大小为1000，考虑O ( n 2 )的算法。
先枚举i，再枚举j，枚举j的时候可以缩小范围，只枚举i前的k个和i后的k 个，再判断j的值是不是等于目标值。如果等于的话说明i是K近相邻下标，将i放入答案里然后要及时b r e a k，不然会重复放。
代码
class Solution { public: vector<int> findKDistantIndices(vector<int>& nums, int key, int k) { vector<int>ans; map<int,int>mp; int n=nums.size(); for(int i=0;i<nums.size();i++){ for(int j=max(0,i-k);j<=min(n-1,i+k);j++){ if(abs(i-j)<=k&&nums[j]==key){ ans.push_back(i);break; } } } return ans; } };
5203. 统计可以提取的工件
题意
思路
数据范围看似很大，实际上每个工件最多只覆盖4个单元格，所以考虑先将dig中的元素存储到map里，这样可以O(1)的查出某个坐标是否被挖掘。然后遍历工件，对于第i个工件，遍历覆盖的每一个坐标，利用map看该坐标是否被覆盖。
时间复杂度是O ( a r t i f a c t s . l e n g t h )
代码
class Solution { public: int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) { int arti_siz=artifacts.size(); int dig_siz=dig.size(); map<pair<int,int>,int>mp; for(auto it:dig){ pair<int,int>t={it[0],it[1]}; mp[t]=1; } int ans=0; for(auto it:artifacts){ int x1=it[0],y1=it[1],x2=it[2],y2=it[3]; bool ff=1; for(int i=x1;i<=x2&&ff;i++){ for(int j=y1;j<=y2&&ff;j++){ pair<int,int>t={i,j}; if(mp.find(t)==mp.end()){ ff=0; } } } if(ff) ans++; } return ans; } };
5227. K 次操作后最大化顶端元素
题意
1<=nums.length<=105
思路
考虑特殊情况，如果n = = 1，那么要考虑k kk的奇偶性。如果k是奇数的话，k次操作后栈一定为空，答案为-1；否则，可以将第一个元素入栈，答案就是第一个元素。
如果最大值的下标在[0,k-2]，都可以取到最大值。可以不断地删除添加某个数，来消耗次数。
如果最大值的下标为k-1，最后一个操作只能删除最大值，无法将最大值放于栈顶，这时候的答案为前面的最大值。
如果最大值下标为k，可以删除前k个元素，最大值为栈顶。
也就是从0到k枚举一遍，除了k-1都可以取到，取这些数的最大值就可以了。
注意要跟n取min，防止数组越界。
代码
class Solution { public: int maximumTop(vector<int>& nums, int k) { int n=nums.size(); if(n==1){ if(k%2) return -1; else return nums[0]; } int ans=-1; //[99,95,68,24,18] 69 =>99 for(int i=0;i<min(n,k+1);i++){ if(i!=k-1) ans=max(ans,nums[i]); } return ans; } };
6032. 得到要求路径的最小带权子图
题意
给出一个带权有向图，选一个子图使得该子图的权值和最小，并且从s r c 1 , s r c 2出发都可以到达d e s t
思路
其实是个很经典的模型，但是当时没有想到。
首先，权值最小要考虑最短路，那么src1跟src2到dest的路径上肯定是有重合的部分的，可以枚举重合的起点x，那么就知道所有符合条件的子图的权值，取最小值就是答案。
求子图权值要知道src1到x的最短路，src2到x的最短路，x到dest的最短路。
因为枚举的是x，所以前两个就分别是从src1,src2出发的最短路数组的值，第三个可以建反图，在反图上从dest跑最短路后数组的值就是答案。
求最短路用的bfs
代码
class Solution { public: vector<long long> bfs( vector<vector<pair<int,int>>>g,int s){ int n=g.size(); vector<long long>dis(n,1e18); vector<bool>st(n,false); dis[s]=0; st[s]=true; queue<int>q; q.push(s); while(!q.empty()){ int t=q.front();q.pop(); st[t]=false; for(auto it:g[t]){ int nex=it.first,w=it.second; if(dis[nex]>dis[t]+w){ dis[nex]=dis[t]+w; if(!st[nex]){ q.push(nex);st[nex]=true; } } } } return dis; } long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) { vector<vector<pair<int,int>>>g1(n); vector<vector<pair<int,int>>>g2(n);//反图 for(auto it:edges){ int from=it[0],to=it[1],w=it[2]; g1[from].push_back({to,w}); g2[to].push_back({from,w}); } vector<long long> dis1=bfs(g1,src1); vector<long long> dis2=bfs(g1,src2); vector<long long> dis3=bfs(g2,dest); long long ans=1e18; for(int i=0;i<n;i++) ans=min(ans,dis1[i]+dis2[i]+dis3[i]); if(ans==1e18) ans=-1; return ans; } };
