6031. 找出数组中的所有 K 近邻下标
题意
给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。K 近邻下标 是 nums 中的一个下标 i ，并满足至少存在一个下标 j 使得 |i - j| <= k 且 nums[j] == key 。以列表形式返回按 递增顺序 排序的所有 K 近邻下标。
$1 <= nums.length <= 1000$
思路
数组大小为$1000$，考虑$O(n^2)$的算法。
先枚举$i$，再枚举$j$，枚举$j$的时候可以缩小范围，只枚举$i$前的$k$个和$i$后的$k$个，再判断$j$的值是不是等于目标值。如果等于的话说明$i$是$K$近相邻下标，将$i$放入答案里然后要及时$break$，不然会重复放。
代码
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(artifacts.length)$
代码
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 <= 10^5$
思路
考虑特殊情况，如果$n==1$，那么要考虑$k$的奇偶性。如果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. 得到要求路径的最小带权子图
题意
给出一个带权有向图，选一个子图使得该子图的权值和最小，并且从$src1,src2$出发都可以到达$dest$
思路
其实是个很经典的模型，但是当时没有想到。
首先，权值最小要考虑最短路，那么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;
}
};
