0


【解题报告】力扣 第 284 场周赛

文章目录

一、找出数组中的所有 K 近邻下标

1、算法:二维枚举

  用一个结果数组保存最后结果,数据量只有1000,所以直接上枚举,对于每个下标,去找所有等于

key

的下标,如果找到则直接塞到结果数组中。时间复杂度

     O
    
    
     (
    
    
     
      n
     
     
      2
     
    
    
     )
    
   
   
    O(n^2)
   
  
 O(n2)。

2、源码

classSolution{public:
    vector<int>findKDistantIndices(vector<int>& nums,int key,int k){int i, j;
        vector<int> ans;for(i =0; i < nums.size();++i){for(j =0; j < nums.size();++j){if(key != nums[j]){continue;}if(i < j && j-i <= k){
                    ans.push_back(i);break;}elseif(j <= i && i-j <= k){
                    ans.push_back(i);break;}}}return ans;}};

二、统计可以提取的工件

1、算法:二维哈希

  直接用一个哈希表哈希出所有的格子,然后对于每个格子如果都被哈希了,则计数器加一。统计格子数量为

     n
    
   
   
    n
   
  
 n,挖出来的数量为 
 
  
   
    
     m
    
   
   
    m
   
  
 m,时间复杂度 
 
  
   
    
     O
    
    
     (
    
    
     n
    
    
     +
    
    
     m
    
    
     )
    
   
   
    O(n+m)
   
  
 O(n+m)。

2、源码

int hashv[1010][1010];classSolution{public:intdigArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig){int i, j, k;int ans =0;bool flag;memset(hashv,0,sizeof(hashv));for(i =0; i < dig.size();++i){
            hashv[ dig[i][0]][ dig[i][1]]=1;}for(i =0; i < artifacts.size();++i){
            flag =true;for(j = artifacts[i][0]; j <= artifacts[i][2]; j++){for(k = artifacts[i][1]; k <= artifacts[i][3];++k){if(hashv[j][k]==0){
                        flag =false;}}}if(flag){++ans;}}return ans;}};

三、K 次操作后最大化顶端元素

1、算法:分情况讨论

  讨论

     k
    
    
     =
    
    
     0
    
    
     ,
    
    
     1
    
    
     ,
    
    
     2
    
   
   
    k = 0,1,2
   
  
 k=0,1,2 的情况,再讨论 
 
  
   
    
     k
    
   
   
    k
   
  
 k 和 
 
  
   
    
     n
    
   
   
    n
   
  
 n 的大小关系。反正就是疯狂分情况讨论。

 
  
   
    
     k
    
    
     =
    
    
     0
    
   
   
    k=0
   
  
 k=0,直接返回第 0 个元素;

 
  
   
    
     k
    
    
     =
    
    
     1
    
   
   
    k=1
   
  
 k=1,元素个数小于等于1,返回-1,否则直接返回第 1 个元素;

 
  
   
    
     k
    
    
     =
    
    
     2
    
   
   
    k=2
   
  
 k=2,元素个数小于等于2,返回第0个元素,否则直接返回第 0 个元素 和 第 2 个元素中的大者;

 
  
   
    
     k
    
    
     >
    
    
     3
    
    
     且
    
    
     n
    
    
     =
    
    
     1
    
   
   
    k>3 且 n=1
   
  
 k>3且n=1 的时候,
 
  
   
    
     k
    
    
     −
    
    
     n
    
   
   
    k-n
   
  
 k−n 是奇数,则返回第0个元素,否则返回 -1;

 
  
   
    
     k
    
    
     >
    
    
     3
    
    
     且
    
    
     n
    
    
     >
    
    
     1
    
   
   
    k > 3 且 n>1
   
  
 k>3且n>1的时候,继续讨论:

 
  
   
    
     k
    
    
     <
    
    
     n
    
   
   
    k < n
   
  
 k<n 时,两种情况:

         1. 删除

     k
    
   
   
    k
   
  
 k 个,然后 
 
  
   
    
     n
    
    
     u
    
    
     m
    
    
     s
    
    
     [
    
    
     k
    
    
     ]
    
   
   
    nums[k]
   
  
 nums[k] 就是栈顶;

         2. 删除

     k
    
    
     −
    
    
     1
    
   
   
    k-1
   
  
 k−1 个,然后从 前 
 
  
   
    
     k
    
    
     −
    
    
     1
    
   
   
    k-1
   
  
 k−1 个中,找最大值;

 
  
   
    
     k
    
    
     =
    
    
     n
    
   
   
    k = n
   
  
 k=n 时,取前 
 
  
   
    
     n
    
    
     −
    
    
     1
    
   
   
    n-1
   
  
 n−1 个最大值;

 
  
   
    
     k
    
    
     >
    
    
     n
    
   
   
    k > n
   
  
 k>n 时,取前 
 
  
   
    
     n
    
   
   
    n
   
  
 n 个最大值;

2、源码

