欢迎大家加QQ群：623375442，可以方便群里面交流。
100381. Find the Number of Winning Players
给你一个整数 n ，表示在一个游戏中的玩家数目。同时给你一个二维整数数组 pick ，其中 pick[i] = [xi, yi] 表示玩家 xi 获得了一个颜色为 yi 的球。
如果玩家 i 获得的球中任何一种颜色球的数目 严格大于 i 个，那么我们说玩家 i 是胜利玩家。换句话说：
- 如果玩家 0 获得了任何的球，那么玩家 0 是胜利玩家。
- 如果玩家 1 获得了至少 2 个相同颜色的球，那么玩家 1 是胜利玩家。
- ...
- 如果玩家 i 获得了至少 i + 1 个相同颜色的球，那么玩家 i 是胜利玩家。
请你返回游戏中 胜利玩家 的数目。
注意，可能有多个玩家是胜利玩家。
测试样例：
输入：n = 4, pick = [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]
输出：2
解释：玩家 0 和玩家 1 是胜利玩家，玩家 2 和玩家 3 不是胜利玩家。
解答：暴力统计一下每个选手的拿球次数，最后判断下每个选手是否成功。
class Solution {
public int winningPlayerCount(int n, int[][] pick) {
int[][] mem = new int[n][11];
for (int[] p : pick) {
mem[p[0]][p[1]] += 1;
}
int res = 0;
for (int i = 0; i < n; ++i) {
boolean isValid = false;
for (int j = 0; j <= 10; ++j) {
if (mem[i][j] >= i + 1) {
isValid = true;
}
}
if (isValid) {
++res;
}
}
return res;
}
}100387. Minimum Number of Flips to Make Binary Grid Palindromic I
给你一个 m x n 的二进制矩阵 grid 。
如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。
你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。
请你返回 最少 翻转次数，使得矩阵 要么 所有行是 回文的 ，要么所有列是 回文的 。
测试样例：
输入：grid = [[1,0,0],[0,0,0],[0,0,1]]
输出：2
解释：最少2次，得到所有行都是回文的。
解答：暴力枚举一下，按行和按列最小反转次数。然后再取小的那一个。
class Solution {
public int minFlips(int[][] grid) {
int m = grid.length, n = grid[0].length;
int bestRow = 0;
for (int i = 0; i < m; ++i) {
int st = 0, ed = n - 1;
while (st < ed) {
if (grid[i][st] != grid[i][ed]) {
++bestRow;
}
++st;
--ed;
}
}
int bestCol = 0;
for (int i = 0; i < n; ++i) {
int st = 0, ed = m - 1;
while (st < ed) {
if (grid[st][i] != grid[ed][i]) {
++bestCol;
}
++st;
--ed;
}
}
return Math.min(bestCol, bestRow);
}
}100385. Minimum Number of Flips to Make Binary Grid Palindromic II
给你一个 m x n 的二进制矩阵 grid 。
如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。
你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。
请你返回 最少 翻转次数，使得矩阵中 所有 行和列都是 回文的 ，且矩阵中 1 的数目可以被 4 整除 。
测试样例：
输入：grid = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
解释：将斜对角线反转就能达到目标。
解答：需要被4整除，所以想到利用DP计算。首先利用并查集（这个是我偷懒了），寻找到数字必须相同的小组。然后利用DP来判断，这个小组反转的2种可能性，对DP数组的变化。
class Solution {
class DSU{
int[] parent;
int[] countTotal, countOri;
public DSU(int n, int[][] grid) {
parent = new int[n];
countTotal = new int[n];
countOri = new int[n];
for (int i = 0; i < n; ++i) {
parent[i] = i;
countTotal[i] = 1;
countOri[i] = grid[i / grid[0].length][i % grid[0].length];
}
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
parent[fx] = fy;
countTotal[fy] += countTotal[fx];
countOri[fy] += countOri[fx];
}
}
}
public int minFlips(int[][] grid) {
int m = grid.length, n = grid[0].length;
DSU uf = new DSU(m * n, grid);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 寻找需要相同的小组
uf.union(i * n + j, (m - 1 - i) * n + j);
uf.union(i * n + j, i * n + (n - 1 - j));
}
}
int[] mem = new int[4];
Arrays.fill(mem, Integer.MAX_VALUE);
mem[0] = 0;
boolean[] isUsed = new boolean[m * n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int f = uf.find(i * n + j);
if (!isUsed[f]) {
int turnZero = uf.countOri[f], turnOne = uf.countTotal[f] - uf.countOri[f];
int[] nextMem = new int[4];
Arrays.fill(nextMem, Integer.MAX_VALUE);
isUsed[f] = true;
// 判断统一是0，或者统一是1对DP数组的影响。
for (int k = 0; k < 4; ++k) {
if (mem[k] != Integer.MAX_VALUE) {
nextMem[k] = Math.min(nextMem[k], mem[k] + turnZero);
nextMem[(k + uf.countTotal[f]) % 4] = Math.min(nextMem[(k + uf.countTotal[f]) % 4], mem[k] + turnOne);
}
}
mem = nextMem;
}
}
}
return mem[0];
}
}100392. Time Taken to Mark All Nodes
给你一棵 无向 树，树中节点从 0 到 n - 1 编号。同时给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 在树中有一条边。
一开始，所有 节点都 未标记 。对于节点 i ：
- 当 i 是奇数时，如果时刻 x - 1 该节点有 至少 一个相邻节点已经被标记了，那么节点 i 会在时刻 x 被标记。
- 当 i 是偶数时，如果时刻 x - 2 该节点有 至少 一个相邻节点已经被标记了，那么节点 i 会在时刻 x 被标记。
请你返回一个数组 times ，表示如果你在时刻 t = 0 标记节点 i ，那么时刻 times[i] 时，树中所有节点都会被标记。
请注意，每个 times[i] 的答案都是独立的，即当你标记节点 i 时，所有其他节点都未标记。
测试样例：
输入：edges = [[0,1],[0,2]]
输出：[2,4,3]
解释：
- 对于 i = 0 ：
- 节点 1 在时刻 t = 1 被标记，节点 2 在时刻 t = 2 被标记。
- 对于 i = 1 ：
- 节点 0 在时刻 t = 2 被标记，节点 2 在时刻 t = 4 被标记。
- 对于 i = 2 ：
- 节点 0 在时刻 t = 2 被标记，节点 1 在时刻 t = 3 被标记。
解答：模版题了，具体可以参考834. Sum of Distances in Tree。
class Solution {
private class InternalData {
private int len;
private List<Integer>[] edges;
private int[] zero, res;
public InternalData(int[][] _edges) {
len = _edges.length + 1;
edges = new List[len];
for (int i = 0; i < len; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
zero = new int[len];
dfsZero(0, -1);
res = new int[len];
}
private int dfsZero(int cur, int pre) {
int initial = cur == 0 ? 0 : add(cur);
int tmp = 0;
for (int n : edges[cur]) {
if (n != pre) {
tmp = Math.max(dfsZero(n, cur), tmp);
}
}
zero[cur] = initial + tmp;
return zero[cur];
}
public void findRes() {
findRes(0, -1, 0);
}
private void findRes(int cur, int pre, int lastBest) {
int initial = add(cur);
if (cur == 0) {
res[0] = zero[0];
} else {
res[cur] = Math.max(lastBest, zero[cur] - initial);
}
int[][] max = new int[2][2];
swapMax(max, pre, lastBest);
for (int n : edges[cur]) {
if (n != pre) {
swapMax(max, n, zero[n]);
}
}
for (int n : edges[cur]) {
if (n != pre) {
if (n == max[0][0]) {
findRes(n, cur, max[1][1] + initial);
} else {
findRes(n, cur, max[0][1] + initial);
}
}
}
}
private int add(int num) {
int initial;
if (num % 2 == 0) {
initial = 2;
} else {
initial = 1;
}
return initial;
}
private void swapMax(int[][] max, int num, int length) {
if (length > max[0][1]) {
max[1][0] = max[0][0];
max[1][1] = max[0][1];
max[0][0] = num;
max[0][1] = length;
} else if (length > max[1][1]) {
max[1][0] = num;
max[1][1] = length;
}
}
}
public int[] timeTaken(int[][] _edges) {
InternalData data = new InternalData(_edges);
data.findRes();
return data.res;
}
}