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)
        {
            // 正中间的数必须是 0
            ans++;
        }

        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++;
                else
                    cnt1 += 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++;
                else
                    cnt1 += grid[i][n / 2] * 2;
            }
        }
        if (cnt1 % 4 == 0)
        {
            // 把这 diff 对数全部变成 0
            ans += diff;
        }
        else
        {
            if (diff)
            {
                // 把一对数都变成 1，其余全变成 0，要翻转 diff 个数
                ans += diff;
            }
            else
            {
                // 把两个 1 翻转为 0
                ans += 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 的长度。