Leetcode 第 136 场双周赛题解

Leetcode 第 136 场双周赛题解

题目1：3238. 求出胜利玩家的数目

思路

遍历 pick，用一个 n×11 大小的矩阵，统计每个玩家得到的每种颜色的球的个数。

遍历每个玩家，如果该玩家至少有一种颜色的球大于玩家编号，则把答案加一。

代码

/** @lc app=leetcode.cn id=3238 lang=cpp** [3238] 求出胜利玩家的数目*/// @lc code=start
class Solution
{
public:int winningPlayerCount(int n, vector<vector<int>> &pick){vector<vector<int>> cnt(n, vector<int>(11, 0));for (auto &p : pick)cnt[p[0]][p[1]]++;int ans = 0;for (int i = 0; i < n; i++){bool judge = false;for (int j = 0; j < cnt[i].size(); j++)if (cnt[i][j] > i)judge = true;if (judge)ans++;}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(nU+m)，其中 m 是数组 pick 的长度，U 是 yi 的最大值。

空间复杂度：O(nU)，其中 U 是 yi 的最大值。

题目2：3239. 最少翻转次数使二进制矩阵回文 I

思路

先计算所有行变成回文最少需要翻转多少次。

也就是对于每一行 row，计算这一行变成回文最少需要翻转多少次。

也就是累加 row[j]!=row[n−1−j] 的个数，其中 0≤j≤⌊n/2⌋。

对于列，统计方式同理。

两种情况取最小值，即为答案。

代码

/** @lc app=leetcode.cn id=3239 lang=cpp** [3239] 最少翻转次数使二进制矩阵回文 I*/// @lc code=start
class Solution
{
public:int minFlips(vector<vector<int>> &grid){int m = grid.size(), n = m ? grid[0].size() : 0;int diff_row = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n / 2; j++)diff_row += grid[i][j] != grid[i][n - 1 - j];int diff_col = 0;for (int j = 0; j < n; j++)for (int i = 0; i < m / 2; i++)diff_col += grid[i][j] != grid[m - 1 - i][j];return min(diff_row, diff_col);}
};
// @lc code=end

复杂度分析

时间复杂度：O(m * n)，其中 m 和 n 分别为数组 grid 的行数和列数。

空间复杂度：O(1)。

题目3：3240. 最少翻转次数使二进制矩阵回文 II

思路

分类讨论。

特殊情况：

讨论正中间一排（如果 m 是奇数）和正中间一列（如果 n 是奇数）中的格子要如何翻转。

综上所述：

• 如果 diff>0，额外把 diff 加入答案。
• 如果 diff=0，额外把 cnt1 mod4 加入答案。

代码

/** @lc app=leetcode.cn id=3240 lang=cpp** [3240] 最少翻转次数使二进制矩阵回文 II*/// @lc code=start
class Solution
{
public:int minFlips(vector<vector<int>> &grid){int m = grid.size(), n = m ? grid[0].size() : 0;int ans = 0;for (int i = 0; i < m / 2; i++)for (int j = 0; j < n / 2; j++){int cnt1 = grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] + grid[m - 1 - i][n - 1 - j];ans += min(cnt1, 4 - cnt1); // 全为 1 或全为 0}if (m % 2 && n % 2 && grid[m / 2][n / 2] == 1){// 正中间的数必须是 0ans++;}int diff = 0, cnt1 = 0;if (m % 2){// 统计正中间这一排for (int j = 0; j < n / 2; j++){if (grid[m / 2][j] != grid[m / 2][n - 1 - j])diff++;elsecnt1 += grid[m / 2][j] * 2;}}if (n % 2){// 统计正中间这一列for (int i = 0; i < m / 2; i++){if (grid[i][n / 2] != grid[m - 1 - i][n / 2])diff++;elsecnt1 += grid[i][n / 2] * 2;}}if (cnt1 % 4 == 0){// 把这 diff 对数全部变成 0ans += diff;}else{if (diff){// 把一对数都变成 1，其余全变成 0，要翻转 diff 个数ans += diff;}else{// 把两个 1 翻转为 0ans += 2;}}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(m * n)，其中 m 和 n 分别为数组 grid 的行数和列数。

空间复杂度：O(1)。

题目4：3241. 标记所有节点需要的时间

思路

换根DP。

题解：【模板】第二类换根 DP（Python/Java/C++/Go）

代码

/** @lc app=leetcode.cn id=3241 lang=cpp** [3241] 标记所有节点需要的时间*/// @lc code=start
class Solution
{
public:vector<int> timeTaken(vector<vector<int>> &edges){vector<vector<int>> g(edges.size() + 1);for (auto &e : edges){int x = e[0], y = e[1];g[x].push_back(y);g[y].push_back(x);}// nodes[x] 保存子树 x 的最大深度 max_d，次大深度 max_d2，以及最大深度要往儿子 my 走vector<tuple<int, int, int>> nodes(g.size());auto dfs = [&](auto &&dfs, int x, int fa) -> int{int max_d = 0, max_d2 = 0, my = 0;for (int y : g[x]){if (y == fa){continue;}int depth = dfs(dfs, y, x) + 2 - y % 2; // 从 x 出发，往 my 方向的最大深度if (depth > max_d){max_d2 = max_d;max_d = depth;my = y;}else if (depth > max_d2){max_d2 = depth;}}nodes[x] = {max_d, max_d2, my};return max_d;};dfs(dfs, 0, -1);vector<int> ans(g.size());auto reroot = [&](auto &&reroot, int x, int fa, int from_up) -> void{auto &[max_d, max_d2, my] = nodes[x];ans[x] = max(from_up, max_d);for (int y : g[x]){if (y != fa){reroot(reroot, y, x, max(from_up, (y == my ? max_d2 : max_d)) + 2 - x % 2);}}};reroot(reroot, 0, -1, 0);return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是数组 edges 的长度。

空间复杂度：O(n)，其中 n 是数组 edges 的长度。