100115. Find Champion I
一场比赛中共有 n 支队伍，按从 0 到 n - 1 编号。
给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 <= i, j <= n - 1 且 i != j 的所有 i, j ：如果 grid[i][j] == 1，那么 i 队比 j 队 强 ；否则，j 队比 i 队 强 。
在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是 冠军 。
返回这场比赛中将会成为冠军的队伍。
测试样例：
输入：grid = [[0,1],[0,0]]
输出：0
解释：
比赛中有两支队伍。
grid[0][1] == 1 表示 0 队比 1 队强。所以 0 队是冠军。
解答：这题就是利用暴力运算，查看那支队可以打败所有其他队伍，即sum(row[i]) == n - 1
class Solution {
public int findChampion(int[][] grid) {
int n = grid.length;
for (int i = 0; i < n; ++i) {
int add = 0;
for (int j = 0; j < n; ++j) {
if (j != i) {
add += grid[i][j];
}
}
if (add == n - 1) {
return i;
}
}
return -1;
}
}100116. Find Champion II
一场比赛中共有 n 支队伍，按从 0 到 n - 1 编号。每支队伍也是 有向无环图（DAG） 上的一个节点。
给你一个整数 n 和一个下标从 0 开始、长度为 m 的二维整数数组 edges 表示这个有向无环图，其中 edges[i] = [ui, vi] 表示图中存在一条从 ui 队到 vi 队的有向边。
从 a 队到 b 队的有向边意味着 a 队比 b 队 强 ，也就是 b 队比 a 队 弱 。
在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是 冠军 。
如果这场比赛存在 唯一 一个冠军，则返回将会成为冠军的队伍。否则，返回 -1 。
注意
- 环 是形如 a1, a2, ..., an, an+1 的一个序列，且满足：节点 a1 与节点 an+1 是同一个节点；节点 a1, a2, ..., an 互不相同；对于范围 [1, n] 中的每个 i ，均存在一条从节点 ai 到节点 ai+1 的有向边。
- 有向无环图 是不存在任何环的有向图。
测试样例：
输入：n = 3, edges = [[0,1],[1,2]]
输出：0
解释：
1 队比 0 队弱。2 队比 1 队弱。所以冠军是 0 队。
解答：这道题目范围比较小，其实暴力DFS就行了。注意存在环的情况（没认真看题，WA几次。。。）
class Solution {
public int findChampion(int n, int[][] _edges) {
List<Integer>[] edges = new List[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
}
for (int i = 0; i < n; ++i) {
if (isValid(i, edges)) {
return i;
}
}
return -1;
}
private boolean isValid(int pos, List<Integer>[] edges) {
Set<Integer> set = new HashSet<>();
dfs(pos, edges, set);
return set.size() == edges.length;
}
private void dfs(int pos, List<Integer>[] edges, Set<Integer> set) {
if (set.contains(pos)) {
return;
}
set.add(pos);
for (int n : edges[pos]) {
dfs(n, edges, set);
}
}
}100118. Maximum Score After Applying Operations on a Tree
有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 ，根节点编号为 0 。给你一个长度为 n - 1 的二维整数数组 edges 表示这棵树，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 有一条边。
同时给你一个长度为 n 下标从 0 开始的整数数组 values ，其中 values[i] 表示第 i 个节点的值。
一开始你的分数为 0 ，每次操作中，你将执行：
- 选择节点 i 。
- 将 values[i] 加入你的分数。
- 将 values[i] 变为 0 。
如果从根节点出发，到任意叶子节点经过的路径上的节点值之和都不等于 0 ，那么我们称这棵树是 健康的 。
你可以对这棵树执行任意次操作，但要求执行完所有操作以后树是 健康的 ，请你返回你可以获得的 最大分数 。
测试样例：
输入：edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
输出：11
解释：
我们可以选择节点 1 ，2 ，3 ，4 和 5 。根节点的值是非 0 的。所以从根出发到任意叶子节点路径上节点值之和都不为 0 。所以树是健康的。你的得分之和为 values[1] + values[2] + values[3] + values[4] + values[5] = 11 。
11 是你对树执行任意次操作以后可以获得的最大得分之和。
解答：这道题目需要利用到动态规划，当前节点如果放弃加入分数，则剩下的所有分支都能加入分数。如果当前节点加入分数，那么剩下节点，就需要看情况计算了。利用动态规划记录当前节点的2种状态。
class Solution {
private List<Integer>[] edges;
private int[] values;
private Long[][] mem;
public long maximumScoreAfterOperations(int[][] _edges, int[] values) {
this.edges = new List[values.length];
for (int i = 0; i < values.length; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
this.values = values;
mem = new Long[values.length][2];
return dfs(0, 0, 0);
}
private long dfs(int pos, int status, int last) {
if (status == 0 && edges[pos].size() == 1 && pos != 0) {
return 0;
} else if (mem[pos][status] == null) {
if (status == 1) {
mem[pos][status] = (long) values[pos];
for (int n : edges[pos]) {
if (n != last) {
mem[pos][status] += dfs(n, status, pos);
}
}
} else {
long n1 = 0, n2 = values[pos];
for (int n : edges[pos]) {
if (n != last) {
n1 += dfs(n, 1, pos);
n2 += dfs(n, 0, pos);
}
}
mem[pos][0] = Math.max(n1, n2);
}
}
return mem[pos][status];
}
}100112. Maximum Balanced Subsequence Sum
给你一个下标从 0 开始的整数数组 nums 。
nums 一个长度为 k 的 子序列 指的是选出 k 个 下标 i0 < i1 < ... < ik-1 ，如果这个子序列满足以下条件，我们说它是 平衡的 ：
- 对于范围 [1, k - 1] 内的所有 j ，nums[ij] - nums[ij-1] >= ij - ij-1 都成立。
nums 长度为 1 的 子序列 是平衡的。
请你返回一个整数，表示 nums 平衡 子序列里面的 最大元素和 。
一个数组的 子序列 指的是从原数组中删除一些元素（也可能一个元素也不删除）后，剩余元素保持相对顺序得到的 非空 新数组。
测试样例
输入：nums = [3,3,5,6]
输出：14
解释：
这个例子中，选择子序列 [3,5,6] ，下标为 0 ，2 和 3 的元素被选中。
nums[2] - nums[0] >= 2 - 0 。
nums[3] - nums[2] >= 3 - 2 。
所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。
包含下标 1 ，2 和 3 的子序列也是一个平衡的子序列。
最大平衡子序列和为 14 。
解答：nums[ij] - nums[ij-1] >= ij - ij-1可以变成nums[ij] - ij >= nums[ij-1] - ij-1。这样每个位置只需要查看nums[i] - i的值，然后保证之前的nums[i] - i只能是单调递增。可以利用线段数来简化coding，这样就能一边遍历，一边动态的变化最大值。
class Solution {
private class SegmentTree {
long[] tree;
int n;
public SegmentTree(int n) {
if (n > 0) {
this.n = n;
tree = new long[n * 2];
}
}
public void update(int pos, long val) {
pos += n;
tree[pos] = val;
while (pos > 0) {
int left = pos;
int right = pos;
if (pos % 2 == 0) {
right = pos + 1;
} else {
left = pos - 1;
}
tree[pos / 2] = Math.max(tree[left], tree[right]);
pos /= 2;
}
}
public long maxRange(int r) {
int l = n;
r += n;
long max = Long.MIN_VALUE;
while (l <= r) {
if ((l % 2) == 1) {
max = Math.max(max, tree[l]);
l++;
}
if ((r % 2) == 0) {
max = Math.max(tree[r], max);
r--;
}
l /= 2;
r /= 2;
}
return max;
}
}
public long maxBalancedSubsequenceSum(int[] nums) {
int len = nums.length;
int[] diff = new int[len];
for (int i = 0; i < len; ++i) {
diff[i] = nums[i] - i;
}
Map<Integer, Integer> sortMap = sort(diff);
long res = Long.MIN_VALUE;
SegmentTree tree = new SegmentTree(len);
for (int i = 0; i < len; ++i) {
int curDiff = diff[i];
int offset = sortMap.get(curDiff);
long oldMax = tree.maxRange(offset);
res = Math.max(oldMax + nums[i], res);
long updateMax = Math.max(oldMax, oldMax + nums[i]);
tree.update(offset, updateMax);
}
return res;
}
private Map<Integer, Integer> sort(int[] diff) {
TreeSet<Integer> set = new TreeSet<>();
for (int n : diff) {
set.add(n);
}
int offset = 0;
Map<Integer, Integer> res = new HashMap<>();
for (int n : set) {
res.put(n, offset++);
}
return res;
}
}