🧩 初学者友好指南 'Largest Magic Square' – LeetCode 1895 (C++, Python, JavaScript)

Source: Dev.to

问题描述

在网格中搜索模式是算法思维中的经典挑战。
在本题中，我们的任务是找到 最大的可能子网格，使得每一行、每一列以及两条主对角线的和都恰好相等。

给定条件

• 一个 m × n 的整数网格。
• 魔方阵 是指一个 k × k 的子网格，其中每一行、每一列以及两条对角线的和都相等。

目标

返回网格中任意魔方阵的最大边长 k。

示例

示例 1

Input:  grid = [[7,1,4,5,6],
               [2,5,1,6,4],
               [1,5,4,3,2],
               [1,2,7,3,4]]
Output: 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

Input:  grid = [[5,1,3,1],
               [9,3,3,1],
               [1,3,3,8]]
Output: 2

约束条件

• m == grid.length
• n == grid[i].length
• 1 ≤ m, n ≤ 50
• 1 ≤ grid[i][j] ≤ 10⁶

直觉

一种暴力解法会检查每一种可能大小的每一个方阵，并手动求其行、列和对角线的和。这会重复大量工作。

为了提高效率，我们使用 前缀和（累计总和）。
如果我们知道一行在第 10 列和第 5 列的累计总和，那么第 5 列到第 10 列之间的和只需两者相减即可。

我们为每个单元格预先计算四个前缀和表：

有了这些表格，检查一个 k × k 方阵是否为幻方只需进行几次常数时间的减法。
我们从可能的最大边长 min(m, n) 开始向下搜索；第一个满足条件的大小即为答案。

解题代码

C++

class Solution {
public:
    // Check whether the k×k square with top‑left corner (r, c) is magic
    bool isMagic(const vector>>& pref,
                 int r, int c, int k) {
        // target sum = main diagonal of the square
        int target = pref[r + k][c + k][2] - pref[r][c][2];

        // anti‑diagonal must match
        if (target != pref[r + k][c + 1][3] - pref[r][c + k + 1][3])
            return false;

        // each row sum must match
        for (int i = r; i >& grid) {
        int m = grid.size(), n = grid[0].size();

        // pref[i][j] = {row, col, diag, anti‑diag} sums up to (i‑1, j‑1)
        vector>> pref(m + 1,
                                          vector>(n + 2, {0,0,0,0}));

        for (int i = 1; i = 2; --k) {
            for (int i = 0; i + k  int:
        m, n = len(grid), len(grid[0])

        # pref[i][j] = [row, col, diag, anti_diag] sums up to (i‑1, j‑1)
        # extra padding (n+2) simplifies anti‑diagonal indexing
        pref = [[[0] * 4 for _ in range(n + 2)] for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                val = grid[i - 1][j - 1]
                pref[i][j][0] = pref[i][j - 1][0] + val          # row
                pref[i][j][1] = pref[i - 1][j][1] + val          # column
                pref[i][j][2] = pref[i - 1][j - 1][2] + val      # main diagonal
                pref[i][j][3] = pref[i - 1][j + 1][3] + val      # anti‑diagonal

        # helper to test a k×k square with top‑left corner (r, c)
        def is_magic(r: int, c: int, k: int) -> bool:
            target = pref[r + k][c + k][2] - pref[r][c][2]      # main diagonal
            if target != pref[r + k][c + 1][3] - pref[r][c + k + 1][3]:
                return False

            # rows
            for i in range(r, r + k):
                if pref[i + 1][c + k][0] - pref[i + 1][c][0] != target:
                    return False
            # columns
            for j in range(c, c + k):
                if pref[r + k][j + 1][1] - pref[r][j + 1][1] != target:
                    return False
            return True

        for k in range(min(m, n), 1, -1):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    if is_magic(i, j, k):
                        return k
        return 1

Python

3] + val

def is_magic(r, c, k):
    # Target sum from the main diagonal
    target = pref[r + k][c + k][2] - pref[r][c][2]

    # Check anti-diagonal
    if target != pref[r + k][c + 1][3] - pref[r][c + k + 1][3]:
        return False

    # Check all rows
    for i in range(r, r + k):
        if pref[i + 1][c + k][0] - pref[i + 1][c][0] != target:
            return False

    # Check all columns
    for j in range(c, c + k):
        if pref[r + k][j + 1][1] - pref[r][j + 1][1] != target:
            return False

    return True

# Check from largest possible side length downwards
for k in range(min(m, n), 1, -1):
    for i in range(m - k + 1):
        for j in range(n - k + 1):
            if is_magic(i, j, k):
                return k
return 1

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestMagicSquare = function (grid) {
    const m = grid.length;
    const n = grid[0].length;

    // Create prefix

工作原理 – 步骤详解

1. 构建前缀表 – O(m·n) 时间，O(m·n) 额外空间。
2. 从大到小遍历边长。
3. 对于每个可能的左上角，提取：
   • 主对角线和，
   • 副对角线和，
   • 每行的和，
   • 每列的和
     使用前缀表的常数时间减法。
4. 第一个通过所有检查的尺寸即为答案。

由于我们在找到第一个有效尺寸后即停止，最坏情况下的总体复杂度为
O(m·n·min(m, n))（对 m, n ≤ 50 仍然很快）。