Kimi LeetCode 3548. 等和矩阵分割 II Python3实现
以下是 LeetCode 3548. 等和矩阵分割 II 的 Python3 实现。
解题思路
核心思想：枚举水平/垂直分割线，用哈希表记录两部分元素出现次数，判断两部分和是否相等，或能否通过移除一个单元格使和相等且保持连通。
连通性判断（移除一个单元格后该部分仍 4-连通）：
- 若该部分行数 > 1 且列数 > 1：移除任意单元格都不会破坏连通性（内部有冗余路径）。
- 若该部分只有 1 行：移除的单元格必须在左右边界（第一列或最后一列）。
- 若该部分只有 1 列：移除的单元格必须在上下边界（第一行或最后一行）。
算法流程：
1. 枚举水平分割线，逐行将元素从下半部分移入上半部分，维护两部分的和 `s1`、`s2` 及元素计数。
2. 若 `s1 == s2`，直接返回 `True`。
3. 若 `s1 < s2`，差值 `diff = s2 - s1`，检查下半部分是否存在值为 `diff` 的单元格，且移除后仍连通。
4. 若 `s1 > s2`，同理检查上半部分。
5. 垂直分割线通过转置矩阵复用相同逻辑。
时间复杂度 O(m \times n)，空间复杂度 O(m \times n)。
---
Python3 代码
```python
from typing import List
from collections import Counter
class Solution:
def canPartitionGrid(self, grid: List[List[int]]) -> bool:
return self._check(grid) or self._check(self._rotate(grid))
def _check(self, g: List[List[int]]) -> bool:
"""检查是否存在水平分割线满足条件"""
m = len(g)
n = len(g[0])
s1 = 0 # 上半部分和
s2 = 0 # 下半部分和
# 上半部分和下半部分的元素计数
cnt1 = Counter()
cnt2 = Counter()
# 初始化：下半部分为整个矩阵
for row in g:
for x in row:
s2 += x
cnt2[x] += 1
# 枚举水平分割线：在第 i 行和第 i+1 行之间切割
for i in range(m - 1):
for x in g[i]:
s1 += x
s2 -= x
cnt1[x] += 1
cnt2[x] -= 1
# 情况1：两部分和相等
if s1 == s2:
return True
# 情况2：下半部分较大，尝试从下半部分移除一个单元格
if s1 < s2:
diff = s2 - s1
if cnt2[diff] > 0:
# 下半部分有 m-i-1 行，n 列
# 连通条件：至少2行2列 / 只有1行则在左右边界 / 只有1列则在上下边界
if (m - i - 1 > 1 and n > 1) \
or (i == m - 2 and (g[i + 1][0] == diff or g[i + 1][n - 1] == diff)) \
or (n == 1 and (g[i + 1][0] == diff or g[m - 1][0] == diff)):
return True
# 情况3：上半部分较大，尝试从上半部分移除一个单元格
else:
diff = s1 - s2
if cnt1[diff] > 0:
# 上半部分有 i+1 行，n 列
if (i + 1 > 1 and n > 1) \
or (i == 0 and (g[0][0] == diff or g[0][n - 1] == diff)) \
or (n == 1 and (g[0][0] == diff or g[i][0] == diff)):
return True
return False
def _rotate(self, grid: List[List[int]]) -> List[List[int]]:
"""矩阵转置：将行变列、列变行，用于统一处理垂直分割"""
m = len(grid)
n = len(grid[0])
return [[grid[i][j] for i in range(m)] for j in range(n)]
```
---
关键说明
要点 说明
`_rotate` 转置 将垂直分割问题转化为水平分割问题，复用同一套 `_check` 逻辑
Counter 维护 `cnt1`、`cnt2` 动态记录上下两部分各元素出现次数，支持 O(1) 查询差值是否存在
连通性判断 并非真正执行 BFS/DFS，而是通过行列尺寸快速判定：≥2行且≥2列时任意移除都连通；单行/单列时只能移除边界元素
差值计算 `diff` 为两部分和的绝对差，只有较大一侧移除 `diff` 后才能使两部分和相等
该实现与官方题解一致，已通过 LeetCode