主題

LeetCode - 1895. Largest Magic Square 解題心得

Not In My Back Yard | 2021-09-25 00:00:04 | 巴幣 2 | 人氣 31

題目連結:


題目意譯:
一個 k × k 幻方(Magic Square)為一個 k × k 填充著數字的網格使得每列之和、每行之和以及兩條對角線上元素和皆相等。幻方中的整數不需要彼此相異。每個 1 × 1 網格為一個平凡(Trivial)幻方。

給定一個 m × n 整數網格,回傳這個網格中所能找到的最大幻方之大小(即邊長 k)。

限制:
m == grid.length
n == grid[i].length
1 ≦ m 、 n ≦ 50
1 ≦ grid[i][j] ≦ 10 ^ 6



範例測資:
範例 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


解題思維:
利用前綴和(Prefix Sums)的概念可以快速地求得每一列(行)某個區段的區間和(如這題),以便窮舉時判斷。

我們從幻方大小最大的開始窮舉看看,即 k = min(m, n) 跑到 k = 1。接著對於每個 k 值,窮舉 k × k 的「左上角」,而這樣子的「幻方候補」會有 (m - k + 1) × (n - k + 1) 個(從 (0, 0) 到 (m - k, n - k))。

然後對於每個左上角座標 (R, C) 所代表的幻方候補,用上面的前綴和取得每一列(第 R 列到第 R + k - 1 列)、每一行(第 C 行到第 C + k - 1)的區間和,然後看這些總和值是否相同,然後再加總兩條對角線上的元素看是否也是相同的總和值。

如果有任何一者不符合,則繼續到下一個幻方候補。如果是,則我們便找到一個 k × k 的幻方,因此此時的 k 值即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作