LeetCode 挑戰題目總覽:30 Days of LC JavaScript Challenge(從 5 月 5 日起,台灣時間每天早上八點釋出新題目)
第 8 天:Allow One Function Call
題目說明
建立一個讓傳入的函式 fn
只能呼叫一次的函式 once
,後續呼叫函式皆返回 undefined
。
解題方法
如果只能呼叫一次,需要紀錄函式被呼叫的次數。
解題程式碼
function once<T extends (...args: any[]) => any>(
fn: T
): (...args: Parameters<T>) => ReturnType<T> | undefined {
let called = false;
return function (...args) {
if (called) return;
called = true;
return fn(...args)
};
}
官方解題說明
https://leetcode.com/problems/function-composition/editorial/
第 9 天:Memoize
題目說明
建立一個讓傳入的函式 fn
在輸入相同參數時,永遠只會呼叫一次的函式 memoize
,後續使用相同參數呼叫函式將返回第一次返回的值(快取)。在 Constraints 有提到,傳入的函式會是 sum
、fib
或 factorial
。
解題方法
跟前一題 once
有點像,但這次要紀錄的是傳入的參數與返回的值,若是已經傳入過的參數則不能呼叫函式。傳入的參數有可能為一個或兩個,不太確定用什麼方式來判斷傳入的是相同參數。參數看起來都是整數不會是物件,也許可以嘗試把參數陣列轉成字串來比較與判斷。傳入參數與返回的值的對應第一個念頭是用 Map 來儲存。
解題程式碼
type Fn = (...params: any) => any;
function memoize(fn: Fn): Fn {
const cache = new Map();
return function (...args) {
const cacheKey = JSON.stringify(args);
if (cache.has(cacheKey)) {
return cache.get(cacheKey);
}
const result = fn(...args);
cache.set(cacheKey, result);
return result;
};
}
官方解題說明
https://leetcode.com/problems/memoize/editorial/
這種類型的優化稱作 Memoization,也是 Higher-Order Function (高階函式)的一個重要應用範例。
第 10 天:Curry
(LeetCode 已上 Premium 之鎖,相同題目可參考 1. implement curry() | BFE.dev - prepare for Front-End job interviews.)
題目說明
建立一個將傳入的函式 fn
Currying。Currying 函式是一種接受較少或與原始函式相同數量參數的函式,並返回另一個 Currying 函式或與原始函式返回值相同的值。
解題方法
知道 Currying 函式長怎樣,以前明明寫過但要實作竟然又腦袋一片空白⋯⋯掙扎一陣子還是看官方解題吧!
官方解題說明
https://leetcode.com/problems/curry/editorial/
Currying 函式使用情境範例:
可重複使用的函式
const add = (a: number) => (b: number): number => a + b; // Create a new function 'add5' by calling the curried 'add' function with the value 5. // The returned function will take a single argument 'b' and add it to 5. const add5 = add(5); // Now, when we call 'add5' with a value (e.g., 3), it adds 5 to the input value, resulting in 8. const result: number = add5(3); // 8
事件處理:可用於建立有特定配置的事件處理函式,同時保持原本通用的事件處理函式。
type EventHandler = (event: Event) => void; const handleClick = (buttonId: number): EventHandler => (event: Event) => { console.log(`Button ${buttonId} clicked`, event); }; const button1Handler: EventHandler = handleClick(1); document.getElementById("button1")?.addEventListener("click", button1Handler);
自定義呼叫 API:可以基於通用 API 呼叫函式建立更特定的 API 呼叫。
type ApiCall = (endpoint: string) => (params: any) => Promise<Response>; const apiCall = (baseUrl: string): ApiCall => (endpoint: string) => (params: any) => fetch(`${baseUrl}${endpoint}`, { ...params }); const myApiCall: ApiCall = apiCall("https://my-api.com"); const getUser = myApiCall("/users"); const updateUser = myApiCall("/users/update"); // Usage: getUser({ userId: 1 }); updateUser({ userId: 1, name: "John Doe" });
組合高階函式與函式組合
type ComposeFn = <T>(f: (x: T) => T, g: (x: T) => T) => (x: T) => T; const compose: ComposeFn = (f, g) => x => f(g(x)); const double = (x: number): number => x * 2; const square = (x: number): number => x * x; const doubleThenSquare = compose(square, double); const result: number = doubleThenSquare(5); // (5 * 2)^2 = 100
官方解法 1
可以使用遞迴的方式來實作,每次呼叫該方法時都會返回一個新的函式,並且使用的參數少於原始函式。直到收集到足夠數量的參數為止再呼叫原始函式。
function curry(fn: Function): Function {
return function curried(...args: any[]) {
// 用 Function.length 來表示該 function 預期被傳入的參數數量
if (args.length >= fn.length) {
return fn(...args);
}
return (...nextArgs: any[]): any => curried(...args, ...nextArgs);
};
}
官方解法 2
如果原始函式有使用到 this
,解法 1 使用箭頭函式會導致 this
值的丟失。用 apply
與 bind
來綁定 this
的值。
function curry(fn: Function): Function {
return function curried(...args: any[]): any {
if (args.length >= fn.length) {
return fn.apply(this, args);
}
// (...nextArgs) => curried(...args, ...nextArgs)
return curried.bind(this, ...args);
};
}
Partial Application vs Currying
Partial Application 是指固定函式的多個參數,生成剩餘參數數量較少的新函式的過程。它允許我們透過預先指定一些參數來從現有的函式建立新函式。可以理解為 Currying 的一種特殊情況,其中參數的應用是「部分」的而不是「逐個」的。
// 假設我們有一個但有三個參數的函式
function sum(a, b, c) {
return a + b + c;
}
// 建立一個 Partial Application 函式,將第一個參數固定為 1
function partialSum(b, c) {
return sum(1, b, c);
}
// 當我們呼叫 partialSum 時,我們只需要提供剩下的兩個參數
console.log(partialSum(2, 3)); // 輸出 6
雖然 Partial Application 與 Currying 這兩種都可以產生更加模組化和可重複使用,但他們的使用情境和實作方式是不同的。Currying 更加著重於建立一連串的函式,而 Partial Application 則是著眼於固定參數以創造更專注的函式。
另外要注意的是 Currying 的實現方式有很多種,它們的行為可能會有顯著的差異。另外一個常見的變化情境是 Currying 函式不限制預先定義的參數數量,而是在使用者未傳遞任何參數時才呼叫函式:
function curry(fn: Function): Function {
return function curried(...args: any[]): any {
// 未傳遞任何參數時才呼叫 fn
if (args.length === 0) {
return fn(...args);
}
return (...nextArgs: any[]): any => {
// 未傳遞任何參數時才呼叫 fn
if (nextArgs.length === 0) {
return fn(...args);
}
return curried(...args, ...nextArgs);
};
};
}
第 11 天:Sleep
題目說明
在 millis
毫秒後返回異步函式完成狀態的值。
解題方法
等幾秒返回想到用 setTimeout
,異步函式通常會使用 Promise(從題目的程式碼也可以看到 sleep
函式類型是 Promise)。
解題程式碼
async function sleep(millis: number): Promise<void> {
return new Promise((resolve) => setTimeout(resolve, millis));
}
官方解題說明
https://leetcode.com/problems/sleep/editorial/
尚未詳讀完畢,但看評論很多說把 Event Loop 解釋得非常清楚,必看!
官方說明涵蓋概念:
setTimeout
與 Event LoopJavaScript 的 Event Loop
非同步的 Callback 函式
Concurrency 和 Event Loop
Async/await
.finally()
異步函式返回 Promise
第 12 天:Promise Time Limit
題目說明
當傳入的異步函式 fn
執行時間超過指定的毫秒數 t
時,返回拒絕狀態、花費的毫秒數與 "Time Limit Exceeded"
,注意其類型為字串而非 Error
;若沒有超過則返回完成狀態與 fn
執行結果與花費的毫秒數。
解題方法
計算函式花費的毫秒數,第一時間想到是在函式執行開始跟結束加上 performance.now()
,計算他們之間的差值。
解題程式碼
發現自己對 Promise 還是不熟悉,拼拼湊湊寫出一個版本,但 Case 1 的測試沒有過,請勿參考(笑)。主要是卡在計時的部分,印象中 performance.now()
沒有很準確,但一時之間沒想到怎麼計時比較好。
function timeLimit(fn: Fn, t: number): Fn {
return async function (...args) {
return new Promise(async (resolve, reject) => {
try {
const startTime = performance.now();
const result = await fn(...args);
const endTime = performance.now();
const deltaTime = endTime - startTime;
if (deltaTime <= t) {
resolve(result);
} else {
throw "Time Limit Exceeded";
}
} catch (error) {
reject(error);
}
});
};
}
官方解題說明
https://leetcode.com/problems/promise-time-limit/editorial/
時間限制的使用情境範例
在指定時間內不停執行同一段程式碼
當請求超過指定時間,則放棄請求並顯示錯誤訊息給使用者
官方解法 1
原來用 setTimeout
可以強制中斷 Promise 在超過時間內回傳失敗狀態!修改本來寫的第一版測試就過了!(註:後面發現這是官方解法 4 哈哈哈)
function timeLimit(fn: Fn, t: number): Fn {
return async function (...args) {
return new Promise(async (resolve, reject) => {
setTimeout(() => {
reject("Time Limit Exceeded");
}, t);
try {
const result = await fn(...args);
resolve(result);
} catch (error) {
reject(error);
}
});
};
}
不過用 try...catch
讓程式碼看起來有點複雜,直接用 .resolve().catch()
似乎更容易閱讀:
function timeLimit(fn: Fn, t: number): Fn {
return async function (...args) {
return new Promise((resolve, reject) => {
setTimeout(() => {
reject("Time Limit Exceeded");
}, t);
fn(...args).then(resolve).catch(reject); // 👈
});
};
}
官方解法 2
解法 1 會有個問題,當異步函式比限制的時間提早完成,setTimeout
仍會執行,而這是不必要的,所以當 Promise 完成時,可以用 clearTimeout
來取消執行。
function timeLimit(fn: Fn, t: number): Fn {
return async function (...args) {
return new Promise((resolve, reject) => {
const timeout = setTimeout(() => { // 👈
reject("Time Limit Exceeded");
}, t);
fn(...args)
.then(resolve)
.catch(reject)
.finally(() => clearTimeout(timeout)); // 👈
});
};
}
官方解法 3
把 setTimeout
也包成 Promise 函式用 Promise.race()
讓兩個 Promise 比賽,誰先結束(不論完成或失敗)就返回誰的值。
function timeLimit(fn: Fn, t: number): Fn {
return async function (...args) {
const timeLimitPromise = new Promise((_, reject) => {
setTimeout(() => {
reject("Time Limit Exceeded");
}, t);
});
const fnPromise = fn(...args);
return Promise.race([timeLimitPromise, fnPromise]);
};
}
第 13 天:Promise Pool
題目說明
無論傳入的異步函式陣列 functions
有多少個,同時進行的異步函式最多只能為 n
。當執行中的任何異步函式完成時,若有未執行的函式則立即執行,確保執行中的函式數量保持在 n
以下,直到陣列中所有函式都已執行完畢,然後返回完成狀態。
可以假定所有傳入的異步函式都不會有拒絕狀態。
解題方法
需要區分哪些函式已經被執行尚未執行:初始執行函式時,確保執行中的函式數量不能超過 n
,當有函式返回成功狀態時,要檢查是否還有未執行的函式。
解題程式碼
試了好幾個方式,兜不出個答案,決定閱讀官方解題。
官方解題說明
https://leetcode.com/problems/promise-pool/editorial/
想像如果用 Promise.all()
來處理一次下載超多檔案時可能會遇到的問題:
環境有可能會限制請求處理的數量,導致請求被取消
資料庫可能會因為過大的負載,無法回應請求的檔案
網路流量過多可能會導致優先級更高的請求被延遲
應用程式可能會在嘗試一次處理所有數據時沒有回應
最佳的方式是限制可同時併發請求的數量,並使用 Promise Pool 來達成。
const files = ["data.json", "data2.json", "data3.json"];
// 這邊會有兩個箭頭函式是因為要建立函式,但不想立刻執行它
const functions = files.map(filename => () => download(filename));
// 可以轉成不用箭頭函式的版本理解
// const functions = files.map(function(filename) {
// return function() {
// return download(filename);
// };
// });
const POOL_LIMIT = 2;
await promisePool(functions, POOL_LIMIT);
官方解法 1
function promisePool(functions: F[], n: number): Promise<any> {
return new Promise((resolve) => {
// 紀錄目前執行中的 Promise 數量
let inProgressCount = 0;
// 紀錄當前要執行的函式索引
let functionIndex = 0;
function helper() {
// 如果 functionIndex 大於或等於 functions 陣列的長度,表示所有的 Promise 已經被執行完畢。
if (functionIndex >= functions.length) {
// 此時檢查 inProgressCount 是否為 0,如果是,則調用 resolve 並傳遞 0 作為解析的值,表示所有 Promise 均已成功完成
if (inProgressCount === 0) resolve(0);
return;
}
// 檢查 inProgressCount 是否小於 n,且 functionIndex 是否小於 functions 陣列的長度時持續執行
while (inProgressCount < n && functionIndex < functions.length) {
// 增加 inProgressCount 的數量,表示有一個新的 Promise 開始執行
inProgressCount++;
// 使用 functionIndex 索引從 functions 陣列中獲取下一個要執行的 Promise 函式
const promise = functions[functionIndex]();
// 將 functionIndex 增加 1,以便下一輪遞迴時執行下一個 Promise 函式
functionIndex++;
// 執行該 Promise 函式,並獲得一個 Promise 物件
// 使用 promise.then() 註冊一個回調函式,當 Promise 完成時執行。
promise.then(() => {
// 減少 inProgressCount 的數量,表示有一個 Promise 完成了執行
inProgressCount--;
// 遞迴調用 helper 函式,以檢查是否可以執行更多的 Promise
helper();
});
}
}
helper();
});
}
官方解法 2
async function promisePool(functions: F[], n: number): Promise<any> {
let copiedFunctions = [...functions];
async function evaluateNext() {
// 檢查 copiedFunctions 陣列的長度是否為 0
// 如果是 0 表示所有的 Promise 函式都已經執行完畢,直接返回
if (copiedFunctions.length === 0) return;
// 使用 copiedFunctions.shift() 從 copiedFunctions 陣列中取出並移除陣列的第一個函式,並將其存儲在 fn 變數中
const fn = copiedFunctions.shift();
// 使用 await fn() 執行 fn,等待該 Promise 函式執行完成
await fn();
// 使用 await evaluateNext() 遞迴調用 evaluateNext 函式,來評估下一個要執行的 Promise 函式
await evaluateNext();
}
// 使用 Array(n).fill(0) 創建了一個長度為 n 的陣列,並將每個元素初始化為 0
// 然後,使用 map 方法將 evaluateNext 函式應用於每個元素,這將返回一個包含 n 個 Promise 的陣列 nPromises
const nPromises = Array(n).fill(0).map(evaluateNext);
// 使用 await Promise.all(nPromises) 等待所有的 Promise 在 nPromises 陣列中完成
await Promise.all(nPromises);
}
官方解法 3
type F = () => Promise<any>;
async function promisePool(functions: F[], n: number): Promise<any> {
const evaluateNext = () => functions[n++]?.().then(evaluateNext);
return Promise.all(functions.slice(0, n).map(f => f().then(evaluateNext)));
};
第 14 天:Cache With Time Limit
題目說明
建立一個可以設定和取得鍵值對的類別,然而每個鍵都有一個與之關聯的有效期限。
set(key, value, duration)
:接受一個整數鍵、一個整數值和一個以毫秒為單位的期限。一旦期限過去,該鍵將無法訪問。如果相同未過期的鍵已經存在,該方法應該返回true
;否則返回false
。如果鍵已經存在,則值和期限都應該被覆蓋。get(key)
:如果存在未過期的鍵,應該返回相關聯的值。否則返回 -1。count()
:返回未過期鍵的計數。
解題方法
第一直覺是用 Map 來儲存鍵值對,可以用 Map.has(key)
設定鍵值對、Map.has(key)
來檢查鍵是否存在以及用 Map.get(key)
鍵來取對應的值。
有效期限可以在 set(key, value, duration)
時將當下時間戳加上 duration
儲存,檢查是否過期則跟當下時間戳相比來判斷。
在寫的過程想到若是 value
可以設為 -1
的話,會導致不能直接將 get(key)
回傳 -1
當作是鍵值對失效的判別(鍵不存在或鍵值對已經過期),但 Constraints 有寫明 key
跟 value
都會是整數,所以就沒有問題。
解題程式碼
class TimeLimitedCache {
cacheMap: Map<number, { value: number; expireTime: number }>;
constructor() {
this.cacheMap = new Map();
}
set(key: number, value: number, duration: number): boolean {
const isCacheValid = this.get(key) !== -1;
this.cacheMap.set(key, { value, expireTime: Date.now() + duration });
return isCacheValid;
}
get(key: number): number {
const cache = this.cacheMap.get(key);
if (cache && cache.expireTime >= Date.now()) {
return cache.value;
}
return -1;
}
count(): number {
return Array.from(this.cacheMap.keys()).reduce(
(acc, key) => (this.get(key) === -1 ? acc : acc + 1),
0
);
}
}
官方解題說明
https://leetcode.com/problems/cache-with-time-limit/editorial/
我的解法跟官方解法 3 概念相同,但會有幾個問題:
已經過期的值仍會被儲放在記憶體內,可被視為記憶體洩漏(Memory Leak)
計算未過期的鍵是
O(N)
的操作