头像

skymiles

Alibaba




离线:2小时前



题目描述

找到最终的安全状态
在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。

现在, 如果我们最后能走到终点,那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。

哪些节点最终是安全的? 结果返回一个有序的数组。

该有向图有 N 个节点,标签为 0, 1, …, N-1, 其中 N 是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表,满足 (i, j) 是图的一条有向边。

样例

示例:
输入:graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出:[2,4,5,6]
这里是上图的示意图。

demo.png

提示:

graph 节点数不超过 10000.
图的边数不会超过 32000.
每个 graph[i] 被排序为不同的整数列表, 在区间 [0, graph.length - 1] 中选取。


算法

(拓扑排序)

这道题一乍看没啥思路,但是反向看,从最终安全的点反向找源点,看如果有环或者走不到某个源点,那么这个点就不是安全点。这就很容易想到拓扑排序,反向建图,进行拓扑排序,把入度为0的点加入答案中。

时间复杂度 O(M+N)

Java 代码

class Solution {
    int N = 10001;
    int M = 32001;
    int n = 0;
    int idx = 0;
    int[] h = new int[N];
    int[] e = new int[M];
    int[] next = new int[M];
    int[] d = new int[N];
    Queue<Integer> q = new ArrayDeque<>();
    List<Integer> res = new ArrayList<>();

    // O(m+n)
    public List<Integer> eventualSafeNodes(int[][] graph) {
        Arrays.fill(h, -1);
        n = graph.length;
        // 反向建图
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                add(graph[i][j], i);
                d[i]++;
            }
        }

        topologicalSort();
        return res.stream().sorted().collect(Collectors.toList());
    }

    private void topologicalSort() {
        // 所有点入度为0 加入队列
        for (int v = 0; v < n; v++) {
            if (d[v] == 0) {
                q.offer(v);
                res.add(v);
            }
        }

        while (!q.isEmpty()) {
            int levelSize = q.size();
            for (int k = 0; k < levelSize; k++) {
                Integer t = q.poll();
                for (int i = h[t]; i != -1; i = next[i]) {
                    // 从点t作为原点span的点j
                    int j = e[i];
                    if (--d[j] == 0) {
                        q.offer(j);
                        res.add(j);
                    }
                }
            }
        }
    }

    private void add(int a, int b) {
        e[idx] = b;
        next[idx] = h[a];
        h[a] = idx++;
    }
}


活动打卡代码 LeetCode 547. 朋友圈

class Solution {
    int n = 0;
    int res = 0;
    boolean[] visited = null;

    // 方法1:DFS求连通分量
    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0) {
            return 0;
        }

        n = M.length;
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(M, i);
                res++;
            }
        }
        return res;
    }

    private void dfs(int[][] M, int u) {
        if (visited[u]) {
            return;
        }
        visited[u] = true;
        for (int j = 0; j < n; j++) {
            if (M[u][j] == 1) {
                dfs(M, j);
            }
        }
    }

}


活动打卡代码 LeetCode 491. 递增子序列

public class Solution {

    List<List<Integer>> res = new ArrayList<>();
    Set<List<Integer>> set = new HashSet<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums == null || nums.length == 0) {
            return res;
        }

        dfs(nums, 0, 0, new ArrayList<>());
        res.addAll(set);
        return res;
    }

    private void dfs(int[] nums, int u, int start, List<Integer> path) {
        // 类似subset,每个中间节点都是答案,都需要存储,所以不能dfs到最下面一层才计算答案
        if (path.size() >= 2) {
            set.add(new ArrayList<>(path));
        }

        if (u == nums.length) {
            return;
        }

        // 尝试每个数字加入当前位子
        for (int i = start; i < nums.length; i++) {

            int size = path.size();
            if (size == 0 || path.get(size - 1) <= nums[i]) {
                path.add(nums[i]);
                dfs(nums, u + 1, i + 1, path);
                path.remove(path.size() - 1);
            }
        }
    }
}




class Solution {
    // 剪枝
    // 1. 从大到小枚举所有边
    // 2. 每条边的内部木棍长度从大到小填
    // 3. 如果当前木棍填充失败,那么跳过接下来所有相同长度的木棍
    // 4. 如果当前木棍填充失败,并且是当前边的第一个,则直接剪掉当前分支
    // 5. 如果当前木棍填充失败,并且是当前边的最后一个,则直接剪掉当前分支

