Depth First Search (Java) - ShuweiLeung/Thinking GitHub Wiki

T(i, s1, s2, s3, s4) = T(i - 1, s1 - nums[i], s2, s3, s4) ||
                       T(i - 1, s1, s2 - nums[i], s3, s4) ||
                       T(i - 1, s1, s2, s3 - nums[i], s4) ||
                       T(i - 1, s1, s2, s3, s4 - nums[i])

    //拓扑排序的典型解法，该题是一个经典应用题目
    public int[] findOrder(int numCourses, int[][] prerequisites) { 
        if (numCourses == 0) return null;
        // Convert graph presentation from edges to indegree of adjacent list.
        int indegree[] = new int[numCourses], order[] = new int[numCourses], index = 0;
        for (int i = 0; i < prerequisites.length; i++) // Indegree - how many prerequisites are needed.
            indegree[prerequisites[i][0]]++;    

        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; i++) 
            if (indegree[i] == 0) {
                // Add the course to the order because it has no prerequisites.
                order[index++] = i;
                queue.offer(i);
            }

        // How many courses don't need prerequisites. 
        while (!queue.isEmpty()) {
            int prerequisite = queue.poll(); // Already finished this prerequisite course.
            for (int i = 0; i < prerequisites.length; i++)  {
                if (prerequisites[i][1] == prerequisite) {
                    indegree[prerequisites[i][0]]--; 
                    if (indegree[prerequisites[i][0]] == 0) {
                        // If indegree is zero, then add the course to the order.
                        order[index++] = prerequisites[i][0];
                        queue.offer(prerequisites[i][0]);
                    }
                } 
            }
        }

        return (index == numCourses) ? order : new int[0];
    }

    Map<String, PriorityQueue<String>> flights;
    LinkedList<String> path;

    public List<String> findItinerary(String[][] tickets) {
        flights = new HashMap<>();
        path = new LinkedList<>();
        for (String[] ticket : tickets) { 	//简历map
            flights.putIfAbsent(ticket[0], new PriorityQueue<>());
            flights.get(ticket[0]).add(ticket[1]);
        }
        dfs("JFK");
        return path;
    }

    public void dfs(String departure) {
        PriorityQueue<String> arrivals = flights.get(departure);
        while (arrivals != null && !arrivals.isEmpty())  //按字典序从小到大遍历所有从当前departure出发能到达的目的地
            dfs(arrivals.poll()); //遍历当前departure的可达地点时，将领近机场弹出pq，起到了visited数组的作用，当再次访问departure时，不会出现无限递归
        path.addFirst(departure);   //将其所有目的地都遍历完以后，再把出发地加入路径集合中（backtracking，保证将死胡同的目的地放到后边访问）
    }

    boolean res = false; //返回结果，true为能组成24
    final double eps = 0.001;  //精度，当double的数值小于0.001时，认为该数等于0

    public boolean judgePoint24(int[] nums) {
        List<Double> arr = new ArrayList<>();
        for(int n: nums) arr.add((double) n);  //将nums整型数组改为double的arraylist
        helper(arr);
        return res;
    }

    private void helper(List<Double> arr){
        if(res) return;
        if(arr.size() == 1){  //当数组元素只有1时，我们判断是否为24
            if(Math.abs(arr.get(0) - 24.0) < eps)
                res = true;
            return;
        }
        for (int i = 0; i < arr.size(); i++) {  //遍历数组，求所有两个数字的组合
            for (int j = 0; j < i; j++) {
                List<Double> next = new ArrayList<>(); //next数组存储第i和j个数的所有可能组合
                Double p1 = arr.get(i), p2 = arr.get(j);
                next.addAll(Arrays.asList(p1+p2, p1-p2, p2-p1, p1*p2)); //两数的加、减、乘，所有情况都包括了
                if(Math.abs(p2) > eps)  next.add(p1/p2);  //判断p2是否小于0.001（看作0），因为除数不能为0
                if(Math.abs(p1) > eps)  next.add(p2/p1);  //同理
                
                //将第i和j个数从arr数组中移去，尝试剩下的数字能否组成24
                arr.remove(i);
                arr.remove(j);
                for (Double n: next){ //一个一个尝试
                    arr.add(n);
                    helper(arr);
                    arr.remove(arr.size()-1);//将之前加上的数字从arr中再去除
                }
                //恢复数组中第i和j个数的值
                arr.add(j, p2);
                arr.add(i, p1);
            }
        }
    }

