Python C++解魔方陣Leetcode 840 Magic Squares In Grid

An-Wen Deng
4粉絲
54 次觀看·2024年10月14日
Python C++解魔方陣Leetcode 840 Magic Squares In Grid.
影片一開始就是展示如何解一個3x3的魔方陣,5總是在中心
In the beginning of film is to show how to solve a 3x3 magic square, 5 is always in the center.
[codes on Leetcode]https://leetcode.com/problems/magic-squares-in-grid/solutions/5609811/magic-square-has-5-in-middle-beats-100/
[Leetcode程式]https://www.youtube.com/watch?v=dybiq3pg-Os&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk
各位好,我們來解今天立課的問題
今天立課的問題是第840題
這個是跟所謂的Magic Square是有關的
那我們來看一下這個Magic Square
這邊我們帶來一個做法是
一開始你就是在最上面的地方
你就從最小數字開始填
他是從1到9嘛
所以我們就填1
然後往右斜上方這邊
這邊應該是在填2
但他已經超過去了
所以他是在這個位置
這個位置相對來講就是在這邊
所以這裡當然就是要填2
好,再來是3
3的話是在這裡
那你右斜上方他已經有了
所以有的話你就填到他下面
所以這個是4
再來是5
實際上人家也有證明出來
3乘3的Magic Square
5一定是在中間的
那證明過程當中是用了一些線型代數
其實他就是在這個網頁
那我們看立課相關題目的說明
他是840題
Magic Square in Grid
他在這邊就是說一個Magic Square
3乘3的
基本上就是我們剛剛所提到的
從1到9
然後讓每一個Column
還有他那兩個對角線的和
都是相同的數字
在這邊的話,1到9的話
當然這個Sum一定是15
所以這沒有問題
好
所以他這邊他就是會給
Raw Column
這樣的一個Grid
這樣的一個
應該這樣講
2D的一個陣列,不是矩陣
他要我們去算
有多少3乘3的連續的
注意喔,他是連續的Magic Square
他這邊是用Subgrid在那邊
所以你要去數
基本上就是他裡面的
Submatrix,而且是連續的
他這邊有一點就是說
一個Magic Square
他只有數字是1到9
那裡面放的數字可能會最大到15
所以他裡面放的數字不一定只是1到9
他會有其他的數字
那我們看這邊一個簡單的立體
因為我們根據剛才的事實
我們知道他這邊5一定是在中間
所以唯一的可能就是他
這個Submatrix是不是Magic Square
那你大概簡單看一下
檢查他的Raw Sum
Column Sum
和他的兩個對角線
基本上都是15
所以這個是
所以這個答案當然就是1
好
那我們看一下
我們大概是怎麼樣去解這樣的問題
當中我們的解法當然就是
應用到一個事實就是說
他的Magic Square
他中間一定是5
好,那我們在這裡稍微看一下
我們大概解答
當中會用到的一個
一個Function就是IsMagic
他到底是不是
所謂的魔方陣3乘3的
那我們這邊顯示當然是Python
那我們在一開始我們就先看一下
這邊我們當然就先放一個容器Once
他是去看1到9是不是都是出現一次
一開始當然全部裡面都是Force
再來就是Raw Sum
Column Sum
我們在這邊的話
Raw Sum Column Sum
基本上都是各三個
然後再來就是
你可以用一個迴圈
我們這裡的迴圈當然是
所謂的Nasty Loop
基本上我們的i,j
這個是在他的中間的
中間的Index
因為我們是
碰到5我們才會進去
所以你就
Raw的部分當然就是
i減1到i加1
Column的部分當然是
c減1到c加1
然後我們就取
他在Index a,b的值
那就叫x
比較簡單
如果你這個x是超過他的範圍
因為他裡面有可能會
擺到15以內的數字
如果不是1到9
我們當然就直接跳出來
就是他是Force
這裡面呢因為
我們在前面已經把他
這個兩個陣列都
應該都已經建好了
他的初始都是0
所以當你在跑這個迴圈的時候
實際上來講的話
我們就可以分別將他
a減i加1的這個Raw sum
我們就加x
那在b減c加1的這個Column sum
我們就加上x
實際上是可以這樣做
就回圈
跑一次
其實你就可以將Raw sum
跟Column sum都把它算出來
那同時我們去檢查
這個x是不是剛好
是出現一次
如果他已經出現第二次
他就會再碰到
這個時候我們就Return Force
那當然
不管怎麼樣
就是說你碰到了
你就設True
那這個迴圈跑完之後
我們最後當然就
這些資料都收集好了
我們去檢查
是不是once從
第一個Index到最後
是不是都是True
都是True我們當然就繼續
只要有一個不是True
當然就Return Force
那我們再看
Raw sum當中是不是所有的
sum都是失誤
只要有一個不是我們當然就是Force
Column sum也是
那當然這個部分
我們是用
for loop去寫
你當然也可以用
所謂all的方式
不過我們這邊用比較簡單的方式去寫
然後最後
你當然不要忘記
這兩個對角線
基本上最關鍵的
就是IsMagic
這個部分
接下來我們看我們在
Leak Code上面的
一個情形
那我們在
Leak Code上面呢
我們這邊當然就是剛剛也講過了
所以這個部分我們當然
是先將這個IsMagic
定好
重點就是說你在
下面你在使用的部分
在這邊
我們當然就是R跟C
分別就是
這個Matrix它的
有幾個Raw
有幾個Column
那如果R小於3或者C小於3
當然沒什麼好講的
當然裡面不可能會有任何的
Matrix Square
當然是0
然後我們在這邊當然就是
也是一個
Nasty For Loop
分別IJ
那我們當然因為我們主要是看它
中間那個值是不是5
所以我們這邊是從
1到R-2
J的話是
1到C-2的部分去看
如果是
我們就加1 如果不是
當然就沒有變化
好 那
這裡面它有兩個Case
我們讓它跑一下
好 那我們Submit
看看
這是Python版的
速度也蠻快的
這邊大概
32毫秒
86%以上的人
這是我們Python的
版本 因為我們
只有檢查中間是5的
所以在速度上來講它就會很明顯
那我們接下來再看
C++的版本
好 C++的
版本也是類似的
那這邊的話
我們
這裡是採用Flip
Flip的話就是0變成1
1變成2
0變成1
1變成0
那它要每個剛好都出現一次嘛
所以在這邊的話我們就去
數它是不是出現9
所以這樣就可以檢查它的
一個唯一性
所以這是應該沒有問題
那下面的部分
當然這邊我們就用
C++裡面的
All of
這樣的一個用法
只要當中有一個
不適當的Return
False
然後再去檢查
是不是兩個對角線合都是失誤
那中間那個當然就不用
中間那個一定是5
好 那在這邊的話
這個邏輯也是跟Python完全一樣
所以我們
Run一次
Submit看看
那基本上
跑了好幾次每次都是0毫秒
好 那我們就先彈到這裡
by bwd6
