skymiles

Alibaba

1.2万

### 题目描述

#### 样例

提示：

graph 节点数不超过 10000.



### 算法

#### 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++) {
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);
}
}

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);
}
}
}
}
}

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


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);
}
}
}

}


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<>());
return res;
}

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

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]) {
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 {

return null;
}

}

// 返回按条件搜索的最尾端节点
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;
}
}
}


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) {
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)) {
}
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) {
}

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

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



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
// 入度+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++;
}
}