16. 3Sum Closest

這題跟 15 題相似,又增加了些許難度。題目敘述一樣也很簡單 : 求 nums 內最接近 target 值的三數和。優化關鍵點一樣是,把 nums 排序,這樣就可以確定指針滑動方向。

Continue reading

這道題要我們從有序數組中去除重複項,題目難度雖然被歸為 easy 等級,但在條件限制上的討論,蠻多東西可以釐清討論的。 英文方面寫得蠻長,記得要看到最後因為有寫一些限制如 :

  • O(1) extra memory
  • The relative order of the elements should be kept the same.

所以不能用 Set 或另開 array 去寫。另外也花了些篇幅去說明,只要原 array 前面長度部分內,有把所有不重複數字列出來就好,不需要在意後面 array 的元素和 array 的長度。

Continue reading

前面有介紹用 dp 方式把這題給解了,但看一下 Related Topics 發現也可以用 Binary Search 求解,上網參考大神們的解法,感覺特別巧妙。因為這題可用 dp 和 Binary Search,也變成是一道高頻難題。 這邊記錄一下大神們的想法。

Continue reading

這題真的蠻難的,一開始看題目我也覺得很繞口,給了一個非負數的 nums 和一個 m 代表把 nums 分成 m 個 group 且 每個 group non-empty 並取 m 個 group 中的最大值。但注意,前面只是代表一種切法而已,我們是要找所有可能切法之中的最小值。看一下 Related Topics 發現可以用 Binary Search 和 DP 求解,也是一道高頻題目。

Continue reading

877. Stone Game

石頭遊戲,兩個人輪流選石頭,Alex 先選,每次只能選開頭或結尾,最終獲得石頭總數多的人獲勝。 乍看之下不好想到可以用 DP 解,但其實可用一個 2D-state 去描述遞迴的狀態。 這題一開始會好奇是因為負評倒讚很多,個人是感覺能從 Game Theory 單純想出這結論也是蠻厲害的…

Continue reading

這題是求最長相同的子序列,可用 Dynamic Programing 來做,最難的還是想出狀態函數。這裡使用 2D-dp ,其中 dp[i][j] 表示 :

  • text1 的前 i 個字符
  • text2 的前 j 個字符

的最長相同的子序列的字符個數

Continue reading

63. Unique Paths II

這題是 62. Unique Paths 的延伸,能選擇往下或往右走直至終點為止,要求出有多少種可能走法,但多了一個限制,會在路徑中加了一些 obstacle 擋住了某些路徑。是一道典型的 Dynamic Programming - 2D matrix 類型的題目。和爬樓梯等都屬於動態規劃中常見題目,因此也經常會被用於面試之中。

Continue reading

139. Word Break

一道很經典的題目,是給定一 string ,能不能分被拆分成 wordDict 裡面的單詞。注意這題,wordDict 裡面的單詞可以重複使用,即單詞使用沒有次數限制,所以 string 可以分成任意段,這就增加了題目的難度。解法蠻多種的,可先從 brute force 下手,再加上暫存優化後,就是蠻標準的 dp 解了,來解一下吧。

Continue reading

這題我看起來也是很技巧性的題目,一開始要把 subarray 的特性掌握的淋漓盡致,並且想到用 hashmap 來建立快速查找關係,真的有點困難…但也是這道題的魅力吧 ! 基本上 hashmap 題目大概都會偏向這種步驟應用,多注意可以讓自己視野開闊。

Continue reading

Author's picture

李昀陽 YunYang Lee

Welcome to my Tech Note. You can read some of the chapters below.

Software Engineer

Taiwan