    private int n = 0;
    private boolean[] visited = null;

    public boolean makesquare(int[] nums) {
        n = nums.length;
        if (n == 0) {
            return false;
        }
        visited = new boolean[n];
        nums = IntStream.of(nums).boxed().sorted(Comparator.reverseOrder()).mapToInt(Integer::intValue).toArray();
        int sum = IntStream.of(nums).sum();
        if (sum % 4 != 0 || nums[0] > sum / 4) {
            return false;
        }
        // 参数:枚举每条边。每条边当前的长度,以及每条边应该最终达到的长度
        return dfs(nums, 0, 0, sum / 4);
    }

    private boolean dfs(int[] nums, int u, int curLen, int singleLen) {
        // 拼好一条边
        if (curLen == singleLen) {
            u++;
            curLen = 0;
        }
        // 拼好所有边
        if (u == 4) {
            return true;
        }

        // 尝试每个木棍
        for (int i = 0; i < n; i++) {
            if (!visited[i] && curLen + nums[i] <= singleLen) {
                visited[i] = true;
                // 加入当前边
                if (dfs(nums, u, curLen + nums[i], singleLen)) {
                    return true;
                }
                visited[i] = false;

                // 第三个剪枝,如果当前木棍填充失败,那么跳过接下来所有相同长度的木棍
                while (i + 1 < n && nums[i + 1] == nums[i]) {
                    i++;
                }

                // 第四个剪枝,如果当前木棍填充失败,并且是当前边的第一个,则直接剪掉当前分支
                if (curLen == 0) {
                    return false;
                }

                // 第五个剪枝,如果当前木棍填充失败,并且是当前边的最后一个,则直接剪掉当前分支
                if (curLen + nums[i] == singleLen) {
                    return false;
                }
            }
        }
        return false;
    }

}




class Solution {

    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }

        dfs(head);
        return head;
    }

    // 返回按条件搜索的最尾端节点
    private Node dfs(Node node) {
        if (node == null) {
            return null;
        }

        Node next = node.next;
        Node child = node.child;
        // 一定要置空child,因为会展开
        node.child = null;

        if (child != null && next != null) {
            Node childEnd = dfs(child);
            Node nextEnd = dfs(next);

            node.next = child;
            child.prev = node;

            childEnd.next = next;
            next.prev = childEnd;

            return nextEnd;
        } else if (next != null && child == null) {
            return dfs(next);
        } else if (child != null && next == null) {
            Node childEnd = dfs(child);
            node.next = child;
            child.prev = node;
            return childEnd;
        } else {
            return node;
        }
    }
}


活动打卡代码 LeetCode 394. 字符串解码

public class Solution {

    private int u = 0;

    public String decodeString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        StringBuilder path = new StringBuilder();
        dfs(s, path);
        return path.toString();
    }

    private void dfs(String s, StringBuilder path) {
        int k = 0;
        while (u < s.length()) {
            char ch = s.charAt(u);
            u++;
            if (Character.isDigit(ch)) {
                k = k * 10 + (ch - '0');
            } else if (ch == '[') {
                // 求解子问题,为什么要new?因为子问题的解乏
                StringBuilder subPath = new StringBuilder();
                dfs(s, subPath);
                String sub = subPath.toString();
                do {
                    path.append(sub);
                } while (--k > 0);
            } else if (ch == ']') {
                // 跳出循环,返回上一次调用
                break;
            } else {
                path.append(ch);
            }
        }
    }

}




class Solution {
    int m = 0;
    int n = 0;
    int res = 1;
    int[][] memo = null;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null) {
            return 0;
        }
        m = matrix.length;
        n = matrix[0].length;
        memo = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int subLen = dfs(matrix, i, j);
                res = Math.max(res, subLen);
            }
        }
        return res;
    }

    // 以(i,j)作为起点寻找最长子路径值是固定的所以可以记忆化
    private int dfs(int[][] matrix, int row, int col) {
        if (memo[row][col] > 0) {
            return memo[row][col];
        }
        int subLen = 1;
        for (int i = 0; i < 4; i++) {
            int x = row + dx[i];
            int y = col + dy[i];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[row][col]) {
                // 1 + dfs(matrix, x, y)会走4次,上下左右,所以要取得一个方向最大的值
                subLen = Math.max(subLen, 1 + dfs(matrix, x, y));
            }
        }
        memo[row][col] = subLen;
        return subLen;
    }

}



