leetcode 840

840: 矩阵中的幻方

数学证明：1.幻方正中心一定是 5

2.无需计算第三行、第三列的和

3.无需计算对角线的和

如果 3×3 矩阵：

• 正中心的数是 5。
• 包含 1 到 9 所有整数。
• 前两行的和都是 15。
• 前两列的和都是 15。

下面证明：矩阵对角线的和一定都是 15。

如何快速判断矩阵包含 1 到 9 所有数？可以把数字压缩到一个二进制数 mask 中，mask 从低到高的 i 位是 1 表示 i 在矩阵中。矩阵包含 1 到 9 所有数相当于 mask=1111111110(2)=2^10−2=1022。

mask |= 1 << x;

mask == (1 << 10) - 2

二进制：把1左移10位——10000000000（十进制 1024）

1024-2=1022=1111111110(2)，表示 mask 的第 1 位到第 9 位全部为 1，第 0 位为 0。

int r_sum[3]{},c_sum[3]{};

等价于：

int r_sum[3] = {0, 0, 0}; int c_sum[3] = {0, 0, 0};

class Solution { public: int numMagicSquaresInside(vector<vector<int>>& grid) { int m=grid.size(),n=grid[0].size(); int ans=0; for(int i=0;i<m-2;i++){ for(int j=0;j<n-2;j++){ //遍历左上角 if(grid[i+1][j+1]!=5) continue; int mask=0; int r_sum[3]{},c_sum[3]{}; for(int r=0;r<3;r++){ for(int c=0;c<3;c++){ int x=grid[i+r][j+c]; mask|=1<<x; //把mask的第x位设为1 r_sum[r]+=x; c_sum[c]+=x; } } if(mask==(1<<10)-2 && r_sum[0]==15 && r_sum[1]==15 && c_sum[0]==15 && c_sum[1]==15){ ans++; } } } return ans; } };