本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3545. 不同字符数量最多为 K 时的最少删除数 - 力扣（LeetCode）
解题思路
哈希表，按个数排序，求和即可
示例代码
python
class Solution:
def minDeletion(self, s: str, k: int) -> int:
return sum(sorted(Counter(s).values())[:-k])3546. 等和矩阵分割 I - 力扣（LeetCode）
解题思路
二维前缀和，按行和按列遍历
不用当然也可以，用一维前缀和，代码复用
示例代码
python
class Solution:
def canPartitionGrid(self, grid: List[List[int]]) -> bool:
n, m = len(grid), len(grid[0])
pre = PrefixSum2D(grid)
for i in range(n - 1):
if pre.find(0, 0, i, m - 1) == pre.find(i + 1, 0, n - 1, m - 1):
return True
for j in range(m - 1):
if pre.find(0, 0, n - 1, j) == pre.find(0, j + 1, n - 1, m - 1):
return True
return Falsepython
class Solution:
def canPartitionGrid(self, grid: List[List[int]]) -> bool:
def check(grid: List[List[int]]) -> bool:
n, m = len(grid), len(grid[0])
pre = [sum(row) for row in grid]
tot = sum(pre)
s = 0
for i in range(n - 1):
s += pre[i]
if 2 * s == tot:
return True
return False
return check(grid) or check(list(zip(*grid)))py
from typing import List
class PrefixSum2D:
__slots__ = ["m", "n", "pre"]
def __init__(self, mat: List[List[int]]):
self.m = m = len(mat)
self.n = n = len(mat[0])
self.pre = pre = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(mat):
for j, v in enumerate(row):
pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + v
def find(self, r1: int, c1: int, r2: int, c2: int) -> int:
"""查询以(r1,c1)为左上角，(r2,c2)为右下角的矩形区间内所有值的和"""
return self.pre[r2 + 1][c2 + 1] - self.pre[r2 + 1][c1] - self.pre[r1][c2 + 1] + self.pre[r1][c1]3547. 图中边值的最大和 - 力扣（LeetCode）
解题思路
错题一道 【更新】题目是错的，但是赛时通过了，思路如下
单链或成环，优先分配环，小环价值更高，其次单链，短链价值更低
所以只需要考虑长度，无需在意具体的节点
节点值从最值开始分配，具体实现可以用队列，优雅一些，数组确实丑陋
示例代码
python
class Solution:
def maxScore(self, n: int, edges: List[List[int]]) -> int:
d = [0] * n
g = defaultdict(list)
for x, y in edges:
g[x].append(y)
g[y].append(x)
d[x] += 1
d[y] += 1
def dfs(x: int) -> int:
res = 1
vis[x] = True
for y in g[x]:
if vis[y]: continue
res += dfs(y)
return res
ans = 0
st, ed = 1, n
vis = [False] * n
h1, h2 = [], []
for i, x in enumerate(d):
if x == 1 and not vis[i]:
h1.append(dfs(i))
for i, b in enumerate(vis):
if d[i] == 0:
st += 1
continue
if not b:
h2.append(dfs(i))
h1.sort()
h2.sort(reverse=True)
for l in h2:
p = [0] * l
i = j = 0
for k in range(l):
if k % 2:
j -= 1
p[j % l] = ed
else:
p[i] = ed
i += 1
ed -= 1
ans += sum(p[i] * p[(i + 1) % l] for i in range(l))
for l in h1:
p1 = [0] * ((l + l % 2) // 2)
p2 = [0] * (l // 2)
for i in range((l + l % 2) // 2):
p1[i] = st + i * 2
for i in range(l // 2):
p2[i] = st + 1 + i * 2
p = p1 + p2[::-1]
st += l
ans += sum(x * y for x, y in pairwise(p))
return ans3548. 等和矩阵分割 II - 力扣（LeetCode）
解题思路
枚举，代码复用更容易解决问题
赛后是用二维前缀和，磨了半小时才做出来
特判单列的矩阵，分割线处也可以删除
单行矩阵只考虑最前端和最后段，其余直接比较个数大小，看上去就很蠢
复盘时参考灵神代码，就是抄了
示例代码
python
class Solution:
def canPartitionGrid(self, grid: List[List[int]]) -> bool:
tot = sum(sum(row) for row in grid)
def check(b: List[List[int]]) -> bool:
n, m = len(b), len(b[0])
def cal(a: List[List[int]]) -> bool:
st = {0}
s = 0
for i, row in enumerate(a[:-1]):
for j, x in enumerate(row):
s += x
if i > 0 or j == 0 or j == m - 1:
st.add(x)
if m == 1:
if s * 2 == tot or s * 2 - tot == a[0][0] or s * 2 - tot == row[0]:
return True
continue
if s * 2 - tot in st:
return True
if i == 0:
st.update(row)
return False
return cal(b) or cal(b[::-1])
return check(grid) or check(list(zip(*grid)))python
class Solution:
def canPartitionGrid(self, grid: List[List[int]]) -> bool:
def cal(grid) -> bool:
n, m = len(grid), len(grid[0])
pre = PrefixSum2D(grid)
cnt = Counter()
for row in grid:
cnt.update(Counter(row))
for i in range(n - 1):
t1 = pre.find(0, 0, i, m - 1)
t2 = pre.find(i + 1, 0, n - 1, m - 1)
t = abs(t1 - t2)
if t == 0: return True
if m == 1:
if t1 - t2 == grid[0][0] or t1 - t2 == grid[i][0] and i >= 1: return True
if t2 - t1 == grid[-1][0] or t2 - t1 == grid[i + 1][0] and i < n - 2: return True
else:
if i == 0:
if t1 > t2:
for j in (0, m - 1):
if t == grid[i][j]:
return True
elif n > 2:
tmp = Counter(grid[0])
if cnt[t] > tmp[t]:
return True
if i == n - 2:
if t2 > t1:
for j in (0, m - 1):
if t == grid[i + 1][j]:
return True
elif n > 2:
tmp = Counter(grid[-1])
if cnt[t] > tmp[t]:
return True
if 0 < i < n - 2 and cnt[t]:
return True
return False
return cal(grid) or cal(list(zip(*grid)))