class Solution {
public:intmaximumTop(vector<int>& nums,int k){int n = nums.size();int maxv =0;// 边界条件if(k ==0){return nums[0];}elseif(k ==1){if(n <=1){return-1;}else{return nums[1];}}elseif(k ==2){if(n <=2){return nums[0];}else{returnmax(nums[0], nums[2]);}}else{if(n ==1){if((k-n)&1){return nums[0];}return-1;}}if(k < n){// 两种情况://     1. 删除 k 个,然后 nums[k] 就是栈顶//     2. 删除 k-1 个,然后从 前 k-1 个中,找最大值
            maxv = nums[k];for(int i =0; i < k-1;++i){
                maxv =max(maxv, nums[i]);}}elseif(k == n){
            maxv =0;for(int i =0; i < k-1;++i){
                maxv =max(maxv, nums[i]);}}else{sort(nums.begin(), nums.end());
            maxv = nums[ nums.size()-1];}return maxv;}};

四、得到要求路径的最小带权子图

1、算法:广度优先搜索

  建立一个正图

     A
    
   
   
    A
   
  
 A 和 反图 
 
  
   
    
     B
    
   
   
    B
   
  
 B,
 
  
   
    
     s
    
    
     r
    
    
     1
    
    
     [
    
    
     i
    
    
     ]
    
   
   
    sr1[i]
   
  
 sr1[i] 代表正图 
 
  
   
    
     A
    
   
   
    A
   
  
 A 上从 
 
  
   
    
     s
    
    
     r
    
    
     c
    
    
     1
    
   
   
    src1
   
  
 src1 到 
 
  
   
    
     i
    
   
   
    i
   
  
 i 的最短路;
 
  
   
    
     s
    
    
     r
    
    
     2
    
    
     [
    
    
     i
    
    
     ]
    
   
   
    sr2[i]
   
  
 sr2[i] 代表正图 
 
  
   
    
     A
    
   
   
    A
   
  
 A 上从 
 
  
   
    
     s
    
    
     r
    
    
     c
    
    
     2
    
   
   
    src2
   
  
 src2 到 
 
  
   
    
     i
    
   
   
    i
   
  
 i 的最短路;
 
  
   
    
     d
    
    
     e
    
    
     s
    
    
     t
    
    
     [
    
    
     i
    
    
     ]
    
   
   
    dest[i]
   
  
 dest[i] 代表反图 
 
  
   
    
     B
    
   
   
    B
   
  
 B 上从 
 
  
   
    
     d
    
    
     e
    
    
     s
    
    
     t
    
   
   
    dest
   
  
 dest 到 
 
  
   
    
     i
    
   
   
    i
   
  
 i 的最短路;然后就是 
 
  
   
    
     s
    
    
     r
    
    
     1
    
    
     [
    
    
     i
    
    
     ]
    
    
     +
    
    
     s
    
    
     r
    
    
     2
    
    
     [
    
    
     i
    
    
     ]
    
    
     +
    
    
     d
    
    
     e
    
    
     s
    
    
     t
    
    
     [
    
    
     i
    
    
     ]
    
   
   
    sr1[i] + sr2[i] + dest[i]
   
  
 sr1[i]+sr2[i]+dest[i] 取个最小值就可以了。

  最短路就用 Dijkstra + Heap 优化,或者 SPFA。

2、源码

class Solution {longlongminv(longlong a,longlong b){return a < b ? a : b;}struct edge {int v;longlong w;edge(){}edge(int _v,longlong _w){
            v = _v;
            w = _w;}};
    vector<edge> eg[2][100010];

    vector<longlong>bfs(int eid,int n,int start){
        vector<longlong> dist;
        priority_queue <int> q;int i;for(i =0; i < n;++i){
            dist.push_back(-1);}
        dist[start]=0;
        q.push(start);while(!q.empty()){int u = q.top();
            q.pop();for(int i = eg[eid][u].size()-1; i >=0;--i){int v = eg[eid][u][i].v;longlong w = eg[eid][u][i].w;if(dist[u]+ w < dist[v]|| dist[v]==-1){
                    dist[v]= dist[u]+ w;
                    q.push(v);}}}return dist;}
public:longlongminimumWeight(int n, vector<vector<int>>& edges,int src1,int src2,int dest){int i;longlong ret =1000000000;
        ret *= ret;longlong x = ret;
        vector<longlong> sr1, sr2, ds;for(i =0; i < n;++i){
            eg[0][i].clear();
            eg[1][i].clear();}for(i =0; i < edges.size();++i){int u = edges[i][1];int v = edges[i][0];int w = edges[i][2];
            eg[0][v].push_back(edge(u, w));
            eg[1][u].push_back(edge(v, w));}
        sr1 =bfs(0, n, src1);for(i =0; i < n;++i){if(sr1[i]!=-1){break;}}if(i == n){return-1;}
        
        sr2 =bfs(0, n, src2);for(i =0; i < n;++i){if(sr2[i]!=-1){break;}}if(i == n){return-1;}
        
        ds =bfs(1, n, dest);for(i =0; i < n;++i){if(sr1[i]==-1|| sr2[i]==-1|| ds[i]==-1){continue;}
            ret =minv(ret, sr1[i]+ sr2[i]+ ds[i]);}return ret == x ?-1: ret;}};
标签: leetcode 算法 图论

本文转载自: https://blog.csdn.net/WhereIsHeroFrom/article/details/123457150
版权归原作者 英雄哪里出来 所有, 如有侵权,请联系我们删除。

“【解题报告】力扣 第 284 场周赛”的评论:

还没有评论