group[i] = 0 means node i hasn't been visited.
group[i] = 1 means node i has been grouped to 1.
group[i] = -1 means node i has been grouped to -1.

    public boolean possibleBipartition(int N, int[][] dislikes) {
        int[][] graph = new int[N][N];
        for (int[] d : dislikes) {  //建立有向图
            graph[d[0] - 1][d[1] - 1] = 1;
            graph[d[1] - 1][d[0] - 1] = 1;
        }
        int[] group = new int[N]; //每个人属于的组
        for (int i = 0; i < N; i++) {
            if (group[i] == 0 && !dfs(graph, group, i, 1)) { //当某个人没分组时，尝试将其进行分类，但实际上在dfs过程中，与该人相关的所有人都会被分类
                return false;
            }
        }
        return true;
    }
    
    private boolean dfs(int[][] graph, int[] group, int index, int g) { //index：当前标记的人 g:要将当前的人归为g组
        group[index] = g;
        for (int i = 0; i < graph.length; i++) {
            if (graph[index][i] == 1) {
                if (group[i] == g) { //有冲突，返回false
                    return false;
                }
                if (group[i] == 0 && !dfs(graph, group, i, -g)) {  //当前index的敌人也会被标记为与敌人不同的group，直到所有敌人都标记或者有冲突
                    return false;
                }
            }
        }
        return true;
    }

//DFS recursive遍历建树
public Node construct(int[][] g) { return build(0, 0, g.length - 1, g.length - 1, g);}

Node build(int r1, int c1, int r2, int c2, int[][] g) {
    if (r1 > r2 || c1 > c2) return null;
    boolean isLeaf = true;
    int val = g[r1][c1];
    for (int i = r1; i <= r2; i++)
        for (int j = c1; j <= c2; j++)  //判断在指定的区域内是否grid的值全部相同，若全相同则说明该层遍历的是叶子结点
            if (g[i][j] != val) {
                isLeaf = false;
                break;
            }
    if (isLeaf) //如果是叶子结点，它的四个孩子均为空，value值与cell的值相同
        return new Node(val == 1, true, null, null, null, null);
    int rowMid = (r1 + r2) / 2, colMid = (c1 + c2) / 2;
    //如果不是叶子结点，则将当前层传入的区域再划分为4块，分别是左上、右上、左下、右下，对应四个孩子
    return new Node(false, false,
            build(r1, c1, rowMid, colMid, g),//top left
            build(r1, colMid + 1, rowMid, c2, g),//top right
            build(rowMid + 1, c1, r2, colMid, g),//bottom left
            build(rowMid + 1, colMid + 1, r2, c2, g));//bottom right
}

// 下面的解法借用了StringBuilder，比较耗费时间，其实将相同的思路转化为算术运算效率和速度会更高
public List<Integer> lexicalOrder(int n) {
    List<Integer> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= 9; i++){
        sb.append(i);
        helper(n, 0, sb, res);
        sb.deleteCharAt(sb.length() - 1);
    }

    return res;
}

