leetcode之最短路径+记忆化dfs+bfs+动态规划刷题总结_leetcode最短路径

leetcode之最短路径+记忆化dfs+bfs+动态规划刷题总结

最短路:给定两个顶点，在以这两个顶点为起点和终点的路径中，边的权值和最小的路径。

最短路径中有几种经典的算法，我们主要练习的是Dijkstra算法和Floyd算法，分别用于解决单元最短路径问题和多源最短路径问题。

Dijkstra算法适用于单源最短路径，具体地，找到最短路已经确定的节点，从它出发更新相邻节点的最短距离。

Floyd算法适用于多源最短路径，具体地，通过一系列n阶矩阵来计算一个n节点加权图的最短距离。每轮让第k个节点做中转节点，更新第i个节点到第j个节点的最短路径。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。

动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。

记忆化即记忆化搜索，也叫记忆化递归，其实就是拆分子问题的时候，发现有很多重复子问题，然后再求解它们以后记录下来。以后再遇到要求解同样规模的子问题的时候，直接读取答案。

使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次.

广度优先搜索算法（Breadth-First Search，缩写为 BFS），又称为宽度优先搜索，是一种图形搜索算法。简单的说，BFS 是从根结点开始，沿着树的宽度遍历树的结点。如果所有结点均被访问，则算法中止。

1-电动车游城市
题目链接：题目链接戳这里！！！

思路：Dijkstra算法
对paths数组建立邻接表，分别存储两个相邻节点以及节点之间的权值，ans数组记录到达当前节点的最少用时，优先队列中存储所用时间，当前位置，剩余电量，并且按照所用时间升序排序，保证每次选择的都是所用时间最少的，如果电量未满可以考虑充电，如如果剩余电量够，可以往相邻的节点走。

class Solution {
    public int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {
        int n = charge.length ;
        List<int[]> [] g = new List[n] ;

        for(int i=0; i<n; i++){
            g[i] = new ArrayList<int[]>() ;
        }

        for(int [] path : paths){ //建立邻接表，后面好操作
            int u = path[0], v = path[1], w = path[2] ;
            g[u].add(new int [] {v, w}) ;
            g[v].add(new int [] {u, w}) ;
        }

        int [][] ans = new int [n][cnt+1] ; //当前位置n，剩余电量cnt，时候的最少用时
        for(int i=0; i<n; i++){
            Arrays.fill(ans[i], Integer.MAX_VALUE/2) ;
        }
        ans[start][0] = 0 ;

        PriorityQueue<int []> queue = new PriorityQueue<>((a,b)->(a[0]-b[0])) ;
        queue.add(new int [] {0, start, 0}) ; //数组中三个元素分别为已用时间，当前位置，剩余电量

        while(!queue.isEmpty()){
            int [] p = queue.poll() ;
            int time = p[0], cur = p[1], power = p[2] ;

            if(time > ans[cur][power]){
                continue ;
            }
            if(cur == end){
                return time ;
            }
            if(power<cnt){//电量未满，可以考虑充电
                int t = time + charge[cur] ;
                if(t<ans[cur][power+1]){
                    ans[cur][power+1] = t ;
                    queue.add(new int [] {t, cur, power+1}) ;
                }
            }

            for(int [] path : g[cur]){
                int next = path[0] ;
                int cost = path[1] ;
                int t = time + cost ;
                int pow = power - cost ;
                if(pow>=0 && t<ans[next][pow]){
                    ans[next][pow] = t ;
                    queue.add(new int [] {t, next, pow}) ;
                }
            }
        }
        return -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

2-K站中转内最便宜的航班
题目链接：题目链接戳这里！！！

思路1：记忆化搜索(dfs)
从src出发，搜索所有能到dst的，并且中转个数少于k的路径，找出价格最便宜的路径价格。

用memo[i][k]做记忆化，防止重复计算，该数组表示从i点到达终点经历不超过k次中转的最低价格。

class Solution {
    int INF = 1000000007 ;
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        //记忆化搜索
        //memo[i][k]数组记录从当前顶点i出发经过最多k个中转点到最后的顶点的最便宜的价格
        int [][] memo = new int [n][k+2] ;

        int ans = dfs(flights, src, dst, k+1, memo) ;

        return ans>=INF ? -1 : ans ;
    }

    public int dfs(int [][] flights, int i, int end, int k, int [][] memo){
        if(k<0){
            return INF ;
        }
        if(i==end){
            return 0 ;
        }
        if(memo[i][k] != 0){
            return memo[i][k] ;
        }

        int min = INF ;
        for(int [] flight : flights){
            if(flight[0]==i){
                min = Math.min(min, dfs(flights, flight[1], end, k-1, memo) + flight[2]) ;
            }
        }
        memo[i][k] = min ;
        return min ;

    }
}
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

思路2：bfs+剪支
对于当前节点，遍历相邻节点，每一轮bfs，k减少1，如果找到更小的价格，则更新ans数组。

class Solution {
    int INF = 1000000007 ;
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
       //bfs+剪支
       List<int []> [] g = new List[n] ;
       for(int i=0; i<n; i++){
           g[i] = new ArrayList<>() ;
       }

