LeetCode --- 136双周赛

题目列表

3238. 求出胜利玩家的数目

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

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

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

一、求出胜利玩家的数量

这题可以直接模拟统计符合条件的玩家数量，代码如下

class Solution {
public:int winningPlayerCount(int n, vector<vector<int>>& pick) {vector<array<int,11>> cnt(n);for(auto p:pick){cnt[p[0]][p[1]]++;}int ans = 0;for(int i = 0; i < n; i++){for(int y:cnt[i]){if(y > i){ans++;break;}}}return ans;}
};

二、最小翻转次数使得二进制矩阵回文 I

根据题目要求，我们按所有行回文计算一下翻转次数，再按所有列回文计算一下翻转次数，取最小值即可，代码如下

class Solution {
public:int minFlips(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();int ans[2]{};for(int i = 0; i < n; i++){for(int j = 0; j < m/2; j++){ans[0] += (grid[i][j] != grid[i][m-j-1]);}}for(int j = 0; j < m; j++){for(int i = 0; i < n/2; i++){ans[1] += (grid[i][j] != grid[n-i-1][j]);}}return min(ans[0], ans[1]);}
};

三、最小翻转次数使得二进制矩阵回文 II

这题要求每行每列都要回文，并且要求矩阵中1的个数都能被4整除，求最小翻转次数。

这题的关键在于如何满足矩阵中1的个数能被4整除，我们先来举个例子来观察一下每行和每列都要回文的矩阵的特点

代码如下

class Solution {
public:int minFlips(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();int ans = 0; // 记录四个角矩阵中需要修改的最小操作次数for(int i = 0; i < n/2; i++){for(int j = 0; j < m/2; j++){int cnt[2]{};cnt[grid[i][j]]++;cnt[grid[i][m-j-1]]++;cnt[grid[n-i-1][j]]++;cnt[grid[n-i-1][m-j-1]]++;ans += min(cnt[0], cnt[1]);}}// cnt 记录单独一行/一列变为回文，需要的操作次数// cnt1 记录单独一行/一列中 1 的个数int cnt = 0, cnt1 = 0;if(n%2){for(int j = 0; j < m/2; j++){cnt += (grid[n/2][j]!=grid[n/2][m-j-1]);cnt1 += grid[n/2][j] + grid[n/2][m-j-1];}}if(m%2){for(int i = 0; i < n/2; i++){cnt += (grid[i][m/2]!=grid[n-i-1][m/2]);cnt1 += (grid[i][m/2] + grid[n-i-1][m/2]);}}if(n%2 && m%2){if(grid[n/2][m/2] == 1)ans++;}return ans + (cnt == 0 ? cnt1%4 : cnt);}
};

四、标记所有点需要的时间

对于给出操作流程，要求算出以每一个结点为根节点完成流程所需时间的题目，有一种通用的思路：先计算以某一个结点完成流程的时间，然后根据这个结点来计算其他结点完成操作流程的时间。(这类题统称为换根dp)

这题也是同理，我们先要计算出以0为根节点时，所有结点被标记所需要的时间，然后根据这一结果计算其他结点为根时的情况，最后返回即可。

代码如下

class Solution {struct Node{int _fi,_se,_child;Node(){}Node(int fi,int se,int child):_fi(fi),_se(se),_child(child){}};
public:vector<int> timeTaken(vector<vector<int>>& edges) {int n = edges.size() + 1;vector<vector<int>>g(n);for(auto e:edges){g[e[0]].push_back(e[1]);g[e[1]].push_back(e[0]);}// time[i] 记录 i 所在子树被标记的最大时间，次大时间 和最大时间的子树，不包含 i 被标记的时间vector<Node> time(n);function<int(int,int)>dfs=[&](int x,int fa)->int{int fi = 0, se = 0, child = 0;for(int y:g[x]){if(y != fa){int res = dfs(y, x) + (2 - y%2);if(res > fi) se = fi, fi = res, child = y;else if(res > se) se = res;}}time[x] = Node(fi, se, child);return fi;};dfs(0, -1);vector<int> ans(n);function<void(int,int,int)>reroot=[&](int x,int fa,int fa_mx){auto [fi,se,child] = time[x];ans[x] = max(fa_mx, fi);for(int y:g[x]){if(y != fa){int up1 = (y == child ? se : fi) + 2 - x%2;int up2 = fa_mx + 2 - x%2;reroot(y, x, max(up1, up2));}}};reroot(0,-1,0);return ans;}
};