[数据结构与算法]3.13 3.14 LeetCode 284周赛

6031. 找出数组中的所有 K 近邻下标

• 题目大意
  给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。K 近邻下标 是 nums 中的一个下标 i ，并满足至少存在一个下标 j 使得 |i - j| <= k 且 nums[j] == key 。
  以列表形式返回按 递增顺序 排序的所有 K 近邻下标。

• 思路

• code

class Solution {
public:
    vector<int> findKDistantIndices(vector<int>& nums, int key, int k) {
        int n = nums.size();
        int b[1010]={0};
        int ans=0;
        for(int i=0;i<n;i++)
        {
            if(nums[i]==key)
            {
                for(int j=max(0,i-k);j<=min(n,i+k);j++)
                {
                    if(b[j]!=1) ans++;
                    b[j]=1;
                }
            }
        }
        vector<int> v;
        for(int i=0;i<n;i++) if(b[i]) v.push_back(i);
        return v;
    }
};

5203. 统计可以提取的工件

• 题目大意
  有n个工件，他们的坐标（左上角和右下角）存放在artifacts数组内。给定一系列挖掘坐标（x,y）表示挖掘（x,y）。若一个工件的所有位置都被挖掘出来，这个工件就可以被提取出来。问一共可以提取多少个工件。
• 思路
  标记被挖掘的位置，最后统计一遍每个工件所在的位置是否全部被挖掘即可。
• code

class Solution {
public:
    int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
        int m=dig.size();
        int all=artifacts.size();
        int mp[1010][1010];
        for(int i=0;i<n;i++) for(int j=0;j<n;j++) mp[i][j]=0;
        for(int i=0;i<m;i++)
        {
            int x=dig[i][0],y=dig[i][1];
            mp[x][y]=1;
        }
        int ans=0;
        for(int i=0;i<all;i++)
        {
            bool is_ok=true;
            for(int x=artifacts[i][0];x<=artifacts[i][2];x++)
                for(int y=artifacts[i][1];y<=artifacts[i][3];y++)
                    if(mp[x][y]==0) is_ok=false;
            if(is_ok) ans++;
        }
        return ans;  
    }
};

5227. K 次操作后最大化顶端元素

• 题目大意
  给定一个栈，每次操作可以从栈头弹出元素或者把已经弹出栈的元素放回栈首。给定一个原始的栈$nums[i]$，你有n次操作，问这样过后能得到的最大栈顶元素是多少。
• 思路
  最最最讨厌的分类讨论题 因为要错好几次才能写对。
  分类讨论情况比较多的题目。有如下情况：
  $k=0$：直接输出 $nums[0]$；
  $n=1$：若 kk 为奇数则输出 -1，否则输出 $nums[0]$；
  $1\le k\le n$：有两种小情况，取其中的最大值即可。
  可以首先将栈顶的 (k - 1)个元素弹出，最后一步操作加入这些元素中的最大值；
  可以将栈顶的 k个元素弹出，露出$nums[k]$ 。
  $k>n$：一定能取到所有数中的最大值。首先将所有数弹出，然后还剩 (k - n)步操作，分析如下。
  若 $(k?n)$是奇数，则反复将最大值加入弹出栈即可。
  若 $(k?n)$ 是偶数，先将一个非最大值加入栈，然后反复将最大值加入弹出栈即可。
• code

class Solution {
public:
    int maximumTop(vector<int>& nums, int k) {
        int n = nums.size();
        if(k==0) return nums[0];
        else if(n==1)
        {
            if(k&1) return -1;
            else return nums[0];
        }
        else if(k<=n)
        {
            int maxn=-9999999;
            for(int i=0;i<k-1;i++) maxn=max(maxn, nums[i]); 
            maxn=max(maxn,nums[k]);
            return maxn;
        }
        else{
            int maxn = -9999999;
            for(int i=0;i<n;i++) maxn=max(maxn,nums[i]);
            return maxn;
        }
    }
};

6032. 得到要求路径的最小带权子图

• 题目大意
  给定一个图，求scr1，scr2都能到达dest的最小边权子图。
• 思路
  由于最后的子图一定是一个三岔路口的形式，每个岔路都是端点之间的最短路，于是我们可以枚举三岔路口节点。其中scr1和scr2跑正向边权的dijkstra预处理出scr1和scr2到每个点的最短路径，dest跑反向边预处理出dest到每一个点的最短路。最后循环一遍枚举每个节点作为岔路口节点，去的答案的最小值即可。
• code

const int N = 100010;
class Solution {

#define ll long long
vector<pair<int, ll>> v[N];
vector<pair<int, ll>> u[N];

vector<ll>& dijk(int s, vector<ll>& dist, vector<pair<int, ll>> w[])
{
    dist[s]=0;                                                             
    priority_queue<pair<int, ll>> q;
    q.push(make_pair(s, 0));        
    while(!q.empty())
    {
        int c=q.top().first, d=q.top().second;
        q.pop();
        if(dist[c]<d) continue;
        for(auto [x, y]:w[c])
        {                          
            if(y + d < dist[x])
            {
                dist[x]=y + d; 
                q.push(make_pair(x, dist[x]));
            } 
        }                       
    }
    return dist;
}

public:
    long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {    
        int m = edges.size();  
        vector<ll> dist1(n, 1e15),dist2(n, 1e15),dist3(n, 1e15);
 
        for(int i=0;i<m;i++)
        {
            v[edges[i][0]].push_back(make_pair(edges[i][1],edges[i][2]));
            u[edges[i][1]].push_back(make_pair(edges[i][0],edges[i][2]));
        } 

        dist1=dijk(src1, dist1, v);dist2=dijk(src2, dist2, v);dist3=dijk(dest, dist3, u);
        
        // for(auto i:dist1) cout<<i<<' ';puts("");
        // for(auto i:dist2) cout<<i<<' ';puts("");
        // for(auto i:dist3) cout<<i<<' ';puts("");

        ll ans=1e15;
        for(int i=0;i<n;i++)
        {
            ll temp = dist1[i]+dist2[i]+dist3[i];
            ans=min(ans,temp);
        }
        if(ans>=1e15) return -1;   
        else return ans;
    }
};