每日一题 力扣 3548. 等和矩阵分割 II 前缀和 哈希表 C++ 题解

文章目录题目描述思路简述代码实现复杂度分析踩坑记录题目描述力扣 3548. 等和矩阵分割 II示例 1输入 grid [[1,4],[2,3]]输出 true解释在第 0 行和第 1 行之间进行水平分割结果两部分的元素和为 1 4 5 和 2 3 5相等。因此答案是 true。示例 2输入 grid [[1,2],[3,4]]输出 true解释在第 0 列和第 1 列之间进行垂直分割结果两部分的元素和为 1 3 4 和 2 4 6。通过从右侧部分移除 2 6 - 2 4两部分的元素和相等并且两部分保持连通。因此答案是 true。示例 3输入 grid [[1,2,4],[2,3,5]]输出 false解释在第 0 行和第 1 行之间进行水平分割结果两部分的元素和为 1 2 4 7 和 2 3 5 10。通过从底部部分移除 3 10 - 3 7两部分的元素和相等但底部部分不再连通分裂为 [2] 和 [5]。因此答案是 false。示例 4输入 grid [[4,1,8],[3,2,6]]输出 false解释不存在有效的分割因此答案是 false。提示1 m grid.length 1051 n grid[i].length 1052 m * n 1051 grid[i][j] 105思路简述有了昨日每日一题的铺垫初次接触的朋友可以先参考我的上篇博客每日一题 力扣 3546. 等和矩阵分割 I 前缀和 贪心 剪枝 C 题解本题与前一题的核心区别在于允许移除矩阵中最多一个元素让分割线两侧的元素和相等且移除元素后分割对应的区域必须保持连通。整体解题思路与前题相似但本题放弃了数组形式的前缀和统计改用变量累加的方式实现前缀和大幅简化了空间开销并引入了哈希表。本题的核心难点是连通性判断删除元素后导致区域不连通的场景仅有两种 (我们视角是按照上半部分与左半部分进行分析不考虑下半部分与右半部分后面说明原因)——水平分割后上侧区域仅为一行、垂直分割后左侧区域仅为一列。这两种特殊场景下我们只能删除所在行/列两端的元素才能保证连通性如下图所示如果单独为水平、垂直分割编写两套代码再结合坐标特判、前缀和数组的坐标偏差逻辑会非常繁琐。因此我们采用旋转复用的技巧仅实现一套水平切割的判断逻辑对矩阵执行4次顺时针90°旋转即可复用同一套代码完成水平、垂直所有方向的分割判定。之后由于这道题可以删除一个元素所以我们提前计算出这个x我们设需要删除的元素值为x分割线上半部分和为sum矩阵总和为total那么后面的这个灯饰我们一定能够认可sum - x total - sum即可推导出核心公式x sum * 2 - total(公式有很多种不同的推导方式选用该公式可以完全避免除法运算带来的精度误差)。每次旋转后我们先对矩阵做边界剪枝与特殊处理m 2由于矩阵不为空意味着当前矩阵仅有一行m 1不满足水平切割的基本条件直接旋转矩阵进入下一轮判断。n 1当前矩阵仅有一列属于一维数组的极端情况虽然是极端情况课这个情况好处理即当成一个一维数组单独遍历处理即可只需要注意x坐标的合法性也就是连通性判断这个判断就是上图所展示的情况旋转矩阵进入下一轮。完成剪枝后进入核心统计逻辑最外层的循环逐行遍历矩阵模拟枚举水平分割线。每确定一条分割线并通过变量统计上半部分的元素和变量实现前缀和同时用哈希表记录上半部分的所有元素值。同样提前计算x针对计算结果分情况判断若x 0无需删除任何元素两部分和已相等直接返回true。若x是具体的数这样我们知道了可以删除的值再去哈希表中进行查找由于我们的矩阵旋转所以不用怕上半部分的和小于下半部分应该是下半部分删除元素的问题借助矩阵旋转我们无需处理下半部分删除元素的场景——旋转后下半部分会变为上半部分可被同一套逻辑覆盖找到目标值x后结合连通性规则校验若上半部分仅一行仅校验行两端元素是否等于x若上半部分≥2行任意元素均可删除直接校验哈希表即可。注这里哈希只需要统计上半部分x是否出现过即可因为特殊位置是固定的所以我们无需统计x的位置最后对矩阵执行顺时针90°旋转进入下一轮方向的判断。矩阵旋转实现通过公式tmp[j][m-1-i] grid[i][j]实现矩阵顺时针90°旋转核心作用是将原矩阵的列转换为行让垂直分割等价为水平分割实现代码复用。代码实现classSolution{public:// 矩阵顺时针旋转90度// 核心作用将 列 → 转换为行让垂直分割可以复用水平分割的代码vectorvectorintrotation(vectorvectorintgrid){intmgrid.size(),ngrid[0].size();// 旋转后矩阵尺寸n行 m列vectorvectorinttmp(n,vectorint(m,0));for(inti0;im;i)for(intj0;jn;j)// 坐标变换公式原(i,j) → 旋转后(j, m-1-i)tmp[j][m-1-i]grid[i][j];returntmp;}boolcanPartitionGrid(vectorvectorintgrid){longlongtotal0;// 矩阵所有元素的总和longlongsum;// 分割线上半部分的元素和前缀和longlongx;// 需要删除的元素值sum - x total - sum → x 2*sum - totalintmgrid.size();// 矩阵行数intngrid[0].size();// 矩阵列数unordered_setlonglongexist;// 存储分割线上半部分的所有元素值不存下标// 第一步计算整个矩阵的元素总和for(inti0;im;i)for(intj0;jn;j)totalgrid[i][j];// 旋转4次覆盖 水平/垂直 四个分割方向上→下、下→上、左→右、右→左for(intk0;k4;k){exist.clear();// 清空哈希表重新记录当前分割的上半部分元素exist.insert(0);// 初始化占位无实际作用兼容边界sum0;// 重置上半部分和mgrid.size();// 更新当前旋转后的矩阵行数ngrid[0].size();// 更新当前旋转后的矩阵列数// 剪枝1当前矩阵只有1行无法水平切割直接旋转下一个方向if(m2){gridrotation(grid);continue;// 直接进入下一轮}// 剪枝2特殊情况 → 矩阵只有1列一维数组单独处理if(n1){for(inti0;im-1;i){sumgrid[i][0];xsum*2-total;// 满足条件无需删除 或 删除列的两端元素保证连通if(x0||xgrid[0][0]||xgrid[i][0]){returntrue;}}gridrotation(grid);continue;// 直接进入下一轮}// 核心逻辑枚举所有水平分割线遍历到倒数第二行保证下半部分非空for(inti0;im-1;i){// 累加当前行所有元素存入哈希表哈希表只保留分割线上半部分for(intj0;jn;j){exist.insert(grid[i][j]);sumgrid[i][j];}// 计算需要删除的元素值xsum*2-total;// 情况1分割后上半部分只有 1 行i0// 连通性规则只能删除行的 左右两端 元素if(i0){if(x0||xgrid[0][0]||xgrid[0][n-1])returntrue;continue;// 直接进入下一轮}// 情况2分割后上半部分 ≥ 2 行// 连通性规则删除任意元素都连通只要哈希表存在x就合法if(exist.contains(x))returntrue;}// 当前方向检查完毕旋转矩阵检查下一个方向gridrotation(grid);}// 四个方向都检查完毕无有效分割returnfalse;}};复杂度分析时间复杂度O ( m n ) O(mn)O(mn)矩阵共旋转4次每次旋转与遍历的时间复杂度均为矩阵元素总个数m n mnmn常数系数不影响复杂度量级。空间复杂度O ( m n ) O(mn)O(mn)主要开销为旋转矩阵的临时数组、哈希表存储的元素值均与矩阵元素个数线性相关。踩坑记录最初尝试使用二维数组统计前缀和但后续被连通性的判定条件绕晕甚至混淆了矩阵的行和列导致逻辑混乱。一开始想用unordered_map建立元素值与下标的映射来校验连通性看完题解后发现了更简洁的思路仅统计分割线一侧的元素结合固定坐标校验特殊位置即可完全不需要记录下标大幅简化了代码逻辑。如果这篇博客对你有帮助别忘了点赞支持一下也可以收藏起来方便后续刷题复习时随时翻看。要是能顺手点个关注爱弥斯还能得到漂泊者批准的游戏时间哦