57. Insert Interval

此題給定一個沒有 overlapping 且按照起始座標排序的 interval 集合,然後再給一個 newInterval 放到該集合內,要合併 interval 使它們都不會重疊,最後返回新的 non-overlapping intervals。 本題的生活化的模擬,可以把題目想成自修室租借,然後插入自己的使用時段(亂入別人的使用時間…),最後返回整個自修室被租借的時段。

Continue reading

90. Subsets II

是經典的 78. Subsets 的進階版,現在數字會有重複(duplicate)。這邊使用 Backtrack 模板來求解。這個題目還有要注意的地方,就是 array 不一定是順序的,例如 test case: [4,4,4,1,4],這範例在我們去除重複答案的時候,若沒注意到有亂序的可能性,高機率會出錯。

Continue reading

78. Subsets

很經典的問題 : 冪集 the power set ,在數學上還蠻常見到的,理論上求得解答方式也很簡單,選或者不選排列組合,就可以得出答案。但在程式上要實現卻有一點點難度,故會被歸類到 Medium 等級。這邊使用 Backtrack 模板來解題。

Continue reading

40. Combination Sum II

這題是 39. Combination Sum 的進階,給定一個 array 和 target ,找出 candidates 中所有可以使數字和為 target 的組合,但 candidates 中的每個數字,在每個組合中只能使用一次。對比 39. 中的數字是可以重複使用,這題是不能重複使用的,但兩題本質沒有區別,依然是使用 DFS 和 backtrack 思想求解。寫到現在其實已經有感覺到一定的模板了,但多多比較與其他 backtrack 題型的差異才是最重要的。

Continue reading

39. Combination Sum

這題給了一個 array of distinct integer 以及目標總和 target , 求用此 array 來組成目標數字的所有組合。像這種要求返回所有符合要求解的題目,基本都是要利用到遞迴,類似的題目有 Subset 、 Permutation 、 Combination 等等,解題套路都是使用 DFS 和 Backtrack 來求得答案。

Continue reading

Permutations 另解

之前解題利用了交換 nums 裡面的兩個數字的方式,這次換另一種寫法,做出一個 inner list 收集可能的結果。基本解題思想都還是 Backtracking ,故把 leetcode46 和 leetcode47 重新解答一遍。

Continue reading

47. Permutations II

是經典的 46. Permutations 的進階版,現在數字會有重複(duplicate) 。這邊一樣使用 Backtrack 來求解。從數學上來說,n 個 element ,且將相同的事物歸為一組, 可歸成 k 組, 且每組有 m_i 個,其 Permutation 一共有 n!/(m_1!m_2!...m_k!) 種排序,為高中數學題中,需要思考下的題目;用程式模擬這個過程也有難度,故被歸類在 Medium 等級。

Continue reading

46. Permutations

是一道經典 distinct integers 的全排列問題,這邊使用 Backtrack 來求解。從數學上來說,n 個 element 的 Permutation 一共有 n! 種排序,思考起來算蠻簡單的,但要用程式模擬這個推導過程,卻是有點難度的,因此被歸類在 Medium 等級。

Continue reading

509. Fibonacci Numbers

這題是非常有名的 Fibonacci 數列,其特徵是除了前兩個數字之外,每個數字等於前兩個數字之和。解法可以帶出一些經典觀念和想法,例如 :

  • Dynamic Programming
  • 迭帶 for-loop
  • recursion 遞迴

由於 Fibonacci 數列的時間空間複雜度計算比較特別,加上可以很初步引入很多的思考方式,故雖然這題是 easy ,我還是做個紀錄。

Continue reading

反轉 Linked List 是一道經典的題目,可以用分別用 :

  • 指針 (iterative)
  • 遞迴 (recursive)

兩種截然不同的風格來解答。個人認為是蠻好的題目,可以多寫幾次,並從各種不同的解答方式來說明思考,故在此筆記。要說簡單也不算,對於 recursive 解法一開始我覺得有點難理解 ! 雖然被歸類在 Easy,但我私心覺得蠻容易打擊第一次做的人的…

Continue reading

Author's picture

李昀陽 YunYang Lee

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

Software Engineer

Taiwan