暑假算法训练营报名

本文主要分享【暑假算法训练营报名】，技术文章【暑假算法7.25，Day24】为【小十一吖】投稿，如果你遇到算法相关问题，本文相关知识或能到你。

暑假算法训练营报名

暑假算法7.25，Day24

图论，背模板代码。。

第一题

网络延迟时间

class Solution {
   
    int N=105;
    int[][] g=new int [N][N];
    int[] dist=new int[N];
    boolean[] st=new boolean[N];
    public int networkDelayTime(int[][] times, int n, int k) {
   
        for(int i=0;i<=n;i++){
   
            Arrays.fill(g[i],0x3f3f3f3f);
        }
        for(int[] nums:times){
   
            int a=nums[0];
            int b=nums[1];
            int c=nums[2];
            g[a][b]=c;
        }
        return dijkstra(n,k);
    }
    int dijkstra(int n,int k){
   
        Arrays.fill(dist,0x3f3f3f3f);
        dist[k]=0;
        for(int i=0;i<n;i++){
   
            int t=-1;
            for(int j=1;j<=n;j++){
   
                if(!st[j]&&(t==-1||dist[j]<dist[t])){
   
                    t=j;
                }
            }
            st[t]=true;
            for(int j=1;j<=n;j++){
   
                dist[j]=Math.min(dist[j],dist[t]+g[t][j]);
            }
        }
        int res=0;
        for(int j=1;j<=n;j++){
   
            if(dist[j]==0x3f3f3f3f){
   
                return -1;
            }
            res=Math.max(res,dist[j]);
        }
        return res;
    }
}

第二题

K站中转内最便宜的航班

class Solution {
   
    //有边数限制使用贝尔曼夫算法
    int N=100;
    int M=5010;
    List<Node> list=new ArrayList<>();
    int[] dist=new int[N];
    int[] backup=new int[N];
    int n,m,k,src,dst;
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
   
        this.n=n;
        this.m=flights.length;
        //k次中转是k条边
        this.k=k+1;
        this.src=src;
        this.dst=dst;
        for(int[] s:flights){
   
            int a=s[0];
            int b=s[1];
            int w=s[2];
            list.add(new Node(a,b,w));
        }
        int t=bellman_ford();
        return t;
    }
    int bellman_ford(){
   
        Arrays.fill(dist,0x3f3f3f3f);
        dist[src]=0;
        for(int i=0;i<k;++i){
   
            backup=Arrays.copyOfRange(dist,0,N);
            for(int j=0;j<m;++j){
   
                int a=list.get(j).a;
                int b=list.get(j).b;
                int w=list.get(j).w;
                dist[b]=Math.min(dist[b],backup[a]+w);
            }
        }
        if(dist[dst]>0x3f3f3f3f/2) return -1;
        else return dist[dst];
    }
}
class Node{
   
    int a,b,w;
    public Node(int a, int b, int w) {
   
            this.a = a;
            this.b = b;
            this.w = w;
    }
}

第三题

到达角落需要移除的障碍物的最小数目

struct node{
   
    int x,y;
    int d;
    bool operator<(const node&a)const{
   
        return d>a.d;
    }
};
class Solution {
   
public:
    int minimumObstacles(vector<vector<int>>& grid) {
   
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dirs{
   {
   -1, 0}, {
   0, 1}, {
   1, 0}, {
   0, -1}};
        vector<vector<int>> visited(m, vector<int>(n, 0));
        vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
        visited[0][0] = 0;
        dis[0][0]=0;
        priority_queue<node> q;
        q.push((node){
   0, 0, 0});
        while (!q.empty()) {
   
            auto t = q.top(); q.pop();
            if(!visited[t.x][t.y]) {
   
                visited[t.x][t.y]=1;
                for (auto dir : dirs) {
   
                    int x = t.x + dir[0], y = t.y + dir[1];
                    if (x < 0 || x >= m || y < 0 || y >= n) continue;
                    if(dis[x][y]>dis[t.x][t.y]+grid[x][y]){
   
                        dis[x][y]=dis[t.x][t.y]+grid[x][y];
                        q.push((node){
   x,y,dis[x][y]});
                    }
                }
            }
        }
        return dis[m-1][n-1];
    }
};

本文《暑假算法7.25，Day24》版权归小十一吖所有，引用暑假算法7.25，Day24需遵循CC 4.0 BY-SA版权协议。