樣例
示例?1:
輸入:
[
?[ 1, 2, 3 ],
?[?4, 5, 6 ],
?[?7, 8, 9 ]
]
輸出: [1,2,3,6,9,8,7,4,5]
示例?2:
輸入:
[
??[1, 2, 3, 4],
??[5, 6, 7, 8],
??[9,10,11,12]
]
輸出: [1,2,3,4,8,12,11,10,9,5,6,7]
解題
https://www.cnblogs.com/techflow/p/12790451.html通過(guò)螺旋丸我們都知道螺旋形是什么意思，所以所謂的螺旋矩陣，就是按照螺旋形的順序來(lái)遍歷一個(gè)數(shù)組，或者說(shuō)矩陣。我們可以看下下圖：
箭頭標(biāo)注的順序就是螺旋的順序，這道題讓我們求的就是按照螺旋的順序遍歷之后的結(jié)果。背景
這道題的題意非常簡(jiǎn)單，我想大家肯定都能看明白，但是真的要上手去做會(huì)發(fā)現(xiàn)還是蠻困難的。主要的難點(diǎn)就是我們遍歷的順序一直在變化，并且變化的速度也是在變化的。雖然從某種程度上來(lái)說(shuō)，這些變化都是有跡可循的，但是即便如此，把這些規(guī)律抽象出來(lái)寫成簡(jiǎn)單易懂沒(méi)有bug的代碼也并不是一件容易的事情。如果我沒(méi)有記錯(cuò)的話，當(dāng)年我大二的時(shí)候?qū)W校里的acm校賽有一題就是這個(gè)，一模一樣的原題。雖然非常簡(jiǎn)單，每個(gè)人都知道怎么做，但是最后的通過(guò)率并不高。這并不完全是出題人的惡意，其實(shí)這類問(wèn)題在acm的比賽當(dāng)中還是很常見(jiàn)的。經(jīng)常會(huì)有一些題目很清晰明確，你只需要照著實(shí)現(xiàn)就可以了的題目。考察的就是選手的抽象和編碼能力，雖然題意不難，但是在比賽高壓的場(chǎng)景下想要快速寫出一個(gè)幾百行包含一系列復(fù)雜邏輯的程序并且沒(méi)有bug，還是非常困難的一件事。由于這類題目的關(guān)鍵就是讓我們模擬出來(lái)題目的意思，所以也被稱為模擬題。想要比較順手地寫出這道題，需要一個(gè)很常用的技巧或者說(shuō)慣例，這也是這篇文章的關(guān)鍵。方向數(shù)組
在許多問(wèn)題當(dāng)中我們經(jīng)常會(huì)遇到這樣一個(gè)問(wèn)題，比如我們需要遍歷一個(gè)迷宮，需要沿著現(xiàn)實(shí)世界當(dāng)中上下左右或者是東南西北的方向進(jìn)行移動(dòng)。在移動(dòng)的過(guò)程當(dāng)中自然就涉及各種各樣的方向，于是我們需要用代碼來(lái)表示方向。比如我們畫一個(gè)小人，它所在的坐標(biāo)是(x, y)，它有東南西北四個(gè)方向可以選。我們假設(shè)他每次移動(dòng)一個(gè)單位的距離，我們很容易就得出它往各個(gè)方向移動(dòng)之后的新坐標(biāo)。
根據(jù)數(shù)學(xué)上向量的定義，我們可以寫出這四個(gè)方向的方向單位向量：[0, 1], [0, -1], [1, 0], [-1, 0]。我們把這些向量存放進(jìn)一個(gè)常量數(shù)組當(dāng)中，就得到了方向數(shù)組。當(dāng)我們需要遍歷所有方向的時(shí)候，我們只需要遍歷這個(gè)數(shù)組即可。不僅如此，如果我們對(duì)方向的遍歷順序有要求，它也完全可以實(shí)現(xiàn)。比如在這題當(dāng)中，我們可以發(fā)現(xiàn)，螺旋遍歷每一次改變順序其實(shí)都是向左轉(zhuǎn)了90度。原本朝東的旋轉(zhuǎn)之后變成了朝南，朝南的變成了朝西，朝西的成了朝北，而朝北的成了朝東。那么我們只需要把方向按照東南西北的順序擺放，我們每次把方向數(shù)組的下標(biāo)增加一位并對(duì)4取模，就得到了下一個(gè)方向。這個(gè)技巧并不難理解，但是可以大大簡(jiǎn)化我們的代碼。解答
理解了方向數(shù)組之后剩下的就容易多了，我們觀察一下上面螺旋遍歷的過(guò)程，每一次改變方向遍歷的長(zhǎng)度雖然不同，但是每一次改變的原因是一致的，就是這個(gè)方向上已經(jīng)遍歷到頭了，所以我們需要變更方向。明白了這點(diǎn)其實(shí)就很容易了，我們只需要維護(hù)每個(gè)方向上的終點(diǎn)，每次到終點(diǎn)則進(jìn)行變向。由于矩陣當(dāng)中元素的數(shù)量是固定的，我們遍歷的次數(shù)也就知道了，所以只要把變更方向的事情處理好，這道題也就解決了。class?Solution:
????def?spiralOrder(self,?matrix:?List[List[int]])?->?List[int]:
????????#?定義方向數(shù)組
????????fx?=?[[0,?1],?[1,?0],?[0,?-1],?[-1,?0]]
????????n?=?len(matrix)
????????if?n?==?0:
????????????return?[]
????????m?=?len(matrix[0])
????????
????????ret?=?[]
????????#?定義邊界數(shù)組
????????#?邊界數(shù)組和旋轉(zhuǎn)的順序也是對(duì)應(yīng)的
????????#?第一次旋轉(zhuǎn)之后上邊界+1，所以第0位是上邊界
????????#?第二次旋轉(zhuǎn)之后，右邊界-1
????????#?以此類推
????????condition?=?[0,?m-1,?n-1,?0]
????????x,?y,?dt?=?0,?0,?0
????????for?i?in?range(n?*?m):
????????????ret.append(matrix[x][y])
????????????x_,?y_?=?x?+?fx[dt][0],?y?+?fx[dt][1]
????????????#?如果已經(jīng)越過(guò)邊界了，則需要轉(zhuǎn)向
????????????if?x_?0]?or?x_?>?condition[2]?or?y_?3]?or?y_?>?condition[1]:
????????????????#?更新邊界
????????????????if?dt?in?(1,?2):
????????????????????condition[dt]?-=?1
????????????????else:
????????????????????condition[dt]?+=?1
????????????????????
????????????????#?轉(zhuǎn)向，并且重新移動(dòng)
????????????????dt?=?(dt?+?1)?%?4
????????????????x_,?y_?=?x+fx[dt][0],?y+fx[dt][1]
????????????????#?print(x_,?y_)
????????????x,?y?=?x_,?y_
????????????
????????return?ret
我們觀察一下代碼，還有一個(gè)我們剛才沒(méi)有提到的細(xì)節(jié)。我們?cè)谝苿?dòng)的時(shí)候，并不是直接在原變量上進(jìn)行變更，因?yàn)槿绻坏┮苿?dòng)超界或者觸發(fā)其他非法的情況，那么我們就無(wú)法回滾了。所以我們會(huì)創(chuàng)建新的x和y的變量來(lái)表示移動(dòng)之后的位置，即使移動(dòng)到了非法位置，也不會(huì)影響之前的結(jié)果。這也是一個(gè)常用的技巧，在Python當(dāng)中，我們?cè)谧兞磕┪布由舷聞澗€表示這是一個(gè)影子（克?。┳兞俊?/section>總結(jié)
我個(gè)人認(rèn)為今天的題目出得不錯(cuò)，初學(xué)者很有必要親自動(dòng)手做一下。因?yàn)樵谧鲱}的過(guò)程當(dāng)中我們可以很具體地學(xué)到方向數(shù)組這個(gè)很有用的解題技巧，它在搜索問(wèn)題當(dāng)中廣泛使用，可以說(shuō)是做算法題必須會(huì)的技巧之一。可能你會(huì)覺(jué)得我們通過(guò)邊界判斷是否需要轉(zhuǎn)向的邏輯看起來(lái)有些復(fù)雜，這并不是必須的。我們也可以使用一些其他方法來(lái)代替，比如我們可以開(kāi)辟一個(gè)數(shù)組記錄已經(jīng)遍歷過(guò)的位置來(lái)代替邊界的判定，和使用邊界判定的方法相比，這樣做消耗的空間要更大一些，并且通過(guò)邊界判定的方法更加考驗(yàn)思維一些，因此我個(gè)人比較推薦。好了，今天的文章就到這里，如果覺(jué)得有所收獲，請(qǐng)順手點(diǎn)個(gè)在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動(dòng)力。
