Leetcode - 136双周赛

目录

一，3238. 求出胜利玩家的数目

二，3239. 最少翻转次数使二进制矩阵回文 I

三，3240. 最少翻转次数使二进制矩阵回文 II

四，3241. 标记所有节点需要的时间

---

一，3238. 求出胜利玩家的数目

本题直接暴力求解，使用一个二维数组存储每个玩家获得每一种颜色球的数量，在检查玩家i是否有一种颜色的球的数量大于 i ，代码如下：

class Solution {public int winningPlayerCount(int n, int[][] pick) {int[][] cnt = new int[n][11];for(int[] x : pick){cnt[x[0]][x[1]]++;}int ans = 0;for(int i=0; i<n; i++){for(int j=0; j<11; j++){if(cnt[i][j] > i){ans++;break;}}}return ans;}
}

二，3239. 最少翻转次数使二进制矩阵回文 I

本题求最少翻转次数且所有行（row）或 所有列（col）是回文的，我们可以分别求两者回文的翻转次数，最后返回最小值，代码如下：

class Solution {public int minFlips(int[][] grid) {int n = grid.length, m = grid[0].length;int row = 0;for(int i=0; i<n; i++){for(int j=0; j<m/2; j++){if(grid[i][j] != grid[i][m-j-1]){row++;}}}int col = 0;for(int j=0; j<m; j++){for(int i=0; i<n/2; i++){if(grid[i][j] != grid[n-i-1][j]){col++;}}}return Math.min(row, col);}
}

三，3240. 最少翻转次数使二进制矩阵回文 II

本题要求所有的行和列都是回文的且矩阵中1的数目可以被4整除，画个图理解一下：

特殊情况——行为奇（n%2==1），列为奇（m%2==1）

• 如果行列都为奇数，那么中心点一定为0（如果它是1，那么矩阵中1的个数一定是奇数，就不满足整除4的条件）

我们需要 tmp 和 cnt 分别统计正中间一列和正中间一列中不回文的对数，以及回文时1的个数。

• 如果cnt%4 = 0，那么我们只需要额外操作 tmp 次，将不回文的全改成0就行
• 如果cnt%4 != 0，那么cnt%4就只能等于2（统计的都是对称的，即一定是偶数），如果tmp>0，只需要操作 tmp 次，1次将0->1，tmp-1次将1->0（可以获得2个1）；如果 tmp = 0，那么只需要操作cnt%4次（即2次），将多出来的1->0

总上所述：tmp > 0，额外操作 tmp 次；否则，操作 cnt%4 次

 

class Solution {public int minFlips(int[][] grid) {int n = grid.length, m = grid[0].length;int ans = 0;for(int i=0; i<n/2; i++){for(int j=0; j<m/2; j++){int cnt = grid[i][j] + grid[n-i-1][j] + grid[i][m-j-1] + grid[n-i-1][m-j-1];ans += Math.min(4-cnt, cnt);//Math.min(0->1, 1->0)}}int tmp = 0, cnt = 0;if(n%2==1 && m%2==1){ans += grid[n/2][m/2];//中心点必须为0}if(n%2 == 1){for(int j=0; j<m/2; j++){if(grid[n/2][j] != grid[n/2][m-j-1])//不回文的对数tmp++;elsecnt += grid[n/2][j]*2;//回文时1的个数}}if(m%2 == 1){for(int i=0; i<n/2; i++){if(grid[i][m/2] != grid[n-i-1][m/2])//不回文的对数tmp++;elsecnt += grid[i][m/2]*2;//回文时1的个数}}return ans + (tmp > 0 ? tmp : cnt%4);}
}

四，3241. 标记所有节点需要的时间

本题就是一个换根dp，我们把标记奇数节点需要1时刻，标记偶数节点需要2时刻当成边权，这时题目要求的就变成了将每一个节点当成根节点时的最大深度（也就是树的高度）。如果暴力的话，需要O(n^2)的时间复杂度，会超时，所以需要使用换根dp。

换根dp，基本思路：

1. 选择一个根节点：首先选择一个节点作为树的根节点，然后从这个根节点开始进行dfs。

2. 第一次dfs：以选择的根节点开始，计算所有节点在当前根节点下的相关信息（如子树大小、子树内某些路径的和等）

3. 换根操作：然后，我们需要遍历每个节点，将树的重心从一个节点移动到另一个相邻的节点，并更新相关信息。这一步是换根DP的核心，它依赖于第一次dfs的结果来快速计算新的根节点下的信息。

4. 更新和记录结果：在换根的过程中，对于每个新的根节点，我们都会计算或更新需要的结果，并记录下来。

对于本题来说，我们使用dfs求以0为根节点最大深度，同时求出子树 x 的最大深度mx1，次大深度mx2，以及最大深度对应的子树节点my（当前根节点下的相关信息）。

然后进行换根操作，对于每一个节点 x，它们的答案有两种可能：

• 子树 x 的最大深度
• x 往上走到某个节点再拐到其他子树 

画个图理解一下：

代码如下： 

class Solution {int[] ans;int[][] node;public int[] timeTaken(int[][] edges) {int n = edges.length + 1;List<Integer>[] g = new ArrayList[n];Arrays.setAll(g, e->new ArrayList<>());for(int[] e : edges){int x = e[0], y = e[1];g[x].add(y);g[y].add(x);}ans = new int[n];node = new int[n][3];dfs(0, -1, g);reroot(0, -1, 0, g);return ans;}int dfs(int x, int fa, List<Integer>[] g){int mx1 = 0, mx2 = 0, my = 0;for(int y : g[x]){if(y == fa) continue;int depth = dfs(y, x, g) + 2 - y%2;if(mx1 < depth){mx2 = mx1;mx1 = depth;my = y;}else if(mx2 < depth){mx2 = depth;}}node[x][0] = mx1;//最大深度node[x][1] = mx2;//次大深度node[x][2] = my;//最大深度对应的子树节点return mx1;}void reroot(int x, int fa, int from, List<Integer>[] g){ans[x] = Math.max(from, node[x][0]);for(int y : g[x]){if(y != fa){int up1 = from + 2 - x%2;//在 x 处不拐弯int up2 = (y == node[x][2] ? node[x][1] : node[x][0]) + 2 - x%2;//在 x 处拐弯reroot(y, x, Math.max(up1, up2), g);}}}
}