1895. 最大的幻方Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

一个 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.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 10⁶

# 思路

计算两条对角线

# 解法


class Solution {
    public int largestMagicSquare(int[][] grid) {
        int row = grid.length, col = grid[0].length;
        int maxLen = Math.min(row, col);

        for (int len = maxLen; len > 1; --len) {
            for (int i = 0; i + len <= row; ++i) {
                for (int j = 0; j + len <= col; ++j) {
                    if (search(grid, i, j, len)) {
                        return len;
                    }
                }
            }
        }
        return 1;
    }

    private boolean search(int[][] grid, int right, int up, int len) {
        int sum = 0;
        int temp = 0;
        for (int i = 0; i < len; ++i) {    //计算两条对角线
            sum += grid[right + i][up + i];
            temp += grid[right + len - 1 - i][up + i];
        }
        if (sum != temp) return false;
 
        for (int i = 0; i < len; ++i) {    //计算每行
            temp = 0;
            for (int j = 0; j < len; ++j) {
                temp += grid[right + i][up + j];
            }
            if (temp != sum) return false;
        }

        for (int j = 0; j < len; ++j) {    //计算每列
            temp = 0;
            for (int i = 0; i < len; ++i) {
                temp += grid[right + i][up + j];
            }
            if (temp != sum) return false;
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# 总结

分析出几种情况，然后分别对各个情况实现

#Java