马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
Q1. 求出胜利玩家的数量
原题链接
Q1. 求出胜利玩家的数量
思绪分析
直接模仿
时间复杂度：O(N)
AC代码
- class Solution {public: int winningPlayerCount(int n, vector<vector<int>>& pick) { unordered_map<int, unordered_map<int, int>> cnt; for (auto& v : pick) { cnt[v[0]][v[1]] ++; } int res = 0; for (auto& [x, u] : cnt) { for (auto [c, d] : u) { if (x == 0 || d > x) { ++ res; break; } } } return res; }};
Q2. 最少翻转次数使二进制矩阵回文 I
原题链接
Q2. 最少翻转次数使二进制矩阵回文 I
思绪分析
直接贪婪就行，盘算原矩阵和转置矩阵的每一行的差异的两两对称位置的数量，取小的谁人
时间复杂度：O(MN)
AC代码
- class Solution: def minFlips(self, grid: List[List[int]]) -> int: res1 = 0 for row in grid: n = len(row) l, r = 0, n - 1 while l < r: res1 += 1 if row[l] != row[r] else 0 l += 1 r -= 1 grid = list(zip(*grid)) res2 = 0 for row in grid: n = len(row) l, r = 0, n - 1 while l < r: res2 += 1 if row[l] != row[r] else 0 l += 1 r -= 1 return min(res1, res2)
原题链接
Q3. 最少翻转次数使二进制矩阵回文 II
思绪分析
头脑+分组背包
左上左下右上右下关于原点对称，以是矩阵只要满足回文，这四部门中1的数量肯定是4的倍数
我们只需思量行列为奇数的时间横对称轴和竖对称轴的环境
同样对两个对称轴的两两对称位置遍历，他们终极的结果要么是两个1要么是两个0，两个0的代价就是2 - 他们的和，两个1的代价也是2 - 他们的和
我们发现这就是一个分组背包标题，最多(n + m) / 2个组，每组内2个物品，背包涵量为4
我们处置惩罚完四个对称部门的调解次数后，对横对称轴和竖对称轴求分组背包即可
时间复杂度:O(NM + N + M)
AC代码
- class Solution: def minFlips(self, grid: List[List[int]]) -> int: res = c = 0 m, n = len(grid), len(grid[0]) buf = [] res = 0 for i in range(m // 2): for j in range(n // 2): s = grid[i][j] + grid[m - 1 - i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][n - 1- j] res += min(4 - s, s) if m % 2: row = grid[m // 2] l, r = 0, n - 1 while l < r: s = row[l] + row[r] buf.append([[0, s], [2, abs(2 - s)]]) l += 1 r -= 1 if n % 2: l, r = 0, m - 1 while l < r: s = grid[l][n // 2] + grid[r][n // 2] buf.append([[0, s], [2, abs(2 - s)]]) l += 1 r -= 1 if m % 2 and n % 2: t = grid[m // 2][n // 2] buf.append([[t, 0], [0, t]]) if not buf: return res f = [inf, inf, inf, inf] for r in buf: nf = f.copy() for j in range(4): mi = inf for x, v in r: t = ((j - x) % 4 + 4) % 4 if nf[x % 4] == inf: f[x % 4] = min(f[x % 4], v) mi = min(nf[t] + v, mi) if nf[j] == inf: f[j] = min(f[j], mi) else: f[j] = mi return res + f[0]
原题链接
Q4. 标记全部节点必要的时间
思绪分析
换根dp
很显着的换根dp，为什么呢？
0时间从根节点开始标记所需时间取决于根节点的孩子和根节点的奇偶性
而且标题要我们求出每个结点作为根时的环境，天然想到换根dp
先一次dfs0预处置惩罚d[]，d 代表0时间开始标记u，u所在子树全部搞定的时间
然后dfs1 举行换根
求u 的儿子结点中 d[v] + (v & 1 ? 1 : 2)的最大值和次大值fi, se
那么我们换根为v时，假如d[v] + (v & 1 ? 1 : 2) == fi, 那么换根后d = se，否则为fi
时间复杂度：O(N)
AC代码
- class Solution: def timeTaken(self, edges: List[List[int]]) -> List[int]: n = len(edges) + 1 adj = [[] for _ in range(n)] for x, y in edges: adj[x].append(y) adj[y].append(x) d = [0] * n def dfs0(u: int, p: int) -> None: for v in adj[u]: if v == p: continue dfs0(v, u) d[u] = max(d[u], d[v] + (1 if v % 2 else 2)) dfs0(0, -1) ans = [0] * n def dfs1(u: int, p: int) -> None: fi, se = 0, 0 for v in adj[u]: if d[v] + (1 if v % 2 else 2) > fi: se = fi fi = d[v] + (1 if v % 2 else 2) elif d[v] + (1 if v % 2 else 2) > se: se = d[v] + (1 if v % 2 else 2) ans[u] = fi for v in adj[u]: if v == p: continue d[u] = se if d[v] + (1 if v % 2 else 2) == fi else fi dfs1(v, u) dfs1(0, -1) return ans
|
发表于 2026-2-13 02:29:18