2022/04/14

簡單輕鬆十分鐘學會 Recursion (遞迴) 刷 LeetCode

一、Recursion

1.1 基本觀念介紹


遞迴就是在函式之中呼叫函式自己本身,本質上是將複雜的問題,拆分成具有相同性質的子問題,進而解決問題的方法。


一個基本的遞迴函式一定要有:

  • 終止條件 (基本條件)

  • 遞迴條件 (呼叫自己的條件)


如果沒有終止條件,就會無限循環直到當掉。




範例 1 : 假設輸入一個正整數 n,求 1 + 2 + … + n 的總和


我們可以很直覺的使用迭代 (迴圈) 的方式,將所有數字累加在一起。



但因為這個問題能拆成有規律的數個小問題,

如輸入正整數 2 → 1 + 2 = 3

輸入正整數 3 → 1 + 2 + 3 = 6


所以這時候就可以使用遞迴來計算。


Time complexity 是 O(n),Space complexity 是 O(1)


簡單輕鬆十分鐘 Linked List (鍊表) 刷 LeetCode

一、Linked List

1.1 基本觀念介紹



Linked list 是一種常見的資料結構,會包含 head 和 tail 的資訊,以 null 來代表 Linked list 的終點,使用 node 來記錄、表示、儲存資料。



1.1.1 Singly linked list




單向鏈結串列 (單鏈結串列、線性鏈結串列、普通鏈結串列) 是最基本的鏈結串列,其特點是鏈結串列的鏈結方向是單向的,對鏈結串列的存取要通過從頭部開始,依序往下讀取。


每個 node 則會包含 value 和 next (Pointer,指向下一個 node 的位置) 的資訊。