DFS

经典题目

1. 典型的，较为直观的DFS题。

200 Number of Islands 417 Pacific Atlantic Water Flow

200

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0)  return 0;
    int n = grid.length;
    int m = grid[0].length;
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1') {
                res += 1;
                dfs(grid, i, j, n, m);
            }
        }
    }
    return res;
}

private void dfs(char[][] grid, int i, int j, int n, int m) {
    if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == '0') {
        return;
    }
    grid[i][j] = '0';
    dfs(grid, i + 1, j, n, m);
    dfs(grid, i, j + 1, n, m);
    dfs(grid, i - 1, j, n, m);
    dfs(grid, i, j - 1, n, m);
}

417

class Solution {
    private int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}};
    
    public List<int[]> pacificAtlantic(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return new ArrayList<int[]>();
        
        int n = matrix.length;
        int m = matrix[0].length;
        
        boolean[][] canTouchPacific = new boolean[n][m];
        boolean[][] canTouchAtlantic = new boolean[n][m];
        List<int[]> ans = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            dfs(matrix, canTouchPacific, i, 0, Integer.MIN_VALUE);
            dfs(matrix, canTouchAtlantic, i, m - 1, Integer.MIN_VALUE);
        }
        
        for (int i = 0; i < m; i++) {
            dfs(matrix, canTouchPacific, 0, i, Integer.MIN_VALUE);
            dfs(matrix, canTouchAtlantic, n - 1, i, Integer.MIN_VALUE);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (canTouchPacific[i][j] && canTouchAtlantic[i][j]) {
                    ans.add(new int[]{i, j});
                }
            }
        }
        
        return ans;
    }
    
    private void dfs(int[][] matrix, boolean[][] sea, int row, int col, int prevHeight) {
        if (row < 0 || row >= sea.length || col < 0 || col >= sea[0].length || sea[row][col] || matrix[row][col] < prevHeight) {
            return;
        }
        sea[row][col] = true;        
        for (int i = 0; i < dirs.length; i++) {
            int newRow = row + dirs[i][0];
            int newCol = col + dirs[i][1];
            dfs(matrix, sea, newRow, newCol, matrix[row][col]);
        }
    }
}

332. Reconstruct Itinerary

DFS。这题是基于一定有一个解的前提，所以我们不用考虑无解的情况。即最后一个点必然是没有出度的点。然后我们用DFS扫，找到的第一个没有出度的点即为最后一个点，第二个点即为最后第二个点，以此类推。。（因为在top down的过程中，对应的pq出栈，即为了防止进入死循环）

英文的描述：The idea is to keep following unused edges and removing them until we get stuck. Once we get stuck, we back-track to the nearest vertex in our current path that has unused edges, and we repeat the process until all the edges have been used.

public List<String> findItinerary(String[][] tickets) {
    HashMap<String, PriorityQueue<String>> map = getMap(tickets);
    List<String> ans = new ArrayList<>();
    helper("JFK", map, ans);
    return ans;
}

private void helper(String cur, HashMap<String, PriorityQueue<String>> map, List<String> ans) {
    PriorityQueue<String> arrs = map.get(cur);
    while(arrs != null && !arrs.isEmpty()) {
        String arr = arrs.poll();
        helper(arr, map, ans);
    }
    ans.add(0, cur);
}

private HashMap<String, PriorityQueue<String>> getMap(String[][] tickets) {
    HashMap<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
    for (String[] t : tickets) {
        String dep = t[0];
        String arr = t[1];
        PriorityQueue<String> arrs = map.get(dep);
        if (arrs == null) {
            arrs = new PriorityQueue<String>();
        }
        arrs.add(arr);
        map.put(dep, arrs);
    }
    return map;
}

851 Loud and Rich

/*
    First build the graph.
    Then apply dfs to each node.
*/
public int[] loudAndRich(int[][] richer, int[] quiet) {
    List<List<Integer>> graph = buildGraph(richer, quiet.length);
    int[] ans = new int[quiet.length];
    Arrays.fill(ans, -1);
    for (int i = 0; i < quiet.length; i++) {
        cal(graph, i, quiet, ans);
    }
    return ans;
}

// DFS call to get minimum quietness among all people who have equal to or more
// money than person i.
private int cal(List<List<Integer>> graph, int i, int[] quiet, int[] ans) {
    if (ans[i] != -1) {
        return ans[i];
    }
    ans[i] = i;
    List<Integer> larger = graph.get(i);
    for (int large : larger) {
        int next = cal(graph, large, quiet, ans);
        if (quiet[ans[i]] >= quiet[next]) {
            ans[i] = next;
        }
    }
    return ans[i];
}

// Build Graph in the form of adjacent list
private List<List<Integer>> buildGraph(int[][] richer, int n) {
    // small : list of large
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<Integer>());
    }
    for (int i = 0; i < richer.length; i++) {
        int high = richer[i][0];
        int low = richer[i][1];
        graph.get(low).add(high);
    }
    return graph;
}