LeetCode 解題筆記-7 Brick Wall

LeetCode 裡的這題Brick Wall 我摸索出了兩種解法,前者在跑runtime的時候炸掉了,現在刷LeetCode時有慢慢跟得上一些題目的思維,但有時候想出來的runtime都還是太高了,還是要慢慢磨練呢,那以下來講解Brick Wall的題目吧!

LeetCode Brick Wall題目詳解

中文翻譯此題為,我們將陣列元素化成一塊塊的磚牆,而陣列內的數字為磚牆的長度,而我們要找到的是一個位置能夠在橫穿最少的磚塊下(從縫隙中過去)貫通整個陣列,此處有個示意圖,我們來看一下!

一看到這題的時候,我一開始想的是我只要遍歷1~N的磚塊位置,一一去確認如果我在第1~N個位置貫穿整個陣列會得到的磚塊數量就可以了,而這個思路也確實是正確的,但實作上的寫法我在第一次寫的時候卻出了很多問題,我們先看看我成功跑出範例的第一個結果的程式碼。

在實作上這樣的寫法把整個問題變得有點複雜,因為我的寫法是,確認1~N的位置哪一個位置穿過最少磚塊,所以每遍歷一個位置的時候,實際上是需要將所有陣列都跑過才有辦法知道到底穿過幾個磚塊,並且這樣也產生了一個問題是我必須要透過紀錄磚塊的位置才能在每次遍歷時都找到正確的地方,這樣憑空講可能有點難懂,我們舉個例子,如果我現在遍歷到第五個位置,開始往下找,我要怎麼知道這個位置有沒有穿過第一個陣列的磚塊以及剩下陣列的磚塊呢,我必須要知道以五來說現在每個陣列跑到哪一個磚塊了,所以程式中寫了if i > current_block[j]就是這樣來的,這樣一步步實現之後雖然跑得出來,可是使用的空間和跑的時間都是天文數字,並且舉一個極端的例子,也是我後來submit的時候因為runtime被擋下來的例子。

[3000],[3000],[3000]

這題不用看也大概知道,答案是很明顯的,可是當我們帶入上述的程式,就會跑出3000*3000這種離譜的次數,原因就是因為我們這裡解題的思路是有點偏硬幹的,那我們到底要怎麼做出正確的思路呢?如果有認真思考的同學,可能已經想到了,我們可以從縫隙這個點出發!以下就來講解第二個思路。

更好的解題思路

剛剛我們有提到,我們一開始思考的方向是將1~N的位置穿過的磚塊數都記錄,最終找最少的,那我們從另一個角度來思考,如果我們將每一個陣列的縫隙位置都記錄起來,並且有重複的話就做加總,則最多縫隙的位置,不就是穿過最少磚塊的位置嗎?那可能會有同學問,使用縫隙有什麼好處?大家可以思考一下縫隙所代表的意義

代表陣列元素的加總

有了這層意義,就代表我們在做遍歷時,可以以陣列元素為基礎,而不需要以1~N的位置了,我們來看看以下的程式碼

left_counter = collections.Counter()

首先這次的程式碼會使用的counter這個數組,這樣我們就能夠去紀錄在同樣位置但不同陣列的縫隙究竟有多少個

count = 0
for row in wall:
    left = 0
    for i in range(len(row) - 1):
        left += row[i]  #紀錄縫隙
        left_counter.update([left]) #紀錄縫隙重複次數
        count = max(count, left_counter[left])
        print(left_counter)
return len(wall) - count

可以看到left這個宣告,這裡代表的是位置的意思,以1,2,2,1來講,總共的縫隙位置,就會有1,3,5這幾個位置,我們將其記錄下來之後放進left_counter內,並且每次都用max來看看目前哪個位置最多重複,就做更新,整體跑完之後,最後再以總共的長度扣掉縫隙,自然就會是穿過的磚塊次數了。

寫LeetCode下來我覺得一開始會碰到就是發現自己的思路雖然是對的,但其實都不是最快速且最便利的,久而久之就會寫的綁手綁腳,但我覺得一開始還是要勇敢地將自己的思路寫下來,即使跑不過,可以在去參考自己和他人的思路的差別,慢慢去訓練自己對於題目的敏銳度,今天的解題就到這裡拉!

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *