Leetcode 第 161 場比賽回顧

零、背景

上次的第 160 場比賽我沒參加，昨晚的第 12 場單週賽我因為看 IG 比賽也沒參加。

由於個人時間有限，沒辦法一一在公眾號寫成文章分享給大家了。

所以我想著可以利用零碎時間，在我的免費知識星球分享這些比賽題。

感興趣的朋友可以下載知識星球 app 搜尋“不止演算法”加入星球，學習各種演算法題解吧。

下面就來看看今天第 161 場比賽的題解吧。

一、交換字元使字串相等

題意：給兩個長度相等的字串，都只包含字母 x 和 y 。

問能夠通過一系列交換，使得兩個字串相等。

如果可以，求最少交換次數。

交換規則：每次可以從兩個字串中分別挑選一個字元，進行交換。

思路：我們先來判斷是否存在答案，然後再來尋找最優答案。

假設第一個字串在上面，第二個字串在下面。

則相同位置的字元存在四種組合。

1）上下都是 x ，不需要交換。

2）上下都是 y ，不需要交換。

3）上是 x ，下是 y ，記為 x 出現的次數。

4）上是 y ，下是 x ，記為 y 出現的次數。

可以發現，對於情況一和情況二是不需要交換的，我們只需要對情況三和情況四進行交換。

而對於兩個情況三，我們通過一次交換則可以使兩個位置都相等。

例如對於 xx 和 yy 字串，一次交換後，就都可以變成 xy 了。

情況四也一樣，可以一次交換消除兩個不相等的位置。

那先進行兩兩交換，最後依舊剩餘四種情況。

P1）零個情況三、零個情況四

P2）零個情況三、一個情況四

P3）一個情況三、零個情況四

P4）一個情況三、一個情況四

面對這四種情況，可以發現 P1 已經使兩個字串相等了。

而 P2 和 P3 由於字元的個數的問題，無論如何也沒辦法使兩個字串相等。

對於 P4 ，則還是可以相等的，只是沒辦法一次交換消除兩個了，需要兩步才能使字串相等。

具體操作步驟是：先上下交換，然後交叉交換，如下圖。

yx => xx => xy
xy => yy => xy

由此我們就可以判斷是否有答案了。

那怎麼證明上面的步驟是最優的呢？

其實很簡單，一次交換最多可以消除兩個，如果都能消除那就是最優答案。

如果沒有消除完，那最後肯定是 P4 狀態，需要多一次操作才能消除。

而其他交換，則是一次消除一個或者都不消除，這樣自然需要更多次數了。

想想每次減二與每次減一或不減，誰更快到達零呢？

二、優美子陣列的個數

題意：給一個數組，如果某個子數組裡面奇數的個數恰好為 k 個，則稱這個子陣列為優美子陣列。

求優美子陣列的個數。

思路：

第一種方法是暴力列舉所有的子陣列，判斷是不是優美子陣列。

子陣列個數是 N^2 個，判斷需要 N 次，所以複雜度是 N^3 ，肯定超時了。

第二種方法是以某位置開始，列舉判斷這個位置為字首的優美子陣列個數。

由於是字首，可以累積統計奇數的個數，所以判斷複雜度就是 O(1) 了。

但是子陣列這個是硬傷，總體複雜度是 O(n^2) ，ACM中還是超時，LeetCode 上我沒試。

第三個方法就是滑動視窗了。

我們先看一個最優子陣列，如果這個子陣列右邊相鄰的數字還是偶數，則把這個偶數加進來依舊是優美子陣列。

左邊也是一個道理。

大概如下圖。

0001...10000

假設兩個 1 這個子陣列已經使最優子陣列了。

左邊有 3 個偶數，右邊有 4 個偶數，左邊和右邊任意選擇形成的子陣列都是優美的。

左邊可以有 4 中選擇（選 0~3 個），右邊可以有 5 中選擇（選 0~4 個）。

由於左邊和右邊互不影響，所以共有 4*5=20 中選擇。

所以我們每找到一個左右邊界都是奇數的最優子陣列時，統計左右偶數的個數，就可以求出總個數了。

由於只掃描一遍陣列，複雜度是 O(n) 。

三、移除無效的括號

題意：給一個字串，其中有一些左括號和右括號。

求刪除最少的字元，使得括號匹配，但會刪除後剩餘的字串。

思路：肯定只刪除括號字元了。