public void helper(int n, int start, StringBuilder sb, List<Integer> res){
    int value = Integer.valueOf(sb.toString());
    if(value > n)
        return;

    res.add(value);
    for (int i = start; i <= 9; i++){
        sb.append(i);
        helper(n, 0, sb, res);
        sb.deleteCharAt(sb.length() - 1);
    }
}

    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> res = new ArrayList<>();
        if(graph == null || graph.length == 0)  return res;

        int nodeCount = graph.length;
        int[] color = new int[nodeCount];

        for(int i = 0;i < nodeCount;i++){ //对每一个结点都遍历
            if(dfs(graph, i, color))    res.add(i);
        }

        return res;
    }

    // unsafe返回false，safe返回true
    public boolean dfs(int[][] graph, int start, int[] color){
        if(color[start] != 0)   return color[start] == 1;

        color[start] = 2; //先将它看成unsafe的，如果它与任何unsafe的结点都不相邻，那么再把它改成safe
        //注意，我们在这里不是用一个set集合去存储unsafe的结点，而是将其值设为2，查看它相邻的结点及相邻结点的相邻结点是否为unsafe(cycle)
        for(int newNode : graph[start]){
            if(!dfs(graph, newNode, color))    return false;
        }
        //如果相邻结点均为safe，或无相邻结点，则将其看作safe
        color[start] = 1;

        return true;
    }

    // 一个cell四周8个相邻cells的方向
    int[] dx = {-1, 0, 1, -1, 1, 0, 1, -1};
    int[] dy = {-1, 1, 1, 0, -1, -1, 0, 1};
    public char[][] updateBoard(char[][] board, int[] click) {
        int x = click[0], y = click[1];
        // 1. If a mine ('M') is revealed, then the game is over - change it to 'X'.
        if(board[x][y] == 'M'){
            board[x][y] = 'X';
            return board;
        }
        // 2. If an empty square ('E') with no adjacent mines is revealed, then change it to revealed
        // blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
        // 3. If an empty square ('E') with at least one adjacent mine is revealed, then change it to a
        // digit ('1' to '8') representing the number of adjacent mines.
        // 因为当一个cell是空时，需要递归遍历其相邻的cell，所以将2、3点合到一起写
        dfs(board, x, y);

        // 4. Return the board when no more squares will be revealed.
        return board;
    }

    public void dfs(char[][] board, int x, int y){
        int m = board.length, n = board[0].length;
        //我们只处理没有reveal和在board内的cell
        if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'E')
            return;

        int num = numOfAdjacentMines(board, x, y);

        // 1. No adjacent mine
        if(num == 0){
            board[x][y] = 'B';
            // recursively处理相邻未reveal的cell
            for(int i = 0; i < 8; i++){
                int newX = x + dx[i], newY = y + dy[i];
                dfs(board, newX, newY);
            }
        }
        else { // 2. At least one adjacent mine
            board[x][y] = (char)('0' + num);
        }
    }

    public int numOfAdjacentMines(char[][] board, int x, int y){
        int num =0, m = board.length, n = board[0].length;
        for(int i = 0; i < 8; i++){
            int newX = x + dx[i], newY = y + dy[i];
            if(newX < 0 || newX >= m || newY < 0 || newY >= n)
                continue;
            // 我们在计算相邻的雷时，已经reveal和没有reveal的都应该考虑
            if(board[newX][newY] == 'M' || board[newX][newY] == 'X')
                num++;
        }
        return num;
    }

    private int id;
    private int[] ids;
    private int[] low;
    private List<Integer>[] graph;

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> bridges = new ArrayList<>();
        graph = buildGraph(n, connections); //用领接链表建树
        // ids在一些解法当中被称作discovery time，但若这样理解，与下面low的含义有些许冲突，我们不妨将其理解为id，但id是按发现的时间进行赋值的
        // 即发现时间为the time that this vertex was discovered - useful to identify when a child vertex can reach its parents ancestors
        ids = new int[n + 1];
        // to check the lowest vertex that this node can reach "through" its children,我们用low数组来追踪当前的结点通过访问其children可达的最小的id
        low = new int[n + 1];
        id = 1; //id(discovery time)从1开始，将id为0作为visited的标志
        visit(1, -1, bridges); //DFS tree根节点的parent是-1
        return bridges;
    }

    private void visit(int node, int parent, List<List<Integer>> bridges) {
        low[node] = ids[node] = id++; //我们将结点的low值初始化为当前的id值，认为其他结点访问自己的同时，肯定对自己也可达，在之后的过程中进行low的更新
        for (int child : graph[node]) {
            if (child == parent) continue; //我们不考虑child通过访问自己的parent可达结点的情况
            if (ids[child] == 0) { // not visited
                visit(child, node, bridges); //在dfs访问child结点的过程后，其low会更新为该child可以连接到的最小值
                low[node] = Math.min(low[node], low[child]);
                if (ids[node] < low[child]) { //当low[child]比ids[node]大时，说明child是访问不到node的祖先的，只能访问到自己
                    bridges.add(Arrays.asList(node, child));
                }
            } else {
                low[node] = Math.min(low[node], ids[child]); //对于已经访问过的结点，可能其id要比当前node的parent还小，并且通过该结点可达
            }
        }
    }

    private List<Integer>[] buildGraph(int n, List<List<Integer>> edges) {
        List<Integer>[] graph = new List[n + 1];
        for(int i = 0; i < graph.length; i++)
            graph[i] = new ArrayList<>();
        for (List<Integer> edge : edges) {
            int u = edge.get(0);
            int v = edge.get(1);
            graph[u].add(v);
            graph[v].add(u);
        }
        return graph;
    }

    public int shortestBridge(int[][] A) {
        int m = A.length, n = A[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Queue<int[]> q = new LinkedList<>();
        boolean found = false;
        // 1. dfs to find an island, mark it in `visited`，因为输入的矩阵当中有两个island，我们只在dfs的过程当中标记一个island
        for (int i = 0; i < m; i++) {
            if (found) {
                break;
            }
            for (int j = 0; j < n; j++) {
                if (A[i][j] == 1) {
                    dfs(A, visited, q, i, j, dirs);
                    found = true;
                    break;
                }
            }
        }

        // 2. bfs to expand this island，然后去搜索第二个island
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                int[] cur = q.poll();
                for (int[] dir : dirs) {
                    int i = cur[0] + dir[0];
                    int j = cur[1] + dir[1];
                    if (i >= 0 && j >= 0 && i < m && j < n && !visited[i][j]) {
                        if (A[i][j] == 1) {
                            return step;
                        }
                        q.offer(new int[]{i, j});
                        visited[i][j] = true;
                    }
                }
            }
            step++;
        }
        return -1;
    }

    private void dfs(int[][] A, boolean[][] visited, Queue<int[]> q, int i, int j, int[][] dirs) {
        if (i < 0 || j < 0 || i >= A.length || j >= A[0].length || visited[i][j] || A[i][j] == 0) {
            return;
        }
        visited[i][j] = true;
        q.offer(new int[]{i, j});
        for (int[] dir : dirs) {
            dfs(A, visited, q, i + dir[0], j + dir[1], dirs);
        }
    }