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(不止演算法)
知識星球:不止演算法
- leetcode 第 312 場演算法比賽
- leetcode 第 311 場演算法比賽
- leetcode 第 310 場演算法比賽
- leetcode 第 286 場演算法比賽
- 請教下,go HTTP 服務如何同時支援 GET 與 POST
- 設計模式之迭代器模式
- 佇列卡住?方向錯了,使出十八般武藝也沒用
- 兩臺電腦如何複製資料,同事的方法我震驚了
- 影片的位元率、關鍵幀、FPS啥意思?
- Leetcode 第 171 場比賽回顧
- TCP服務端主動斷開連線問題
- Leetcode 第 179 場比賽回顧
- 觀看得到與B站的跨年晚會
- Leetcode 第 169 場比賽回顧
- Leetcode 第 168 場比賽回顧
- Leetcode 第 166 場比賽回顧
- Leetcode 第 165 場比賽回顧
- Leetcode 第 164 場比賽回顧
- 開始使用 vscode 了
- Leetcode 第 161 場比賽回顧