TypeScript 練習題：30 天 LeetCode 挑戰（第 8 天至第 14 天）

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 Loop
JavaScript 的 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) 的操作

安娜的自我探索與成長筆記

安娜的自我探索與成長筆記

TypeScript 練習題：30 天 LeetCode 挑戰（第 8 天至第 14 天）

Table of contents

第 8 天：Allow One Function Call

第 9 天：Memoize

第 10 天：Curry

第 11 天：Sleep

第 12 天：Promise Time Limit

第 13 天：Promise Pool

第 14 天：Cache With Time Limit