剑指 Offer II 110+LCP09+LC605+112+113

所有路径

给定一个有 n 个节点的有向无环图，用二维数组 graph 表示，请找到所有从 0 到 n-1 的路径并输出（不要求按顺序）。

graph 的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些结点（译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a ），若为空，就是没有下一个节点了。

分析：

使用dfs，定义函数void dfs(graph, x, n)，graph代表有向无环图，x代表当前搜索的节点，n代表最后一个要访问的节点；因为是有向无环图所以不存在重复访问的情况。定义一个集合ans来接收所有可行的路径；定义另一个集合tmp来接收每一次搜索过程中的访问过得节点。当x==n时：代表已访问到最后一个节点，搜索终止并把当前的tmp加入到ans中去；否则去graph中找到x的邻接点，递归的去搜索这些点。

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> deque = new ArrayDeque<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n = graph.length;
        deque.offerLast(0);
        dfs(graph, 0, n-1);
        return ans;

    }
    void dfs(int[][] graph, int x, int e){
        if (x == e){
            ans.add(new ArrayList<>(deque));
            return;
        }
        int[] nodes = graph[x];
        for (int node : nodes){
            deque.offerLast(node);
            dfs(graph, node, e);
            deque.pollLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

最小跳跃次数

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。

为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。

分析：

dp问题，定义一维数组dp。从右向左计算dp值(从后向前)，当前位置如果为i 则它如果直接跳到右边（前面）去就是dp[jump[i]+i]+1（这个值已经计算过了），计算出当前位置dp[i]之后，当前位置i可以影响 i+1到dp[j] >= dp[i]+1位置上的值（因为某个位置可以跳到左边任意位置）注意遍历到dp[j]>=dp[i]+1即可。初始值dp[arr.length-1] = 1。

class Solution {
    public int minJump(int[] jump) {
        int[] dp = new int[jump.length];
        dp[jump.length - 1] = 1;
        for(int i = jump.length - 2; i > -1; --i){
            dp[i] = jump[i] + i >= jump.length ? 1 : dp[jump[i] + i] + 1;
            //遍历当前位置更新后影响到的后面的位置，只需要更新到dp[j] >= dp[i]+1即可
            //如果遍历到某dp[j]
             for(int j = i + 1; j < dp.length && dp[j] >= dp[i] + 1; ++j){
                dp[j] = dp[i] + 1;
            }
        }
        return dp[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

分析：

没什么难的就是对数组的遍历，不过要考虑清楚每一种情况。从左向右遍历数组flowerbed，如果当前位置index的值flowerbed[index]=0:

• 如果index==0且flowerbed[index+1]==0；
• 如果index==flowerbed.length-1且flowerbed[index-1]==0；
• flowerbed[index+1]==0且flowerbed[index-1]==0；

以上情况都可以在index位置上种花，则令flowerbed[index]=1。

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int i = 0;
        int count = 0;
        while (i < flowerbed.length){
            if (flowerbed[i] == 0 && (i==0||flowerbed[i-1]==0) && (i==flowerbed.length-1 || flowerbed[i+1]==0)){
                flowerbed[i] = 1;
                count++;
            }
            i++;
        }
        return count>=n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

分析：

dfs+记忆化搜索。定义一个二维数组dp，dp[i][j]表示从matrix[i][j]开始的最长递增路径。定义函数int dfs(matrix, x, y, count, pre)，x，y代表当前搜索点的坐标，count代表当前路径长度，pre代表访问该点之前点的值，pre初始化大小为-1。dfs遍历中的处理：

• 如果x，y越界则返回0；
• 如果matrix[x][y]<=pre，则返回0；
• 如果当前dp[x][y]中有记录，则返回dp[x][y]；
• 递归的去搜索上，下，左，右四个方向的点，取四个方向返回来的最大值max，设置dp[x][y]=max+1，并返回max+1;

然后去matrix中暴力搜索，求每个点的最长递增路径的长度，返回最大值。

class Solution {
    int[][] dp;
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        dp = new int[m][n];
        int ans = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                ans = Math.max(dfs(matrix, -1, i, j), ans);
            }
        }
        return ans;
    }
    public int dfs(int[][] matrix, int pre, int i, int j){
        if (i<0||j<0||i>=matrix.length||j>=matrix[0].length||matrix[i][j]<=pre) {
            return 0;
        }
        if (dp[i][j] != 0) return dp[i][j];
        int right = dfs(matrix, matrix[i][j], i+1, j);
        int left = dfs(matrix, matrix[i][j], i-1, j);
        int up = dfs(matrix, matrix[i][j], i, j+1);
        int down = dfs(matrix, matrix[i][j], i, j-1);

        int max = Math.max(Math.max(up, down), Math.max(left, right));
        dp[i][j] = max + 1;
        return dp[i][j];
    }
}
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

课程顺序

现在总共有 numCourses 门课需要选，记为 0 到 numCourses-1。

给定一个数组 prerequisites ，它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。 例如 prerequisites[i] = [ai, bi] 表示想要学习课程 ai ，需要先完成课程 bi 。

请根据给出的总课程数 numCourses 和表示先修顺序的 prerequisites 得出一个可行的修课序列。

可能会有多个正确的顺序，只要任意返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

分析：

拓扑排序。先对每一条边的关系建图，对prerequisites[i]中的ai和bi，认为是一条从bi到ai的边。定义集合edges，edges[i]表示从第i个节点可以到达的节点；定义数组infos，infos[i]表示第i个节点的入度。首先遍历数组prerequisites，向edges[bi]中加入ai，并将infos[ai]++；完成后开始进行bfs。首先定义一个队列q，把infos中值为0的点全部入队，这代表这些点没有先完成的课程可以先修；在广度优先搜索的每一步中，取出队首的节点 u：

• 将 u 放入答案中；
• 移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，那么就将 v 放入队列中。

在广度优先搜索的过程结束后。如果答案中包含了这 n 个节点，那么就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

class Solution {
    // 存储有向图
    List<List<Integer>> edges;
    // 存储每个节点的入度
    int[] indeg;
    // 存储答案
    int[] result;
    // 答案下标
    int index;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        indeg = new int[numCourses];
        result = new int[numCourses];
        index = 0;
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
            ++indeg[info[0]];
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        // 将所有入度为 0 的节点放入队列中
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            // 从队首取出一个节点
            int u = queue.poll();
            // 放入答案中
            result[index++] = u;
            for (int v: edges.get(u)) {
                --indeg[v];
                // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                if (indeg[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        if (index != numCourses) {
            return new int[0];
        }
        return result;
    }
}
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