Leetcode 第 161 場比賽回顧

語言: CN / TW / HK

零、背景

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

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

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

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

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

一、交換字元使字串相等

題意:給兩個長度相等的字串,都只包含字母 xy

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

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

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

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

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

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

1)上下都是 x ,不需要交換。

2)上下都是 y ,不需要交換。

3)上是 x ,下是 y ,記為 x 出現的次數。

4)上是 y ,下是 x ,記為 y 出現的次數。

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

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

例如對於 xxyy 字串,一次交換後,就都可以變成 xy 了。

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

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

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

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

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

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

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

P2P3 由於字元的個數的問題,無論如何也沒辦法使兩個字串相等。

對於 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 陣列,我們挑 57 ,然後就可以 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(不止演算法)

知識星球:不止演算法