Leetcode 第126場比賽回顧
一、背景
前面做過 Leetcode 的第 88 場比賽,並寫了《 Leecode 第88場比賽回顧 》筆記。
今天簡單的做了 Leetcode 第 126 場比賽,也簡單的記錄一下。
二、查詢常用字元
題意很簡單,給一些字串,求字串的公共子序列。
這裡還要求,允許字串亂序,輸出的時候公共子序列從小到大輸出。
如果純粹是公共子序列,那麼這道題就需要使用一些高階資料結構才能解決。
但是這裡允許字串亂序,那這個問題就可以簡化為計數問題了。
求多個字串的公共子序列,其實就是迴圈依次求每個字串和當前答案的公共子序列,即迴圈合併即可。
而對於兩個字串的計數合併,則是對每個字母計數統計,然後分別取最小值即可。
至於字串拆分,就是一個迴圈而已,這裡就不上程式碼了。
當然,我實際做的時候,沒有拆分為三個函式,而是一個迴圈搞定的,這裡拆分為三個函式好方便大家理解。
三、檢查替換後的詞是否有效
具體題意是: abc
字串為有效字串,我們把 abc
插入到一個有效字串裡面形成的字串也是有效的。
例如 abc
插入到 abc
有四種插入法:
插入到最前面,形成 abcabc
有效字串。
插入到第一個位置 a
之後,形成 aabcbc
有效字串。
插入到第二個位置 b
之後,形成 ababcc
有效字串。
插入到最後面,形成 abcabc
有效字串。
問題:判斷給定的一個字串是否是有效的。
這道題是一個常見的題型:檢查資料是否符合某種遞迴的模式。
最經典的就是括號匹配問題。
而對應的解決方案就是使用棧來解決。
對於遞迴模式,之所以能夠使用棧來解決,就是因為掃描前面的資料時,暫時不知道是否滿足對應的遞迴模式。
而我們使用棧暫時把前面的資料儲存起來,當檢查發現滿足模式後,逆向的執行這個模式,就可以逆向的遞迴縮短字串。
如果給定的字串滿足要求,則掃描完出入字串後,棧裡面也應該剛好為空。
具體到這道題,則是發現第一個字元 c
時,棧頂的兩個元素肯定依次是 b
和 a
。 如果不滿足,則不是有效字串,如果滿足,則繼續下去即可。
四、最大連續1的個數 III
題意:給一個有 0
和 1
組成的陣列,我們最多允許對 K
個 0
的值變為 1
,求僅含 1
的最長連續子陣列的長度。
如果你看我上篇文章《 Leecode 第88場比賽回顧 》的話,會發現也有一道類似的題。
那道題是給了一堆 0
和 1
,求挑一個 0
使得這個 0
距離最近的 1
最遠。
我們的方法是累計計算中間的連續 0
的個數,然後算出答案來。
那對於我們這道題,其實可以使用類似的思想,不過這裡允許 0
不連續,並且最多隻能累計 K
個 0
。
具體來說,就是維護一個佇列,這個佇列需要滿足兩個條件。
一、佇列裡面的數字是連續的。
二、佇列裡面 0
的個數不超過 K
個。
而我們的答案就是佇列的最大長度。
而程式碼實現,則是掃描輸入的資料,一次入隊,並更新佇列 0
的個數。
如果 0
的個數超過限制,則隊首需要不斷出隊,直到滿足不超過 K
個。
具體如下:
這裡面有個主意實現就是,當不滿足條件時,需要迴圈出隊。因為隊首可能不是 0
。
由於我們確定不滿足條件時, 0
的個數肯定是 K+1
個。我們也可以直接先把隊首的 1
出隊,然後再出一個 0
。
當然,兩個思想在邏輯上是等價的,不過第一個演算法更通用寫,而後面這個則更個性化。
五、合併石頭的最低成本
題意是給 K
堆石頭,每堆知道有多少個。
然後會對這些石頭進行合併,每次把連續的 K
堆石頭合併為一堆,成本是這 K
堆石頭的總個數。
要求不斷的合併下去,直到所有石頭合併為一堆,求最小成本。
如果不能合併為一堆,則返回 -1
。
面對這道題,我們首先需要判斷是否能合併為一堆。
簡單觀察即可發現,每合併一次,石頭的堆數就減少 K-1
。
所以我們可以推匯出這樣一個等式: N - p * (K - 1) = 1
,其中 N
是石頭的總堆數, p
是合併的次數。
公式轉化一下,則可以得到一個判斷是否有答案的不等式: (N - 1) % (K - 1) == 0
。
接下來,就是假設有答案,怎麼得到最優的答案了。
其實,在看到這個問題時,第一眼想到的是哈夫曼樹。
但是哈夫曼樹的策略是貪心演算法,即不斷的挑選最小的 K
個數字,而且很容易證明其正確性。
而我們這道題必須是連續的 K
個數字,貪心的話還無法證明其正確性,所以需要換個思路了。
既然是類似於哈夫曼樹的題,就應該先來看看這顆樹長什麼樣子,樹的圖形畫出來後,題就變得比較形象了,一般也可以找到一種視覺化的方案來。
比如對於第一個示例,輸入是 stones = [7,7,8,6,5,6,6], K = 3
,我們可以手動畫出下面的最優樹。
我們觀察這個樹之後,可以發現這個問題可以劃分為一系列子問題來解決,大概如下圖。
我們對於給如的陣列序列,隨意的劃分為兩部分,使得第一部分合併為 1
堆,第二部分合併為 K - 1
堆。
這樣的劃分有很多,最優答案肯定是其中一個劃分(根據最優答案反推,我們可以劃分出這樣的圖)。
既然這樣,我們就可以寫出對應的遞迴程式碼了。
程式碼裡面有一個出口。
第一個是是否已經計算過,計算過則直接返回。
第二個是這個區間是否不足 K
個,不足則不需要合併,即答案是 0
。
第三個是這個區間是否剛好 K
個,這個時候直接合併為 1
個,答案就是區間和。
第四個就是上面我們提到的劃分,在多個劃分中找到最小的答案。
在計算劃分的時候,有個注意事項就是,只有兩個劃分可以合併時,我們才需要加上區間和。
而對於輸入,我們只需要初始化一下dp陣列,然後計算字首和即可。
六、最後
這次的四道題其實還是比較有點技術含量的,涉及到統計計數、堆、棧、動態規劃四個知識點。
另外,上篇文章提到,上次的時候程式設計環境弄了好久,現在終於差不多穩定了。
測試的時候,差不多是這個樣子。
答案對了,直接輸出 YES
,答案錯了,輸出 NO
,並把輸入和輸出都輸出來。
想要我的模板的,可以公眾號後臺回覆 leetcode
獲取原始碼。
-EOF-