每日习题015-等和矩阵分割 I

等和矩阵分割 I

解读：

给一个正整数组成的矩阵，判断是否可以通过一条水平或者垂直分割线将矩阵分为两个部分：

非空且和相等

思路：

第一眼感觉和14习题有点像，我们同样可以用2个数组来分别存储当前行/列的前i行/列元素总和，只要刚好等于总和一半就成功了。

还需要注意的一点是，单个元素值≤ 10⁵，矩阵总元素个数≤ 10⁵，如果理论最大情况，将会到10的10次方，超过了int型的存储极限（≈ 2×10⁹）。

class Solution { public boolean canPartitionGrid(int[][] grid) { int w = grid[0].length; int h = grid.length; long weight [] = new long [w]; long height [] = new long [h]; long row = 0L; for(int i=0;i<h;i++){ int status = 0; for(int j=0;j<w;j++){ height[i] += grid[i][j]; weight[j] += grid[i][j]; row += grid[i][j]; } } long now = 0L; for(int i=0; i<h-1; i++){ long c = height[i]; now += c; if(now*2 == row){ return true; } if(now*2 > row){ break; } } now = 0L; for(int i=0; i<w-1; i++){ long c = weight[i]; now += c; if(now*2 == row){ return true; } if(now*2 > row){ break; } } return false; } }