系列文章

【英雄哥六月集训】第 01天:数组

【英雄哥六月集训】第 02天:字符串

【英雄哥六月集训】第 03天:排序

【英雄哥六月集训】第 04天:贪心

【英雄哥六月集训】第 05天: 双指针

【英雄哥六月集训】第 06天:滑动窗口

【英雄哥六月集训】第 07天:哈希

【英雄哥六月集训】第 08天:前缀和

【英雄哥六月集训】第 09天:二分查找

【英雄哥六月集训】第 10天: 位运算

【英雄哥六月集训】第 11天: 矩阵

【英雄哥六月集训】第 12天: 链表

【英雄哥六月集训】第 13天: 双向链表

【英雄哥六月集训】第 14天: 栈

【英雄哥六月集训】第 15天: 二叉树

【英雄哥六月集训】第 16天: 队列

【英雄哥六月集训】第 17天: 广度优先搜索

【英雄哥六月集训】第 18天: 树

【英雄哥六月集训】第 19天: 二叉树

【英雄哥六月集训】第 20天: 二叉搜索树

【英雄哥六月集训】第 21天: 堆(优先队列)

【英雄哥六月集训】第 22天: 有序集合

【英雄哥六月集训】第 23天: 字典树

【英雄哥六月集训】第 24天: 线段树

【英雄哥六月集训】第 25天: 树状数组

【英雄哥六月集训】第 26天: 并查集

【英雄哥六月集训】第 27天: 图

---

图

图通常用来表示和存储具有“多对多”关系的数据，是数据结构中非常重要的一种结构。

一、 概率最大的路径

1514. 概率最大的路径

class Solution {
    int maxn = 10010;
    List<List<Edge>> edge = new ArrayList<List<Edge>>(maxn);
    class Edge{
        int to;
        double val;
        Edge(){
        }

        Edge(int t,double v){
            this.to=t;
            this.val=v;
        }
    }

    public double bfs(int start,int end){
        double[] dis = new double[maxn];
        int i;
        for(i=0;i<maxn;++i){
            dis[i]=0.00d;
        }
        dis[start]=1.00d;
        Queue<Integer> q = new ArrayDeque<Integer>();
        q.add(start);
        while(!q.isEmpty()){
            Integer u = q.remove();
            int len = edge.get(u).size();
            for(i=0;i<len;++i){
                int v = edge.get(u).get(i).to;
                double d = dis[u]*(edge.get(u).get(i).val);

                if(d>dis[v]){
                    dis[v]=d;
                    q.add(v);
                }
            }
        }
        return dis[end];
    }
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        int i;
        for(i=0;i<maxn;++i){
            edge.add(new ArrayList<Edge>());
        }
        for(i=0;i<edges.length;++i){
            if(succProb[i]<=0){
                continue;
            }
            int u = edges[i][0];
            int v = edges[i][1];
            double w = succProb[i];

            edge.get(u).add(new Edge(v,w));
            edge.get(v).add(new Edge(u,w));
            
        }
        return bfs(start,end);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

---

二、 信物传送

LCP 56. 信物传送

class Solution {
    int[][] dir = new int[][]{
        {-1,0},{0,1},{1,0},{0,-1}
    };
    public int conveyorBelt(String[] matrix, int[] start, int[] end) {
        int i,j;
        int m=matrix.length;
        int n = matrix[0].length();
        int[][] grid = new int [110][110];
        for(i=0;i<m;i++){
            for(j=0;j<n;j++){
                if(matrix[i].charAt(j)=='^'){
                    grid[i][j]=0;
                }
                else if(matrix[i].charAt(j)=='>'){
                    grid[i][j]=1;
                }
                else if(matrix[i].charAt(j)=='v'){
                    grid[i][j]=2;
                }
                else if(matrix[i].charAt(j)=='<'){
                    grid[i][j]=3;
                }
            }
        }
        int u = start[0]*n+start[1];
        int[] dis = new int[10010];
        for(i=0;i<n*m;++i){
            dis[i]=100000000;
        }
        dis[u]=0;
        Deque<Integer> q = new ArrayDeque<Integer>();
        q.add(u);
        while(!q.isEmpty()){
            Integer f = q.remove();
            int x = f/n;
            int y = f%n;
            for(i=0;i<4;++i){
                int tx = x+dir[i][0];
                int ty = y+dir[i][1];

                if(tx<0||ty<0||tx==m||ty==n){
                    continue;
                }
                int next = tx*n+ty;
                int nextd = dis[f]+((grid[x][y]==i?0:1));
                if(nextd < dis[next]){
                    dis[next] = nextd;
                    q.add(next);
                }
            }
        }
        return dis[end[0]*n+end[1]];

        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

三、 T 秒后青蛙的位置

1377. T 秒后青蛙的位置

class Solution {
    int maxn = 110;
    List<List<Integer>> e = new ArrayList<List<Integer>>(maxn);
    double ans = 0.00d;
    public void inite(){
        for(int i=0;i<maxn;i++){
            e.add(new ArrayList<Integer>());
        }
    }
    public void dfs(int u,int fat,double p,int step,int maxstep,int target){
        int i,cnt=0;
        for(i =0; i<e.get(u).size(); ++i){
            if(e.get(u).get(i)!=fat){
                ++cnt;
            }
        }
        if(step <= maxstep){
            if(u==target){
                if(cnt ==0 && step <= maxstep){
                    ans = p;
                } else if(cnt>=1 && step == maxstep){
                    ans = p;
                }
            }
        }
        if(step == maxstep){
            return ;
        }

        for(i=0; i<e.get(u).size(); ++i){
            if(e.get(u).get(i)!=fat){
                dfs(e.get(u).get(i),u,p*1.0/cnt,step+1,maxstep,target);
            }
        }
    }
    public double frogPosition(int n, int[][] edges, int t, int target) {
        inite();
        int i;
        for(i=0; i<edges.length; ++i){
            int u = edges[i][0];
            int v = edges[i][1];

            e.get(u).add(v);
            e.get(v).add(u);
        }

        dfs(1,0,1,0,t,target);
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

总结