class Solution {

    List<String> res = new ArrayList<>();

    public List<String> removeInvalidParentheses(String s) {
        if (s == null || s.length() == 0) {
            res.add("");
            return res;
        }
        // 统计待删除左右括号数目
        int rmL = 0, rmR = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                rmL++;
            } else if (ch == ')') {
                if (rmL == 0) {
                    rmR++;
                } else {
                    rmL--;
                }
            }
        }

        dfs(new StringBuilder(s), 0, rmL, rmR);
        return res;
    }

    // l/r: number of left/right parentheses to remove.
    // "(()))"
    private void dfs(StringBuilder sb, int u, int rmL, int rmR) {
        if (rmL < 0 || rmR < 0) {
            return;
        }
        if (rmL == 0 && rmR == 0) {
            if (isValid(sb)) {
                res.add(new String(sb));
            }
            return;
        }

        int n = sb.length();
        for (int i = u; i < n; i++) {
            if (sb.charAt(i) != '(' && sb.charAt(i) != ')') {
                continue;
            }

            // We only remove the first parentheses if there are consecutive ones to avoid duplications.
            if (i != u && sb.charAt(i) == sb.charAt(i - 1)) {
                continue;
            }
            // copy一份sb,删除i为半括号,i表示当前删除半括号的位置
            StringBuilder cur = new StringBuilder(sb);
            cur.deleteCharAt(i);
            // 还有')',递归删除')'
            if (sb.charAt(i) == ')' && rmR > 0) {
                dfs(cur, i, rmL, rmR - 1);
            }
            // 还有'(',递归删除'('
            if (sb.charAt(i) == '(' && rmL > 0) {
                dfs(cur, i, rmL - 1, rmR);
            }
        }
    }

    private boolean isValid(StringBuilder sb) {
        int cnt = 0;
        int n = sb.length();
        for (int i = 0; i < n; i++) {
            char ch = sb.charAt(i);
            if (ch == '(') {
                cnt++;
            }
            if (ch == ')') {
                cnt--;
            }
            if (cnt < 0) {
                return false;
            }
        }
        return cnt == 0;
    }

}



skymiles
10天前
public class Solution {

    List<String> res = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) {
            return res;
        }

        dfs(root, "");
        return res;
    }

    private void dfs(TreeNode root, String path) {
        if (root == null) {
            return;
        }

        path += root.val;

        // leaf
        if (root.left == null && root.right == null) {
            res.add(path);
        }

        if (root.left != null) {
            dfs(root.left, path + "->");
        }

        if (root.right != null) {
            dfs(root.right, path + "->");
        }
    }
}



活动打卡代码 LeetCode 210. 课程表 II

skymiles
10天前
class Solution {
    int N = 100001, idx = 0, resIdx = 0, n = 0;
    int[] h = new int[N];
    int[] e = new int[N];
    int[] next = new int[N];
    int[] d = new int[N];   // 入度
    int[] res = null;       // 结果
    Queue<Integer> q = null;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        n = numCourses;
        q = new ArrayDeque<>(n);
        res = new int[n];
        Arrays.fill(h, -1);

        for (int i = 0; i < prerequisites.length; i++) {
            int a = prerequisites[i][1];
            int b = prerequisites[i][0];
            // 添加一条边a->b
            add(a, b);
            // 入度+1
            d[b]++;
        }

        if (topologicalSort()) {
            return res;
        } else {
            return new int[] {};
        }
    }

    private boolean topologicalSort() {
        // 这里v是节点的值
        for (int v = 0; v < n; v++) {
            if (d[v] == 0) {
                q.offer(v);
            }
        }

        while (!q.isEmpty()) {
            //队列不空,则取出头节点,表示入度为0的节点
            Integer t = q.poll();
            if (t == null) {
                continue;
            }
            res[resIdx++] = t;
            // 遍历头节点的每一个出边,这里i表示出边节点下标
            for (int i = h[t]; i != -1; i = next[i]) {
                // j表示节点的值
                int j = e[i];
                //出边能到达的节点,入度减1
                //如果结点j,入度为0则入队
                if (--d[j] == 0) {
                    q.offer(j);
                }
            }
        }

        return resIdx == n;
    }

    // 添加一条边a->b
    private void add(int a, int b) {
        e[idx] = b;
        next[idx] = h[a];
        h[a] = idx;
        idx++;
    }
}