TypeScript 練習題:30 天 LeetCode 挑戰(第 8 天至第 14 天)

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 有提到,傳入的函式會是 sumfibfactorial

解題方法

跟前一題 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 函式使用情境範例:

  1. 可重複使用的函式

     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
    
  2. 事件處理:可用於建立有特定配置的事件處理函式,同時保持原本通用的事件處理函式。

     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);
    
  3. 自定義呼叫 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" });
    
  4. 組合高階函式與函式組合

     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 值的丟失。用 applybind 來綁定 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() 來處理一次下載超多檔案時可能會遇到的問題:

  1. 環境有可能會限制請求處理的數量,導致請求被取消

  2. 資料庫可能會因為過大的負載,無法回應請求的檔案

  3. 網路流量過多可能會導致優先級更高的請求被延遲

  4. 應用程式可能會在嘗試一次處理所有數據時沒有回應

最佳的方式是限制可同時併發請求的數量,並使用 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 有寫明 keyvalue 都會是整數,所以就沒有問題。

解題程式碼

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