這裡其實有一個知識點都被大家忽略了，從而導致第一次看這道題，不知道怎麼做。

我們怎麼判斷一個字串是否是括號匹配的？

使用棧儘量的去匹配，直到遍歷完了棧中還有左括號，或者遇到右括號但是棧為空。

對於第一種遍歷完了，這個其實就已經找到了最長的能夠匹配的括號了。

棧中的都是左括號，只能刪除。

而對於第二種遇到右括號棧為空，那當前字元確實沒啥用，刪除就行了。

所以這道題就變得簡單了，在遇到第二種情況時，標記刪除，然後繼續匹配即可。

四、是否是好陣列

題意： 給一個正整陣列成的陣列，問是否可以從陣列中挑一些元素，使得這些元素乘以任意一個整數，使得和為 1 。

例如，對於 12,5,7,23 陣列，我們挑 5 和 7 ，然後就可以 5*3 + 7*(-2) 得到 1 了。

思路：其實這道題比較迷惑人。

我們完全可以使用這個陣列來當做幾個，對於那些沒挑的元素，使用整數 0 就行了。

所以接下來問題就是，怎麼判斷這個陣列有沒有答案。

先來看兩個數字，什麼時候才可以組合得到 1 呢？

顯然是最大公約數為 1 的時候，其他時候肯定都有答案（高中數學知識）。

證明也很簡單。

假設我們是用過遞迴減法來證明最大公約數是 1 ，這個遞迴減法的展開就是兩個數字的加加減減。

使用遞迴取模來證明也一樣，取模本質上是進行了很多次減法嘛。

如果是多個數字呢？那自然判斷多個數字的最大公約數是否是 1 了。

證明其實和兩個數字一樣。

第一步先兩個數字加加減減得到最大公約數，如果是 1 結束。

第二步，如果還有下一個數字，使用前面得到的最大公約數當做新的數字，回到第一步，來與下一個數字求最大公約數。

第三步，此時最大公約數不為 1 ，沒有答案。

五、最後

這次比賽其實還算簡單，做題耗時如下。

第一題用了19分鐘。 第二題用了20分鐘。 第三題用了8分鐘。 第四題用了4分鐘。

不過由於我的敲程式碼速度比較慢，這次比賽排名還是比較靠後。

後面我繼續啟動練習打字了。

以前，我習慣於讀電子書。

對於那種幾十分鐘的電子書音訊講解，我之前是抗拒的。

因為我覺得那種效果不大。

就像現在的很多課程，XXX技術的五大問題，XXX技能20講，XXX技術三十六招等等。

看著很有用，但是實際學習的時候，發現很像雞湯。

那些課程一會就聽完了，沒有自己的實踐，沒有自己的思考，沒有自己的沉澱，最後自己心中只知道一些名詞，其他的什麼都沒留下。

為什麼會這樣呢？上面我提到了，沒有實踐、思考、沉澱。

如果我們能夠自律的進行實踐練習、反覆琢磨思考為什麼，最終形成自己的方法論後，那這些課程自然是有用的。

另一方面，如果看一本書前能夠提前大概瞭解一下對應的核心主題，那對讀書也有很有幫助的。

所以，昨天我嘗試下載了樊登讀書 app，閱讀了推薦給我的幾本書，比如《終身成長》、《刻意練習》、《非暴力溝通》等。

發現還是學到不少東西。

比如《終身成長》裡面，人在某一領域的成功與失敗關鍵在於思維模式的差異。

失敗的人是固定型思維，成功的人是成長型思維。

固定型思維的人遇到糟心事會認為運氣不好，失敗了會怪別人，或者認為自己就這樣不會成功的。

成長型思維的人遇到糟心事會有邏輯的分析原因，探究根本，尋找解決方案。

比如 LOL 比賽，固定型思維就是比賽失敗了，認為自己就這樣了，年紀大了，個人能力有限。

而成長性思維遇到比賽失敗時，會想為什麼失敗，對方為何能成功，能不能從對面學習等等。

這其實也對應一句名言：失敗是成功之媽。

但是前提是你需要有成長型思維。

書中還介紹了很多例子來來介紹之間的差異，以及我們應該如何培養，感興趣的可以掃描下面二維碼免費閱讀。

-EOF-

本文公眾號：天空的程式碼世界

個人微訊號：tiankonguse

QQ演算法群：165531769（不止演算法）

知識星球：不止演算法