@Yano 2019-09-20T10:49:47.000000Z 字数 8643 阅读 3909

LeetCode Depth First Search 题目汇总

LeetCode

公众号

coding 笔记、点滴记录，以后的文章也会同步到公众号（Coding Insight）中，希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

130 Surrounded Regions

https://leetcode.com/problems/surrounded-regions/

题目描述

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

代码


class Solution {
    public void solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if ((i == 0 || i == board.length - 1 || j == 0 || j == board[0].length - 1) && board[i][j] == 'O') {
                    dfs(i, j, board);
                }
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '$') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
    private void dfs(int i, int j, char[][] board) {
        if (board[i][j] == 'O') {
            board[i][j] = '$';
            if (i > 0 && board[i - 1][j] == 'O') {
                dfs(i - 1, j, board);
            }
            if (i < board.length - 1 && board[i + 1][j] == 'O') {
                dfs(i + 1, j, board);
            }
            if (j > 0 && board[i][j - 1] == 'O') {
                dfs(i, j - 1, board);
            }
            if (j < board[0].length - 1 && board[i][j + 1] == 'O') {
                dfs(i, j + 1, board);
            }
        }
    }
}

133 Clone Graph

https://leetcode.com/problems/clone-graph/

题目描述

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

   1
  / \
 /   \
0 --- 2
     / \
     \_/

代码


/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        Map<Integer, UndirectedGraphNode> map = new HashMap<>();
        return dfs(node, map);
    }
    private UndirectedGraphNode dfs(UndirectedGraphNode node, Map<Integer, UndirectedGraphNode> map) {
        if (node == null) {
            return node;
        }
        if (map.containsKey(node.label)) {
            return map.get(node.label);
        }
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
        map.put(newNode.label, newNode);
        for (UndirectedGraphNode neighbors : node.neighbors) {
            newNode.neighbors.add(dfs(neighbors, map));
        }
        return newNode;
    }
}

200 Number of Islands

https://leetcode.com/problems/number-of-islands/

题目描述

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Answer: 1
Example 2:

Answer: 3

Credits:Special thanks to @mithmatt for adding this problem and creating all test cases.

代码


public class Solution {
        public void clearRestOfLand(int x, int y, char[][] grid) {
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == '0'){
            return;
        }
                grid[x][y] = '0';
        clearRestOfLand(x - 1, y, grid);
        clearRestOfLand(x + 1, y, grid);
        clearRestOfLand(x, y - 1, grid);
        clearRestOfLand(x, y + 1, grid);
    }
        public int numIslands(char[][] grid) {
        int count = 0;
                for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1') {
                    count++;
                    clearRestOfLand(i, j, grid);
                }
            }
        }
        return count;
    }
}

207 Course Schedule

https://leetcode.com/problems/course-schedule/

题目描述

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

click to show more hints.

Hints:

This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.

代码


class Solution {
    public boolean canFinish(int numCourses, int[][] pre) {
        // key 课程id，value 前置课程id
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < pre.length; i++) {
            if (map.containsKey(pre[i][0])) {
                map.get(pre[i][0]).add(pre[i][1]);
            } else {
                Set<Integer> set = new HashSet<>();
                set.add(pre[i][1]);
                map.put(pre[i][0], set);
            }
        }
        int[] visit = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(i, visit, map)) {
                return false;
            }
        }
        return true;
    }
    private boolean dfs(int i, int[] visit, Map<Integer, Set<Integer>> map) {
        if (visit[i] == -1) {
            return false;
        }
        if (visit[i] == 1) {
            return true;
        }
        visit[i] = -1;
        if (map.containsKey(i)) {
            for (int pre : map.get(i)) {
                if (!dfs(pre, visit, map)) {
                    return false;
                }
            }
        }
        visit[i] = 1;
        return true;
    }
}

210 Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

题目描述

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:

click to show more hints.

Hints:

This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.

代码


class Solution {
    public int[] findOrder(int numCourses, int[][] pre) {
        // key 课程id，value 前置课程id
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < pre.length; i++) {
            if (map.containsKey(pre[i][0])) {
                map.get(pre[i][0]).add(pre[i][1]);
            } else {
                Set<Integer> set = new HashSet<>();
                set.add(pre[i][1]);
                map.put(pre[i][0], set);
            }
        }
        int[] visit = new int[numCourses];
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(i, visit, map, ans)) {
                return new int[0];
            }
        }
                int[] result = new int[numCourses];
        for(int i = 0; i < numCourses; i++){
            result[i] = ans.get(i);
        }
                return result;
    }
    private boolean dfs(int i, int[] visit, Map<Integer, Set<Integer>> map, List<Integer> ans) {
        if (visit[i] == -1) {
            return false;
        }
        if (visit[i] == 1) {
            return true;
        }
        visit[i] = -1;
        if (map.containsKey(i)) {
            for (int pre : map.get(i)) {
                if (!dfs(pre, visit, map,ans)) {
                    return false;
                }
            }
        }
        visit[i] = 1;
        ans.add(i);
        return true;
    }
}

329 Longest Increasing Path in a Matrix

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

题目描述

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4

The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4

The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Credits:Special thanks to @dietpepsi for adding this problem and creating all test cases.

代码

public class Solution {
    public static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public int robot(int x, int y, int[][] m, int[][] cache) {
        if(cache[x][y] != 0) return cache[x][y];
        int max = 1;
        for(int[] dir : dirs) {
            int dx = dir[0], dy = dir[1];
            if(x + dx < 0 || x + dx >= m.length || y + dy < 0 || y + dy >= m[0].length || m[x][y] <= m[x + dx][y + dy]) {
                continue;
            }
            // 同一个值反复调用，就会产生冗余，需要缓存结果
            max = Math.max(max, robot(x + dx, y + dy, m, cache) + 1);
        }
        cache[x][y] = max;
        return max;
    }
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] cache = new int[m][n];
        int ans = 1;
        // 枚举每一个点，计算每个点的最大升序
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                ans = Math.max(ans, robot(i, j, matrix, cache));
            }
        }
        return ans;
    }
}

LeetCode Depth First Search 题目汇总

公众号

130 Surrounded Regions

题目描述

代码

133 Clone Graph

题目描述

代码

200 Number of Islands

题目描述

代码

207 Course Schedule

题目描述

代码

210 Course Schedule II

题目描述

代码

329 Longest Increasing Path in a Matrix

题目描述

代码

内容目录