       for(int [] flight : flights){
           int u = flight[0], v = flight[1], w=flight[2] ;
           g[u].add(new int [] {v, w}) ;
       }

       int [] ans = new int [n] ;
       Arrays.fill(ans, Integer.MAX_VALUE) ;
       Queue<int []> queue = new LinkedList<>() ;
       queue.add(new int [] {src, 0}) ;

       while(!queue.isEmpty() && k+1>0){
           int size = queue.size() ;
           for(int i=0; i<size; i++){
               int [] p = queue.poll() ;
               for(int [] f : g[p[0]]){
                   int price = p[1] + f[1];
                   if(price < ans[f[0]]){
                       ans[f[0]] = price ;
                       if(f[0] != dst){
                       queue.add(new int [] {f[0], price}) ;
                       }
                   }
               }
           }
           k -- ;
       }
       return ans[dst] >= INF ? -1 : ans[dst] ;

    }
}
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

思路3：动态规划
其实就是记忆化递归的转换，自顶向下变成自底向上。

class Solution {
    int INF = 1000000007 ;
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
     //动态规划
     //dp[i][k]表示从i点出发到dst走最多k+1步的最少价格
     int [][] dp = new int [n][k+2] ;
     for(int i=0; i<n; i++)
     Arrays.fill(dp[i],INF) ;
     return f(n, flights, src, dst, k+1, dp) ;
    }
    public int f(int n, int [][] flights, int src, int dst, int K, int [][] dp){
        dp[dst][0] = 0 ;

        for(int k=1; k<=K; k++){
            for(int [] flight : flights){
                dp[flight[0]][k] = Math.min(dp[flight[0]][k], dp[flight[1]][k-1] + flight[2]) ;
            }
        }
        int ans =  IntStream.of(dp[src]).min().getAsInt() ;

        return ans >= INF ? -1 : ans ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3-阈值距离内邻居最少的城市
题目链接：题目据链接戳这里！！！

思路：首先要求出来每个节点到其余节点的最短路径，所以可以使用Floyd算法，使用matrix矩阵记录从i节点到j节点的最短路长度，然后遍历所有i节点，如果到达j节点的距离小于等于distanceThreshold，则使用nums[i]记录满足要求的路径数量，选择最小值。

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        //多源最短路径，使用Floyd算法
        int [][] matrix = new int [n][n] ; 
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                matrix[i][j] = 1000000000 ;
            }
        }

        for(int i=0; i<n; i++){
            matrix[i][i] = 0 ;
        }

        for(int [] edge : edges){
            int u = edge[0], v = edge[1], w = edge[2] ;
            matrix[u][v] = matrix[v][u] = w ;
        }

        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    matrix[i][j] = Math.min(matrix[i][j], matrix[i][k]+matrix[k][j]) ;
                }
            }
        }

        int [] num = new int [n] ;
        int pos = -1, min = 1000000000 ;

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j]<=distanceThreshold){
                    num[i] ++ ;
                }
            }
            if(num[i] <= min){
                min = num[i] ;
                pos = i ;
            }
        }

        return pos ;
    }
}
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

**

不辜负每一份热情，不讨好每一份冷漠，做好自己，健健康康为祖国工作50年！！！

**