最大的幻方
难度:
标签:
题目描述
一个 k x k 的 幻方 指的是一个 k x k 填满整数的方格阵，且每一行、每一列以及两条对角线的和 全部相等 。幻方中的整数 不需要互不相同 。显然，每个 1 x 1 的方格都是一个幻方。
给你一个 m x n 的整数矩阵 grid ，请你返回矩阵中 最大幻方 的 尺寸 （即边长 k）。
示例 1：
输入：grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]] 输出：3 解释：最大幻方尺寸为 3 。 每一行，每一列以及两条对角线的和都等于 12 。 - 每一行的和：5+1+6 = 5+4+3 = 2+7+3 = 12 - 每一列的和：5+5+2 = 1+4+7 = 6+3+3 = 12 - 对角线的和：5+4+3 = 6+4+2 = 12
示例 2：
输入：grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]] 输出：2
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 106
代码结果
运行时间: 108 ms, 内存: 16.4 MB
/*
* Approach using Java Streams:
* We can also utilize Java Streams to streamline the computation of sums for rows, columns, and diagonals.
* This approach primarily involves converting traditional for-loops into stream operations where possible.
*/
import java.util.stream.IntStream;
public class LargestMagicSquareStream {
public int largestMagicSquare(int[][] grid) {
int m = grid.length, n = grid[0].length;
int maxK = Math.min(m, n);
for (int k = maxK; k > 0; k--) {
for (int i = 0; i + k <= m; i++) {
for (int j = 0; j + k <= n; j++) {
if (isMagic(grid, i, j, k)) return k;
}
}
}
return 1;
}
private boolean isMagic(int[][] grid, int x, int y, int k) {
int sum = IntStream.range(0, k).map(j -> grid[x][y + j]).sum();
// Check rows
if (!IntStream.range(0, k).allMatch(i -> IntStream.range(0, k).map(j -> grid[x + i][y + j]).sum() == sum)) return false;
// Check columns
if (!IntStream.range(0, k).allMatch(j -> IntStream.range(0, k).map(i -> grid[x + i][y + j]).sum() == sum)) return false;
// Check diagonals
int diag1 = IntStream.range(0, k).map(i -> grid[x + i][y + i]).sum();
int diag2 = IntStream.range(0, k).map(i -> grid[x + i][y + k - 1 - i]).sum();
return diag1 == sum && diag2 == sum;
}
}解释
方法:
这个解决方案首先计算了矩阵的行和列前缀和，以便快速计算任何子矩阵的行和列的和。然后，它尝试找到最大的幻方，从最大可能的边长开始，逐步减小边长，直到找到一个有效的幻方或者边长降到1。对于每个可能的边长，它会遍历所有可能的起始点，检查是否所有行、列以及对角线的和都等于第一行的和。如果找到这样的幻方，则立即返回这个边长。如果没有找到，最后返回1（因为任何1x1的子矩阵都是幻方）。
时间复杂度:
O(mn + min(m, n)^3)
空间复杂度:
O(mn)
代码细节讲解
🦆
在计算每个可能的幻方时，为什么选择从最大可能的边长开始递减检查，而不是从小到大增加边长进行检查？
▷🦆
在检查每行和每列的和是否相等时，如果发现某行或某列的和不符合标准和，是否有必要继续检查剩余行和列？
▷🦆
算法中如何确保在计算对角线的和时不会出现索引越界的错误？
▷🦆
前缀和数组`rowsum`和`colsum`的初始化过程中，为什么选择先单独处理第一个元素，再处理剩余元素？
▷