LeetCode 挑戰題目總覽：30 Days of LC JavaScript Challenge（從 5 月 5 日起，台灣時間每天早上八點釋出新題目）
第 1 天：Create Hello World Function
解題程式碼
function createHelloWorld() {
return function(...args): string {
return "Hello World"
};
};
官方解題說明
https://leetcode.com/problems/create-hello-world-function/editorial/
暖身題，官方解題說明從函式開始逐個介紹到閉包的觀念，很適合新手學習跟老手複習，推薦閱讀！
第 2 天：Counter
題目說明
第一次呼叫 createCounter 回傳 n，後續每次呼叫都返回比前一次返回的值加 1。
解題方法
這表示要返回 n 原本的值同時需要將 n 加一，這讓我想到 ++ 遞增運算子。
可以用變數跟運算子的相對位置來記遞增運算子返回的值是計算前還是計算後的值：n++ 的 n 放在 ++ 的前面，所以是運算前的值；++n 是放在 ++ 的後面，所以是運算後的值。
解題程式碼
function createCounter(n: number): () => number {
return function() {
return n++;
}
}
官方解題說明
https://leetcode.com/problems/counter/editorial/
第 3 天：Counter II
題目說明
實作函式 createCounter，可以傳一個初始值參數，返回包含三個函式的物件，三個函式分別是 increment()、decrement()、reset()。
解題方法
increment() 、decrement() 都是回傳計算過後的值，變數要放在運算子的後面。reset() 需要將計算的基值重置成初始值，需要額外用變數儲存當前計算值，保留初始值 init。
解題程式碼
type ReturnObj = {
increment: () => number;
decrement: () => number;
reset: () => number;
};
function createCounter(init: number): ReturnObj {
let currentValue = init;
function increment() {
return ++currentValue;
}
function decrement() {
return --currentValue;
}
function reset() {
currentValue = init;
return currentValue;
}
return {
increment,
decrement,
reset,
};
}
官方解題說明
https://leetcode.com/problems/counter-ii/editorial/
第一次知道 Proxy 代理，可以用來攔截和修改目標物件的操作，如存取屬性、設定屬性值、調用函式等。以下是一些實際應用範例：
驗證寫入資料正確性
const validator = { set: (obj, prop, value) => { if (prop === "age") { if (typeof value !== "number" || value < 0) { throw new TypeError("Age must be a positive number"); } } obj[prop] = value; }, }; const person = new Proxy({}, validator); person.age = 25; // Works fine person.age = -5; // Throws an error存取物件屬性的日誌紀錄和追蹤
const target = { name: 'John', age: 25 }; const handler = { get(obj, prop) { console.log(`Accessing property "${prop}"`); return obj[prop]; }, set(obj, prop, value) { console.log(`Setting property "${prop}" to "${value}"`); obj[prop] = value; return true; }, }; const loggedTarget = new Proxy(target, handler); console.log(loggedTarget.name); // 輸出: Accessing property "name" // 輸出: John loggedTarget.age = 30; // 輸出: Setting property "age" to "30"
第 4 天：Apply Transform Over Each Element in Array
題目說明
返回 arr 經過 fn 處理後的結果，不能使用 Array.map()，可以理解成實作一個類似 Array.map 方法的功能。
解題方法
遍歷陣列的方式除了 Array.map 還有 for、for...of 與 Array.forEach() 可以用（for...in 是用在 Object），這幾個方法都需要一個額外的變數來儲存 fn 處理後的結果。因為在題目的 Constraints 條件內，輸入的 arr 不會數字以外的類型，所以可以省略輸入類型需為數字的防呆。
解題程式碼
function map(arr: number[], fn: (n: number, i: number) => number): number[] {
let resultArray: number[] = [];
arr.forEach((element, index) => {
resultArray.push(fn(element, index));
})
return resultArray;
};
官方解題說明
https://leetcode.com/problems/apply-transform-over-each-element-in-array/editorial/
閱讀了官方解題說明後，發現他們都沒有用到 Array.forEach()，在 playground 一跑才知道 forEach 的效能相較於其他方法較低，在處理 500 萬個元素時，它需要耗時最多達 321 毫秒的時間。雖然官方提供六種不同的解法，且效能存在差異，但要注意的是更高的效能並不代表更推薦使用該方法。
官方解法 1：寫入初始為空的陣列
這種解法是在一個初始為空的陣列中寫入值。newArr[i] = fn(arr[i], i) 寫入超出初始陣列範圍的索引。不鼓勵使用這種方式，不僅容易混淆，也可能導致性能慢和不可預測的問題。這個方法處理 500 萬個元素需要大約 250 毫秒。
function map(arr: number[], fn: (n: number, i: number) => number): number[] {
const newArr: number[] = [];
for (let i = 0; i < arr.length; ++i) {
newArr[i] = fn(arr[i], i);
}
return newArr;
};
官方解法 2：使用 for...in 迴圈
for...in 通常用在遍歷物件屬性，但也可以遍歷陣列的索引，並且對稀疏陣列（Sparse Array）特別有用。它僅遍歷陣列中已經被賦值的索引，略過那些尚未被賦值的索引。
在這個例子中，arr 是一個稀疏陣列，因為它的大部分元素都是 undefined。當你使用for...in 迴圈遍歷這個陣列時，迴圈只會遍歷到索引 1，因為這是唯一被賦值的索引。
let arr = Array(100); // 建立一個長度為 100 的稀疏陣列，所有元素都未定義
arr[1] = 10; // 在索引 1 的位置賦值，其他位置仍然未定義
for (let index in arr) {
console.log(index); // 僅輸出 "1"
}
這個方法處理 500 萬個元素需要大約 1000 毫秒，與內建的 Array.map() 方法最相似。
function map(arr: number[], fn: (n: number, i: number) => number): number[] {
const newArr: number[] = new Array(arr.length);
for (const i in arr) {
newArr[i] = fn(arr[i], Number(i));
}
return newArr;
};
官方解法 3：將值更新到陣列
這種解法是把 fn 處理後的結果用 for 迴圈一個一個地用 Array.push() 追加到新陣列的尾端，時間複雜度在平均情況下是 O(1)。這個方法處理 500 萬個元素需要大約 200 毫秒。
function map(arr: number[], fn: (n: number, i: number) => number): number[] {
const newArr: number[] = [];
for (let i = 0; i < arr.length; ++i) {
newArr.push(fn(arr[i], i));
}
return newArr;
};
官方解法 4：預先分配記憶體（Preallocate Memory）
建立陣列時就預先分配好所需的記憶體空間，這是因為當我們向陣列添加元素時，如果陣列原本沒有足夠的空間來存放新元素，JavaScript 會自動為陣列分配更多記憶體，這是一個相對較慢的操作。因此如果我們一開始就分配足夠的記憶體，那麼當我們添加元素時就不需要再重新分配記憶體。這個方法處理 500 萬個元素需要大約 40 毫秒。
function map(arr: number[], fn: (n: number, i: number) => number): number[] {
const newArr = new Array<number>(arr.length);
for (let i = 0; i < arr.length; ++i) {
newArr[i] = fn(arr[i], i);
}
return newArr;
};
官方解法 5：32 位整數數組（32 Bit Integer Array）
JavaScript 提供了一種名為 "Typed Arrays" 的特殊陣列，這種陣列只允許存放特定類型的數據，並且一旦創建，它的大小就不能更改。這種陣列對於需要儲存大量數據的情況非常有用，因為它比傳統的 JavaScript 陣列更節省記憶體。這個方法處理 500 萬個元素需要大約 20 毫秒。
function map(arr: number[], fn: (n: number, i: number) => number): number[] {
const newArr = new Int32Array(arr.length);
for (let i = 0; i < arr.length; ++i) {
newArr[i] = fn(arr[i], i);
}
return newArr as unknown as number[];
};
官方解法 6：記憶體內轉換（In-Memory Transformation）
這種方法是直接修改原始陣列，而不創建新的陣列。這種方法的優點是它最節省記憶體，因為它並不需要創建新的陣列。然而，這種方法的缺點是它會改變原始陣列的內容，這可能會導致一些難以預料的錯誤。這個方法處理 500 萬個元素需要大約 10 毫秒。
function map(arr: number[], fn: (n: number, i: number) => number): number[] {
for (let i = 0; i < arr.length; ++i) {
arr[i] = fn(arr[i], i);
}
return arr;
};
以上六種解法時間複雜度都是 O(n) ，空間複雜度除了解法 6 是 O(1) 其他都是 O(n)。（n 是 arr.length）
第 5 天：Filter Elements from Array
題目說明
僅返回 arr 經過 fn 處理後為真值的元素陣列，不能使用 Array.filter()，一樣可以理解成實作一個類似 Array.filter 方法的功能。
解題方法
這題可以看做是昨天的題目再加上是否為真值的判斷。但因為經過 fn 處理後為真值的元素數量不一定等於 arr 的長度，所以應該不能用預先分配記憶體的解法。
解題程式碼
function filter(arr: number[], fn: (n: number, i: number) => any): number[] {
const newArr: number[] = [];
for (let i = 0; i < arr.length; i++) {
if (fn(arr[i], i)) newArr.push(arr[i]);
}
return newArr;
}
官方解題說明
https://leetcode.com/problems/filter-elements-from-array/editorial/
說明涵蓋以下觀念：
什麼是真值與假值
邏輯運算符 OR
||、AND&&、Nullish Coalescing??
下方僅紀錄部分官方解法：
官方解法 3：預先分配記憶體（Preallocate Memory）
原本以為不能使用這種方法，但實際上是可行的。具體方法是先創建一個與原始陣列相同長度的新陣列，然後通過迴圈將真值元素更新到新陣列中，同時記錄實際真值元素的數量。最後，從新陣列的尾端刪去多餘的元素即可。
這種方法比較適用於結果陣列長度接近預先分配的記憶體數量，若是長度落差過大反而會浪費記憶體。
function filter(arr: number[], fn: (n: number, i: number) => any): number[] {
const result: number[] = new Array<number>(arr.length);
// 紀錄為真值的元素數量
let count = 0;
for (let i = 0; i < arr.length; i++) {
if (fn(arr[i], i)) {
result[size] = arr[i];
size++;
}
}
// 從尾端開始移除多餘的初始未定義值
while (result.length > count) {
result.pop();
}
return result;
}
官方解法 4：就地進行操作（Perform Operations In-Place）
這個解法類似於解法 3，但是直接使用傳入陣列的記憶體，沒有額外創建 result 陣列。
儘管這種解決方案效率高，但通常不建議修改傳入函式的參數。這是因為函式的使用者可能不希望他們的陣列被修改，可能會導致錯誤。另外，需要注意的是內建的 Array.filter() 不會改變輸入的陣列。
function filter(arr: number[], fn: (n: number, i: number) => any): number[] {
let count = 0;
for (let i = 0; i < arr.length; i++) {
if (fn(arr[i], i)) {
result[size] = arr[i];
size++;
}
}
while (result.length > count) {
result.pop();
}
return result;
}
解法 2（for..in）和解法 5（內建）是最慢的，因為它們處理了稀疏陣列的情況。
解法 1（push）在大多數元素被移除的情況下是最快的。這是因為在這種情況下，需要進行昂貴的 push 操作的次數較少。
解法 3（預先分配記憶體）和解法 4（就地操作）在只有少數元素被移除的情況下表現最好。這是因為在這種情況下，需要進行 pop 操作的次數較少。解法 4 比解法 3 更快，因為它不需要創建新的陣列。
所有解法時間複雜度都是 O(N) ，空間複雜度除了解法 4 是 O(1) 其他都是 O(N)。（N 是 arr.length）
在計算空間複雜度時，我們只考慮隨著輸入規模變化而變化的部分。在解法 4 中，我們並沒有創建新的數組，而是在原始數組上進行操作，所以並沒有使用與輸入規模相關的額外空間。我們只使用了固定的額外空間來存儲一些臨時變量或計數器，所以說解法 4 的額外空間複雜度是
O(1)。
第 6 天：Array Reduce Transformation
題目說明
按照陣列 nums 中元素的順序，從左至右（第一個到最後一個）逐個透過回調函式 fn 處理初始值 init 和每個元素上，最後將陣列縮減成單一值後返回。不能使用 Array.reduce()，一樣可以理解成實作類似 Array.reduce() 的方法。
解題方法
由於需要按順序處理陣列中的每個元素，並且每個元素的處理結果都會影響到下一個元素的處理，適合使用迴圈。在迴圈中，會需要一個變數來持續追蹤目前的處理結果。每次迴圈結束時，更新這個變數的值，將其設定為當前元素經過縮減函數處理後的結果。這樣就能夠將前一次迴圈的結果適當地帶入到下一次的處理中。最後迴圈結束後，只需要返回這個變數的值，即可得到陣列經過縮減處理後的結果。
解題程式碼
type Fn = (accum: number, curr: number) => number;
function reduce(nums: number[], fn: Fn, init: number): number {
let result = init;
for (let i = 0; i < nums.length; i++) {
result = fn(result, nums[i]);
}
return result;
}
官方解題說明
https://leetcode.com/problems/array-reduce-transformation/editorial/
官方提供三種解法，時間複雜度都是 O(n)，空間複雜度則會取決於回調函式 fn，如果計算陣列中所有的值總和為 O(1)，若是篩選陣列的在最壞的情況下則是 O(n)。
縮減函式（Reduce）的使用情境範例
陣列中所有的值相加
const nums = [1, 2, 3]; const sum = nums.reduce((accumulator, val) => accumulator + val, 0); console.log(sum); // 6根據鍵值建立索引（常見）
讓資料可以在 O(1) 的時間內透過鍵值存取，讓我想到 normalizr 這個函式庫就是專門為這種任務設計的。
const groceries = [ { id: 173, name: "Soup" }, { id: 964, name: "Apple" }, { id: 535, name: "Cheese" } ]; const indexedGroceries = groceries.reduce((accumulator, val) => { accumulator[val.id] = val; return accumulator; }, {}); console.log(indexedGroceries); /** * { * "173": { id: 173, name: "Soup" }, * "964": { id: 964, name: "Apple" }, * "535": { id: 535, name: "Cheese" }, * } */結合
Array.filter和Array.map當需要將
.filter().map()連接在一起使用，同時從陣列中移除元素並進行轉換的情況並不少見，但問題是這種方法由於會多創建一個陣列，效率較低。因此可以用單個縮減函式取代提高效能。const groceries = [ { id: 173, name: "Soup" }, { id: 964, name: "Apple" }, { id: 535, name: "Cheese" } ]; /** With filter and map */ var names = groceries .filter(item => item.id > 500) .map(item => item.name) /** With reduce */ var names = groceries.reduce((accumulator, val) => { if (val.id > 500) { accumulator.push(val.name); } return accumulator; }, []); console.log(names); // ["Apple", "Cheese"]
第 7 天：Function Composition
題目說明
這一題跟昨天的 Array Reduce Function 其實有點像，只是把陣列的元素從數字變成函式，可以理解成每次迴圈使用的回調函式都不同，最後返回的結果雖然變成函式，並且初始值由返回的函式傳入的值決定，但函式一樣是回傳單一值。
解題方法
嘗試解題的時，發現跟 Array Reduce Function 不一樣的地方是，函式組合計算順序是反過來的。可以看題目的舉例[f(x), g(x), h(x)] 組合後的結果是 fn(x) = f(g(h(x))) 所以是 h(x) 的計算結果傳給 g(x) 再傳給 f(x)。
若要將執行順序反過來，第一個念頭是把陣列反轉，但用 Array.reverse() 會改變原來的陣列，需要先複製一個陣列再做處理。不過印象中 reverse 效能沒有很好，也可以用 for 迴圈從最後一個當做執行起始點。
解題程式碼
// for...of + Array.reverse
function compose(functions: F[]): F {
const reversedFns = [...functions];
reversedFns.reverse();
return function(x) {
let result = x;
for (const fn of reversedFns) {
result = fn(result);
}
return result
}
};
const reversedFns = [...functions]; reversedFns.reverse(); 這兩行程式碼，這會增加執行時間。reversedFns = [...functions] 這行程式碼的時間複雜度是 O(n)，因為它需要遍歷 functions 陣列的所有元素。而 reversedFns.reverse() 這行代碼也需要 O(n) 的時間，因為它需要將陣列中的元素反轉。因此在時間複雜度上為 O(2n)，但因為常數倍數在時間複雜度分析時會被忽略，所以是 O(n)。
由於創建了一個新的陣列 reversedFns 來儲存反轉後的函式陣列，因此空間複雜度是 O(n)。
// for
function compose(functions: F[]): F {
return function (x) {
let result = x;
for (let i = functions.length - 1; i >= 0; i--) {
result = functions[i](result);
}
return result;
};
}
由於沒有額外的操作時間複雜度為 O(N)；也沒有創建新的陣列或是物件，因此空間複雜度是 O(1)。
官方解題說明
https://leetcode.com/problems/function-composition/editorial/
發現我少寫 if (functions.length === 0) return x; 這個判斷來處理 functions 為空的情況，雖然不影響輸出結果，但加上會使得函式的邊界條件更明確，可讀性更好。
官方解法 2：使用 Array.reduceRight()
原來 JavaScript 已經有內建反過來的 Array.reduce() 方法？！早說嘛！
function compose(functions: F[]): F {
return function (x: number) {
return functions.reduceRight((acc, fn) => fn(acc), x);
}
};
// 用 Arrow Function 簡化的版本
// const compose = (functions: F[]) => (x: number) => functions.reduceRight((acc, fn) => fn(acc), x);ａ