【力扣·周赛】第 284 场周赛(C++ | 枚举 | 分类讨论 | 最短路 | 建反图)

简介: 【力扣·周赛】第 284 场周赛(C++ | 枚举 | 分类讨论 | 最短路 | 建反图)

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. 统计可以提取的工件

题意

20200401134307494.png

20200401134307494.png

思路

数据范围看似很大,实际上每个工件最多只覆盖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 次操作后最大化顶端元素

题意

20200401134307494.png

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

20200401134307494.png

思路

其实是个很经典的模型,但是当时没有想到。

首先,权值最小要考虑最短路,那么src1跟src2到dest的路径上肯定是有重合的部分的,可以枚举重合的起点x,那么就知道所有符合条件的子图的权值,取最小值就是答案。

求子图权值要知道src1到x的最短路,src2到x的最短路,x到dest的最短路。

因为枚举的是x,所以前两个就分别是从src1,src2出发的最短路数组的值,第三个可以建反图,在反图上从dest跑最短路后数组的值就是答案。

求最短路用的bfs

20200401134307494.png

参考题解

代码

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;
    }
};
目录
相关文章
|
17小时前
|
编译器 C++
【C++】类和对象(下)
【C++】类和对象(下)
|
17小时前
|
编译器 C++
【C++】类和对象(中)(2)
【C++】类和对象(中)(2)
|
17小时前
|
存储 编译器 C++
【C++】类和对象(中)(1)
【C++】类和对象(中)(1)
|
21小时前
|
存储 编译器 C++
C++ 存储类
C++ 存储类
7 0
|
1天前
|
机器学习/深度学习 canal NoSQL
从C语言到C++_12(string相关OJ题)(leetcode力扣)
从C语言到C++_12(string相关OJ题)(leetcode力扣)
6 0
|
1天前
|
编译器 测试技术 C语言
从C语言到C++_11(string类的常用函数)力扣58和415(下)
从C语言到C++_11(string类的常用函数)力扣58和415
4 0
|
1天前
|
存储 编译器 C语言
从C语言到C++_11(string类的常用函数)力扣58和415(中)
从C语言到C++_11(string类的常用函数)力扣58和415
6 0
|
1天前
|
存储 C语言 C++
从C语言到C++_11(string类的常用函数)力扣58和415(上)
从C语言到C++_11(string类的常用函数)力扣58和415
6 0
|
1天前
|
C语言 C++
从C语言到C++⑧(第二章_类和对象_下篇_续)笔试选择题和OJ题
从C语言到C++⑧(第二章_类和对象_下篇_续)笔试选择题和OJ题
4 0
|
1天前
|
Java 编译器 C语言
从C语言到C++⑦(第二章_类和对象_下篇)初始化列表+explicit+static成员+友元+内部类+匿名对象(下)
从C语言到C++⑦(第二章_类和对象_下篇)初始化列表+explicit+static成员+友元+内部类+匿名对象
6 0