leetcode 1895(前缀和+暴力枚举)
1895: 最大的幻方
幻方指的是一个k x k填满整数的方格阵，且每一行、每一列以及两条对角线的和全部相等 。幻方中的整数不需要互不相同。
显然，每个1 x 1的方格都是一个幻方。
思路：前缀和+暴力枚举
1.暴力检查
- 因为
m, n ≤ 50,所以最大可能的边长k是min(m,n) - 从大到小尝试
k，找到第一个满足条件的幻方即可返回
2.优化计算
- 我们可以预处理行前缀和和列前缀和，以便快速计算任意子矩阵的行和与列和
- 对角线可以通过直接遍历来求和
3.算法步骤
预处理行前缀和与列前缀和，从大到小枚举边长 k
枚举子矩阵的左上角 (r,c)，检查该子矩阵是否为幻方
- 计算第一行的和作为目标值
- 检查所有行的和是否等于目标值
- 检查所有列的和是否等于目标值
- 检查两条对角线的和是否等于目标值
如果找到，直接返回当前 k
如果都没找到，返回 1（因为 1×1 总是幻方）
class Solution { public: int largestMagicSquare(vector<vector<int>>& grid) { int m=grid.size(),n=grid[0].size(); vector<vector<int>> rowPrefix(m+1,vector<int>(n+1,0)); //预处理行前缀和和列前缀和 vector<vector<int>> colPrefix(m+1,vector<int>(n+1,0)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ rowPrefix[i+1][j+1]=rowPrefix[i+1][j]+grid[i][j]; colPrefix[i+1][j+1]=colPrefix[i][j+1]+grid[i][j]; } } auto getRowsum=[&](int r,int c1,int c2){ return rowPrefix[r+1][c2+1]-rowPrefix[r+1][c1]; }; auto getColsum=[&](int c,int r1,int r2){ return colPrefix[r2+1][c+1]-colPrefix[r1][c+1]; }; for(int k=min(m,n);k>1;k--){ //从大到小枚举边长k for(int r=0;r+k<=m;r++){ for(int c=0;c+k<=n;c++){ int target=getRowsum(r,c,c+k-1); bool ok=true; for(int i=r;i<r+k;i++){ if(getRowsum(i,c,c+k-1)!=target){ ok=false; break; } } if(!ok) continue; for(int j=c;j<c+k;j++){ if(getColsum(j,r,r+k-1)!=target){ ok=false; break; } } if(!ok) continue; int diag1=0,diag2=0; for(int d=0;d<k;d++){ diag1+=grid[r+d][c+d]; diag2+=grid[r+d][c+k-1-d]; } if(diag1!=target || diag2!=target) continue; return k; } } } return 1; } };