LeetCode 3548. 等和矩阵分割2 详细题解（前缀和+二分+连通性分析）

LeetCode 3548. 等和矩阵分割2 详细题解前缀和二分连通性分析️ 标签前缀和、二分查找、连通性、哈希表、矩阵、周赛难题 难度中等| 题目编号3548|️ 题型矩阵处理 / 贪心优化一、题目描述给定一个由正整数组成的m x n矩阵grid判断是否能通过一条水平或一条垂直分割线将矩阵切成两个非空部分满足以下条件之一两部分所有元素的和相等最多移除一个单元格后两部分和相等且移除后剩余区域保持连通。连通定义区域内任意两个单元格可通过上下左右移动互相到达不分裂成多块。若存在合法分割返回True否则返回False。二、示例演示示例 1输入grid [[1,4],[2,3]] 输出true 解释水平分割上下两部分和均为5直接满足相等。示例 2输入grid [[1,2],[3,4]] 输出true 解释垂直分割左和为4右和为6移除右侧的2差值抹平且保持连通。示例 3输入grid [[1,2,4],[2,3,5]] 输出false 解释差值为3移除3后区域分裂不满足连通性。示例 4输入grid [[4,1,8],[3,2,6]] 输出false 解释无任何合法分割方式。三、数据范围与约束1 ≤ m grid.length ≤ 1e51 ≤ n grid[i].length ≤ 1e52 ≤ m * n ≤ 1e5总元素数不超1e5保证线性算法可过1 ≤ grid[i][j] ≤ 1e5四、解题核心思路1. 核心突破口本题只能用一条水平或垂直分割线切分矩阵目标是让两部分和相等或删除一个元素后相等且保证删除后区域连通。快速求区间和使用行、列前缀和避免重复求和提升效率快速查找目标值用哈希表存值的坐标配合二分查找快速判断区域内是否存在目标差值连通性判断按分割后的区域形状分情况判定可删除的位置杜绝误判2. 分割方式水平分割在第i行与i1行之间切分分成上下两个矩形垂直分割在第j列与j1列之间切分分成左右两个矩形3. 和的判定规则设矩阵总和为total切分后一块和为s另一块为total-s。直接合法s total - s两部分和完全相等删除一个合法|s - (total - s)| diff在和更大的块里找到一个值等于diff的元素删除后两部分和相等4. 连通性判定关键删除元素后剩余区域必须保持连通不分裂成多块规则如下多行多列删除任意元素都保持连通只需存在目标值即可单行多列只能删除最左端或最右端元素删除中间会断裂多行单列只能删除最上端或最下端元素删除中间会断裂单行单列不能删除删除后区域为空不满足题意5. 效率优化用哈希表记录每个数值的所有坐标配合二分查找把区域内查找的复杂度降到对数级别应对数据范围上限不超时。五、满分代码Python代码严谨高效贴合题目要求附带详细注释可直接提交评测。fromtypingimportListfromcollectionsimportdefaultdictimportbisectclassSolution:defcanPartitionGrid(self,grid:List[List[int]])-bool:m,nlen(grid),len(grid[0])totalsum(sum(row)forrowingrid)# 行前缀和快速计算上半部分和row_sum[0]*(m1)foriinrange(m):row_sum[i1]row_sum[i]sum(grid[i])# 列前缀和快速计算左半部分和col_sum[0]*(n1)forjinrange(n):colsum(grid[i][j]foriinrange(m))col_sum[j1]col_sum[j]col# 哈希表存储每个值对应的所有坐标按行排序方便二分查找val_to_coordsdefaultdict(list)foriinrange(m):forjinrange(n):val_to_coords[grid[i][j]].append((i,j))# 对每个值的坐标列表排序forvinval_to_coords:val_to_coords[v].sort()# 辅助函数判断指定矩形区域内是否存在目标值defhas_value_in_rect(val,r1,r2,c1,c2):coordsval_to_coords.get(val)ifnotcoords:returnFalse# 二分定位起始行lo,hi0,len(coords)whilelohi:mid(lohi)//2ifcoords[mid][0]r1:lomid1else:himid idxlo# 遍历符合行范围的坐标检查列范围whileidxlen(coords)andcoords[idx][0]r2:ifc1coords[idx][1]c2:returnTrueidx1returnFalse# 辅助函数判断当前区域能否删除一个值为diff的元素且保持连通defcan_remove(rows,cols,r1,r2,c1,c2,diff):# 多行多列任意位置可删ifrows1andcols1:returnhas_value_in_rect(diff,r1,r2,c1,c2)# 单行多列只能删左右两端elifrows1andcols1:returngrid[r1][c1]difforgrid[r1][c2]diff# 多行单列只能删上下两端elifrows1andcols1:returngrid[r1][c1]difforgrid[r2][c1]diff# 单行单列无法删除else:returnFalse# 枚举所有水平分割线foriinrange(m-1):toprow_sum[i1]bottomtotal-top# 直接满足和相等iftopbottom:returnTruediffabs(top-bottom)# 从和更大的部分删除元素iftopbottom:# 上半部分ifcan_remove(i1,n,0,i,0,n-1,diff):returnTrueelse:# 下半部分ifcan_remove(m-i-1,n,i1,m-1,0,n-1,diff):returnTrue# 枚举所有垂直分割线forjinrange(n-1):leftcol_sum[j1]righttotal-left# 直接满足和相等ifleftright:returnTruediffabs(left-right)# 从和更大的部分删除元素ifleftright:# 左半部分ifcan_remove(m,j1,0,m-1,0,j,diff):returnTrueelse:# 右半部分ifcan_remove(m,n-j-1,0,m-1,j1,n-1,diff):returnTrue# 所有分割方式都不满足returnFalse六、代码详解1. 核心变量说明total矩阵所有元素的总和row_sum行前缀和数组用于快速计算水平分割后的上半部分和col_sum列前缀和数组用于快速计算垂直分割后的左半部分和val_to_coords哈希表key为矩阵元素值value为该值所有坐标的有序列表diff两部分和的差值即需要删除的元素值2. 辅助函数讲解1has_value_in_rect作用快速判断目标值是否出现在指定矩形区域内。先用二分查找缩小行范围再遍历检查列范围比暴力遍历效率更高。2can_remove作用判断当前区域能否删除一个值为diff的元素且删除后保持连通。严格按照连通性规则分四种情况判断杜绝连通性误判贴合题目要求。3. 完整执行流程计算矩阵总和构建行、列前缀和记录每个元素的坐标存入哈希表并排序枚举所有水平分割线检查直接相等、删除元素相等两种情况枚举所有垂直分割线重复上述判断逻辑找到合法分割立即返回True遍历完毕无合法方案返回False七、复杂度分析时间复杂度O(mn log(mn))预处理坐标为O(mn)二分查找为对数级别枚举分割为线性次数整体高效适配题目数据范围空间复杂度O(mn)用于存储前缀和数组与元素坐标哈希表八、常见易错点连通性误判单行/单列删除中间元素导致区域分裂查找超时暴力遍历区域查找差值大数据量下超时分割遗漏只检查水平或垂直一种分割方式删错区域从和更小的块里删除元素无法让两部分和相等原创题解禁止搬运觉得有用欢迎点赞、收藏遇到问题可在评论区交流~