Leetcode 第 168 場比賽回顧

零、背景

leetcode 的這次比賽已經沒什麼技術含量，拼的是打字速度與電腦操作的速度。

然後，我的滑鼠壞了，複製個變數總是選不中，複製個測試用例也複製不了。

滑鼠我肯定會買一個的。

但是由這個問題，也看出 leetcode 的一個設計缺陷。

leetcode 題目上給了三四個測試用例，測試執行時，輸入卻只提供一個，而不能給一個選擇快速測試所有的。

寫完程式碼，穩重期間一般都會把提供的所有測試用例跑通過才會提交。

由此，所有做題的人都在重複做一件事情：將所有的測試用例從題目中提取出來，貼上進輸入框，點選執行。

如果 leetcode 直接提供一個多選框，選擇跑那些測試使用者，將會給做題的人節省很多時間。

leetcode 的工作人員看見了，可以優化一下。

接下來看看這四道題吧。

一、位數為偶數的數字個數

題意：給若干數字，問十進位制位數是偶數的數字有多少個。

思路：一個個求十進位制長度，然後判斷即可。

二、陣列劃分為連續K個數字

題意：給若干數字，問能否將陣列劃分為若干子陣列，子陣列是連續遞增且長度為 K。

思路：貪心即可。

不斷的從最小值找一個滿足條件的子陣列，剛好找完則存在，否則不存在。

優化：直接使用陣列查詢的話，複雜度很高。

可以使用 map 來進行數字統計，這樣 map 的 key 是天然有序的，就直接迭代即可找到後面的 k 個數字了。

三、出現次數最多的次數

題意：給一個字串，求出現次數最多的那個子串出現的次數。

這個問題比較繞。

首先是所有子串中出現的最多次數。

比如 A 子串出現 5 次，其他子串出現不超過 5 次。

那出現次數最多的子串就是 A ，然後 A 出現的次數是 5 。

所以出現次數最多的次數就是 5 。

當然，這個子串還有三個限制，比如子串長度最小是多少，最大是多少，去重後的字母個數不大於多少。

思路：考慮到可能任何子串都可能是答案，所以遍歷所有子串是在所難免的了。

不過，根據子串的三個限制，對於相同起始位置的子串，可以進行一個剪枝，使得需要遍歷的子串數量大大減少。

具體來說，就是相同起始位置的子串，一旦某個長度不滿足最大長度了，那後面的都不滿足。

四、最多的糖果

題意：題意相當複雜，聽我慢慢描述。

首先有 n 個盒子，每個盒子可能會上鎖，上鎖的話需要鑰匙才能開啟。 當然，盒子也不在身邊，也就是盒子和鑰匙同時在手上才能開啟盒子獲得盒子裡的寶物。

開啟盒子後，裡面會有糖果、鑰匙、其他盒子。

最開始給你一些已經解鎖的盒子，問通過不斷的開啟可以開啟的盒子，最多能獲取多少個糖果。

思路：主要是題目複雜，只要理解了題目，就可以發現，直接 BFS 或者 DFS 搜尋即可。

大概搜尋思路就是，根據現有的解鎖盒子，全部開啟，然後就得到一些新盒子和新鑰匙。

新盒子如果沒上鎖，就可以遞迴再次開啟。

新盒子如果上鎖了，可以看看自己有沒有鑰匙，有了，就開啟。

新鑰匙可以看看自己是不是已經有沒開啟的盒子，有了，也可以開啟。

其他情況就把新盒子和新鑰匙儲存起來。

五、最後

這次比賽最後一題再 ACM 中屬於模擬題，一般只要讀懂題意就可以做出來。

而第三題，有沒有更優的方法我還不知道，你認為有更優的方法嗎？

-EOF-

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

個人微訊號：tiankonguse

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

知識星球：不止演算法