TypeScript 練習題:30 天 LeetCode 挑戰(第 15 天至第 21 天)

TypeScript 練習題:30 天 LeetCode 挑戰(第 15 天至第 21 天)

LeetCode 挑戰題目總覽:30 Days of LC JavaScript Challenge(從 5 月 5 日起,台灣時間每天早上八點釋出新題目)

第 15 天:Debounce

題目說明

實作一個 Debounce 函式會將函式 fn 執行延遲 t 毫秒,若在延遲期間 fn 再次被呼叫,原本的執行會被取消,並再延遲 t 毫秒後執行 fn

解題方法

延遲執行會想到使用 setTimeout(),要取消呼叫的話會需要原本設定的 setTimeout

解題程式碼

function debounce(fn: F, t: number): F {
  let timer = null;
  return function (...args) {
    if (timer) clearTimeout(timer);
    timer = setTimeout(() => {
      timer = null;
      fn(...args);
    }, t);
  };
}

官方解題說明

https://leetcode.com/problems/debounce/editorial/

最常見的 Debounce 經典用途是當使用者在輸入搜尋框。如果每次輸入一個字元就顯示搜尋新的結果,重新渲染搜尋結果列表可能比輸入另一個字元的時間更長。因此理想情況是只在使用者完成輸入時,才重新渲染搜尋結果列表給使用者。

另一個例子則是當我們在縮放圖表時,縮小圖表需要下載更多的數據。但是如果在使用者縮小時以每秒 60 幀的速度來下載數據,則效率非常低,應該只在使用者完成縮小這個動作時下載數據。

看說明 clearTimeout(undefined) 或是已完成的 setTimeout 是不會執行任何操作的,所以我本來的寫法是可以省略對 timer 的判斷。

function debounce(fn: F, t: number): F {
  let timer;
  return function (...args) {
    clearTimeout(timer);
    timer = setTimeout(() => {
      fn(...args);
    }, t);
  };
}

第 16 天:Throttle

題目說明

實作一個 Throttle 函式會在最初被立即呼叫一次,在接下來的 t 毫秒內無法執行,但應該再延遲結束後使用最新的函式參數呼叫 fn

解題方法

延遲函式執行一樣想到 setTimeout(),函式呼叫需要先判斷是否在延遲期間,若在延遲期間需要儲存最後一次所帶的參數並在延遲結束時用來呼叫函式。

解題程式碼

測試案例 3 沒有通過,試好一陣子沒有解法,決定看官方解法是哪裡想錯了。

type F = (...args: any[]) => void;

function throttle(fn: F, t: number): F {
  let isThrottled = false;
  let lastArgs;
  return function (...args) {
    if (isThrottled) {
      lastArgs = args;
      return;
    }
    fn(...args);
    isThrottled = true;
    setTimeout(() => {
      isThrottled = false;
      if (lastArgs) {
        fn(...lastArgs);
        lastArgs = "";
      }
    }, t);
  };
}

官方解題說明

https://leetcode.com/problems/throttle/editorial/

官方解法 1

將 Throttle 理解成會有兩種狀態:循環與等待。在等待期間不會有任何函式被執行,當 Throttle 被呼叫會立即執行回調。一但執行函式後就會進入循環的狀態。這時應該使用最後一個接收的參數每 t 毫秒執行一次提供的回調。

type F = (...args: any[]) => void

function throttle(fn: F, t: number): F {
  let timeoutInProgress = null;
  let argsToProcess = null;

  const timeoutFunction = () => {
    if (argsToProcess === null) {
      timeoutInProgress = null; // enter the waiting phase
    } else {
      fn(...argsToProcess);
      argsToProcess = null;
      timeoutInProgress = setTimeout(timeoutFunction, t);
    }
  };

  return function throttled(...args) {
    if (timeoutInProgress) {
      argsToProcess = args;
    } else {
      fn(...args); // enter the looping phase
      timeoutInProgress = setTimeout(timeoutFunction, t);
    }
  }
};

第 17 天:JSON Deep Equal

題目說明

判斷兩個物件是否深度相等。若要兩個物件深度相等,它們必須包含相同的鍵值,而且相對應的值也必須深度相等。若兩個物件通過 === 的等式檢查也相等,則它們也被視為深度相等。

可以假設這兩個物件都是 JSON.parse 的輸出結果,換句話說表示它們都是有效的 JSON 物件。要在不使用 lodash 的 .isEqual() 函式的情況下解決這個問題。

解題方法

物件有深度表示會不只有一層,直覺想到可能會用遞迴來檢查。除此之外腦袋一片空白(好廢)只好來看官方解題的思路是什麼。

官方解題說明

https://leetcode.com/problems/json-deep-equal/editorial/

嚴格相等(===)、一般相等(==)與 Object.is() 差異

  • 不同型別的值

    • 嚴格相等:即不相等

    • 一般相等:先將比較值轉換成同型別後比較

    • Object.is():即不相等

  • 基本資料型別

    • 嚴格相等:值相等即相等

    • 一般相等:先將比較值轉換成同型別後比較

    • Object.is():使用 SameValue 的相等運算法,-0+0 會不相等,NaNNaN 則為相等。

  • 物件與陣列型別

    • 嚴格相等:引用同一物件才被視為相等(同記憶體位置)

    • 一般相等:引用同一物件才被視為相等(同記憶體位置)

    • Object.is():引用同一物件才被視為相等(同記憶體位置)

為什麼題目要強調物件是 JSON.parse 的輸出結果?

因為這代表我們不需要處理一些特殊情況:例如值為 undefined 或是不可列舉的屬性以及循環參照。

使用情境

  • 緩存和記憶(Caching and Memoization)

  • UI 框架中的狀態比較(State Comparison in UI Frameworks)

  • 測試和斷言(Testing and assertions)

  • 數據同步(Data Synchronization)

  • JSON 比較(JSON Diffing)

官方解法 1:比較遞迴 Comparative Recursion

解題思路是先處理可以用簡單的方式來判斷是否相等的情況,像漏斗篩選掉簡單的情況後再分別處理是陣列或是物件。

時間複雜度是 O(N),空間複雜度為 O(D)N 是遞迴比較的值總數,D 為遞迴的最大深度)。

function areDeeplyEqual(o1: any, o2: any): boolean {
    // 檢查兩者嚴格相等 === 為 true,直接返回 true
    if (o1 === o2) return true;
    // 檢查兩者任一是否為 null,如果其中一個是 null 另一個不是,則不相等,返回 false
    // 獨立判斷是因為 null 只會與 undefined 相等,與其他值都不相等
    if (o1 === null || o2 === null) return false;

    // 將兩者使用 String 函式做轉換後,若形式不相等不可能深度相等,返回 false
    // 則表示可能是不同的基本型別或者是像 Date 和 RegExp 這樣的特殊物件
    // 註:並不代表兩者轉換結果相同就是型別相同,只是判斷類型不相同一定不深度相等
    if (String(o1) !== String(o2)) return false;

    // 若型別是基本型別(非物件和非函式),則檢查兩者不嚴格相等,返回 false
    if (typeof o1 !== 'object') {
        return o1 === o2;
    }

    // 若其中一個是陣列
    if (Array.isArray(o1)) {
        // 若兩者長度不相等,不可能深度相等,返回 false
        if (o1.length !== o2.length) return false;
        // 遍歷陣列檢查每個元素是否都深度相等,若有任一不相等返回 false
        for (let i = 0; i < o1.length; i++) {
            if (!areDeeplyEqual(o1[i], o2[i])) return false;
        }
        // 所有元素皆深度相等,返回 true
        return true;
    }
    // 類型是物件的情況
    // 若兩者鍵的數量不相等,不可能深度相等,返回 false
    if (Object.keys(o1).length !== Object.keys(o2).length) return false;

    // 遍歷陣列檢查每個鍵值是否都深度相等,若有任一不相等返回 false
    for (const key in o1) {
        if (!areDeeplyEqual(o1[key], o2[key])) return false;
    }

    return true;
}

官方解法 2:迭代解決方案

若是遍歷逐個檢查輸入的物件來比較兩者是否深度相等,無法處理鍵順序不同的情況。但我們可以透過明確追蹤和處理巢狀物件的堆疊(Stack),逐步處理,這樣就不再需要遞迴函式呼叫。

時間複雜度是 O(N),空間複雜度為 O(D)N 是輸入物件中的元素總數,D 為巢狀物件的最大深度)。

任何可以用遞迴解決的事情也可以用堆疊處理

因為遞迴依賴互叫堆疊(Call Stack)來管理函式呼叫並處理遞迴過程。另一方面,堆疊數據結構可以模仿呼叫堆疊的行為,使我們能夠迭代地實作相同的邏輯。兩種方法都遵循相同的深度優先遍歷模式(depth-first traversal pattern)。

function areDeeplyEqual(o1: any, o2: any): boolean {
  // 建立一個儲存一對要比較的物件堆疊
  const objs: [any, any][] = [[o1, o2]];

  // 循環檢查直到堆疊內的物件對都已經比較過
  while (objs.length) {
    // 從堆疊取出最後一對的物件
    [o1, o2] = objs.pop();

    // 若是兩個物件嚴格相等,繼續取堆疊的下一對物件
    if (o1 === o2) continue;

    // 若是其中一個物件不是物件型別,則不是深度相等,返回 false
    if (typeof o1 !== "object" || typeof o2 !== "object") return false;    
    // 若是其中一個是陣列,而另一個不是陣列,也不是深度相等,返回 false
    if (Array.isArray(o1) !== Array.isArray(o2)) return false;

    // 取得兩個物件的鍵值
    // 若是 Object.keys 傳入陣列會回傳索引值
    const keys1 = Object.keys(o1);
    const keys2 = Object.keys(o2);

    // 若是兩者的鍵值長度不相同,則不深度相等,返回 false
    if (keys1.length !== keys2.length) return false;

    // 遍歷第一個物件的鍵
    for (const key of keys1) {
      // 若是第一個物件有的鍵,第二個物件沒有,則不深度相等,返回 false
      if (!(key in o2)) return false;

      // 把鍵對應的值放到堆疊內,後續做比較
      //(把巢狀的下一層放到堆疊內處理,類似遞迴)
      objs.push([o1[key], o2[key]]);
    }
  }

  // 所有的物件對都已經互相比較且都深度相同,返回 true
  return true;
}

第 18 天:Convert Object to JSON String

題目說明

將 Object 轉成字串格式,不會有多餘的空格,可以假設物件只有字串、數字、陣列、物件、布林值與 null。鍵的順序要與 Object.keys() 返回的順序相同。不能用 JSON.stringfy() 來解題。

解題方法

Object.keys() 除了數字鍵以外,排列的順序則是依照這些屬性被加入到物件的順序。會優先以升序排列數字鍵,然後才是字串和符號鍵。由於 ECMA 規範並沒有明確規定其輸出順序,所以在不同瀏覽器的輸出結果可能不相同。

巢狀結構一樣會想到使用遞迴來處理,但感覺不能用堆疊處理。

發現自己面對遞迴的題目腦袋常常容易打結,ChatGPT 說可以先確認問題的基本情況,即無須再進行拆解或處理的情況,套用到這個題目應該就是遇到基本型別的時候。

解題程式碼

function jsonStringify(object: any): string {
  // array
  if (Array.isArray(object)) {
    const keyString = object.map((el) => jsonStringify(el)).join();
    return `[${keyString}]`;
  }

  // object
  if (typeof object === "object" && object !== null) {
    const keyString = Object.entries(object)
      .map(([key, value]) => `"${key}":${jsonStringify(value)}`)
      .join(",");
    return `{${keyString}}`;
  }

  // string
  if (typeof object === "string") {
    return `"${object}"`;
  }
  // integer, boolean, null
  return `${object}`;
}

官方解題說明

https://leetcode.com/problems/convert-object-to-json-string/editorial/

使用情境

  • API 數據序列化(API Data Serialization):在建立與 API 通訊的網頁應用程式時,物件通常需要在發送為 HTTP 請求中的資料之前轉換為 JSON 字串。這可以讓資料正確序列化並以 API 理解的格式傳輸。

      // Creating an object to be sent as data in an HTTP request
      const data = { name: 'Racoon', age: 9, email: 'racoon@example.com' };
    
      // Converting the object to a JSON string
      const jsonData = JSON.stringify(data);
      // jsonData: '{"name":"Racoon","age":9,"email":"racoon@example.com"}'
    
      // Sending an HTTP POST request with the JSON data as the request body
      fetch('https://api.example.com/users', {
        method: 'POST',
        headers: {
          'Content-Type': 'application/json'
        },
        body: jsonData
      })
        .then(response => response.json())
        .then(responseData => {
          // Handling the response data received from the server
          console.log(responseData);
        })
        .catch(error => {
          // Handling any errors that occurred during the request
          console.error(error);
        });
    
  • 本機儲存(Local Storag):在網頁開發中,本機儲存(localStorage)或會話儲存(sessionStorage)API 常用於在瀏覽器內本機儲存資料。由於這些 API 只接受字串值,因此必須將物件轉換為 JSON 字串以儲存複雜的資料結構,並稍後檢索它們。

      const user = { name: 'RocketRacoon', id: 8913, isAdmin: false };
      const jsonUser = JSON.stringify(user);
      localStorage.setItem('user', jsonUser);
    
      // Retrieve the user from local storage and parse it back to an object
      const storedUser = localStorage.getItem('user');
      const parsedUser = JSON.parse(storedUser);
      console.log(parsedUser.name); // Output: "RocketRacoon"
    
  • 記錄(Logging):當記錄資料或產生記錄檔時,將物件轉換為 JSON 字串可以提供結構化且可讀性良好的格式來儲存記錄。它可以輕鬆分析、搜尋和處理記錄資料。

      const logData = { timestamp: new Date(), level: 'info', message: 'User logged in' };
      const jsonLogData = JSON.stringify(logData);
    
      // Store the jsonLogData in log files or send it to a logging service
      // ...
    
  • 配置檔案(Configuration Files):JSON 通常被用於各種應用程式中的配置檔案。將物件轉換為 JSON 字串可以輕鬆存儲和檢索配置設定,從而使應用程式行為具有自定義和靈活性。

      const config = { apiUrl: 'https://api.example.com', maxRetries: 3, timeout: 5000 };
      const jsonConfig = JSON.stringify(config);
    
      // Save the jsonConfig to a configuration file
      // ...
    

官方解法 1:使用類似 JSON 的字串連接

跟我想到的解法很像,只是我的可以再精簡一點,例如把 null 提到最前面,因為 typeof of null 會是 object(歷史錯誤),這樣後面也不需要加判斷 object !== null

function jsonStringify(object: any): string {
  if (object === null) {
    return 'null';
  }

  if (Array.isArray(object)) {
    const elements = object.map((element: any) => jsonStringify(element));
    return `[${elements.join(',')}]`;
  }

  if (typeof object === 'object') {
    const keys = Object.keys(object);
    const keyValuePairs = keys.map((key: string) => `"${key}":${jsonStringify(object[key])}`);
    return `{${keyValuePairs.join(',')}}`;
  }

  if (typeof object === 'string') {
    return `"${object}"`;
  }

  return String(object);
}

官方解法 2:使用 switch 條件

思路跟解法 1 很像,只是變成以 typeof object 作為第一層的條件判斷後再根據不同型別做判斷。

function jsonStringify(object) {
  switch (typeof object) {
    case "object":
      // array
      if (Array.isArray(object)) {
        const elements = object.map((element) => jsonStringify(element));
        return `[${elements.join(",")}]`;
      // object (not falsy value like null)
      } else if (object) {
        const keys = Object.keys(object);
        const keyValuePairs = keys.map(
          (key) => `"${key}":${jsonStringify(object[key])}`
        );
        return `{${keyValuePairs.join(",")}}`;
      } else {
        return "null";
      }
    case "boolean":
    case "number":
      return `${object}`;
    case "string":
      return `"${object}"`;
    default:
      return "";
  }
}

第 19 天:Array of Objects to Matrix

題目說明

實作一個函式將陣列 arr 轉換為矩陣 marr 是一個由物件或陣列所組成的陣列。每個陣列項目可以深度嵌套子陣列和子物件,也可以包含數字、字串、布林值和 null 值。

第一行 m 應該是欄位名稱。如果沒有嵌套,欄位名稱就是物件中的唯一鍵。如果有嵌套,欄位名稱就是物件中各自路徑,並以 . 分隔。 其餘的行對應於 arr 中的物件。矩陣中的每個值對應於物件中的一個值。如果給定的物件沒有給定欄位的值,該儲存格應該包含一個空字串 ""。 矩陣中的欄位應該按字母順序進行排列。

解題方法

雖然有嘗試拆解問題,但還是沒有寫到可以通過全部測試案例的程式碼(卡在 Case 3),紀錄自己的步驟之後對照官方解題看看是哪裡卡住了。

  1. 取得所有唯一的欄位名:物件包物件卡關

  2. 將唯一的欄位名按照字母排序:第一步驟之後用 sort()

  3. 把欄位值填到矩陣內

解題程式碼

思緒蠻亂的,效能肯定不好用超多 forEach 寫到最後也不知道自己在寫什麼(笑)。

function jsonToMatrix(arr: any[]): (string | number | boolean | null)[][] {
  const getColumnKeys = (array: any[]) => {
    const keys: string[] = [];
    array.forEach((item) => {
      if (Array.isArray(item)) {
        item.forEach((el, index) => {
          Object.keys(el).forEach((key) => {
            keys.push(`${index}.${key}`);
          });
        });
      } else {
        Object.keys(item).forEach((key) => {
          // 如何處理 nested object?
          if (!keys.includes(key)) {
            keys.push(key);
          }
        });
      }
    });
    return keys;
  };
  const columnKeys = getColumnKeys(arr).sort();

  const matrixValues = arr.map((item) =>
    columnKeys.map((columnKey) => {
      const keyPath = columnKey.split(".");
      let object = item;
      for (const key of keyPath) {
        object = object[key];
        if (object === undefined) {
          break;
        }
      }
      return object === undefined ? "" : object;
    })
  );

  return [columnKeys, ...matrixValues];
}

官方解題說明

https://leetcode.com/problems/array-of-objects-to-matrix/editorial/

看完官方解法發現這一題真的蠻複雜的,大致拆解問題的方向是對的,應該要多思考如何將函式再切分的更小單位,也許會讓思緒再更清楚一些,不用一次思考很多可能性,例如取值可以從 matrixValues 獨立出來,最後再組合成矩陣。

使用情境

  • 數據分析(Data Analysis)

  • 數據庫操作(Database Operations)

  • 數據導出(Data Export)

  • 視覺化(Visualizations)

官方解法 1:遞迴

整個思路跟我拆解的差不多,但總是搞不清楚什麼時候該遞迴。

function jsonToMatrix(arr: any[]): (string | number | boolean | null)[][] {
  const isObject = (x: any): x is object => (x !== null && typeof x === 'object');

  // 該函式遞歸遍歷嵌套結構並返回找到的所有唯一鍵的數組
  const getKeys = (arg: any): string[] => {
    if (!isObject(arg)) return [''];
    return Object.keys(arg).reduce((acc: string[], curr: string) => {
      return (acc.push(...getKeys(arg[curr]).map((x: string) => x ? `${curr}.${x}` : curr)), acc);
    }, []);
  };

  const keys: string[] = [...arr.reduce((acc: Set<string>, curr: any) => {
    getKeys(curr).forEach((k: string) => acc.add(k));
    return acc;
  }, new Set<string>())].sort();

  const getValue = (obj: any, path: string): string | number | boolean | null => {
    const paths: string[] = path.split('.');
    let i = 0;
    let value: any = obj;
    while (i < paths.length) {
      if (!isObject(value)) break;
      value = value[paths[i++]];
    }
    if (i < paths.length || isObject(value) || value === undefined) return '';
    return value;
  };

  const matrix: (string | number | boolean | null)[][] = [keys];
  arr.forEach((obj: any) => {
    matrix.push(keys.map((key: string) => getValue(obj, key)));
  });

  return matrix;
}

官方解法 2:使用 Map 的選擇性迭代方法

function jsonToMatrix(arr: any[]): (string | number | boolean | null)[][] {
  const isObject = (elem: any): boolean => elem instanceof Object;

  const getSub = (obj: any): Map<string, any> => {
    const map = new Map<string, any>();

    const setMap = (elem: any, preKey: string) => {
      if (!isObject(elem)) {
        map.set(preKey, elem);
        return;
      }

      const subMap = getSub(elem);
      for (const entry of subMap.entries()) {
        const symbol = `${preKey}.${entry[0]}`;
        map.set(symbol, entry[1]);
      }
    };

    if (Array.isArray(obj)) {
      for (let i = 0; i < obj.length; i++) {
        setMap(obj[i], `${i}`);
      }
    } else {
      for (const key of Object.keys(obj)) {
        setMap(obj[key], key);
      }
    }

    return map;
  };

  const map = getSub(arr);
  const set = new Set<string>();

  for (const key of map.keys()) {
    const i = key.indexOf('.');
    const symbol = key.slice(i + 1);
    set.add(symbol);
  }

  const keys = [...set].sort((a, b) => a < b ? -1 : 1);
  const len = arr.length;
  const matrix: (string | number | boolean | null)[][] = [keys];

  for (let i = 1; i <= len; i++) {
    if (keys.length === 0) {
      matrix[i] = [];
      continue;
    }

    for (let j = 0; j < keys.length; j++) {
      const key = `${i - 1}.${keys[j]}`;
      if (!matrix[i]) {
        matrix[i] = [];
      }
      matrix[i][j] = map.has(key) ? map.get(key) : "";
    }
  }

  return matrix;
}

第 20 天:Differences Between Two Objects

題目說明

實作一個函式,接受兩個深層嵌套的物件或陣列 obj1obj2,並回傳一個新的物件,代表它們之間的差異。回傳的物件只包含值從 obj1obj2 有變化的鍵,並且用陣列來表示變化前後的值 [obj1 value, obj2 value] 。只存在其中一個物件但不存在另一個物件中的鍵也不應該包含在回傳的物件中。

解題方法

看完題目感覺是第 17 天:JSON Deep Equal 的進階題,只是當不相等時需要將有差異鍵與值記錄起來。

解題程式碼

最後寫的版本 Case 5 沒有通過。

function objDiff(obj1: any, obj2: any): any {
  const difference = {};
  Object.keys(obj1).forEach((key) => {
    if (typeof obj1[key] === "object" && typeof obj2[key] === "object") {
      if (obj1[key].length === 0 || obj2[key].length === 0) {
        return;
      }
      if (!Array.isArray(obj1[key]) && !Array.isArray(obj2[key])) {
        difference[key] = objDiff(obj1[key], obj2[key]);
        return;
      }
      if (Array.isArray(obj1[key]) && Array.isArray(obj2[key])) {
        difference[key] = objDiff(obj1[key], obj2[key]);
        return;
      }
      difference[key] = [obj1[key], obj2[key]];
      return;
    }
    if (obj2[key] !== obj1[key] && obj2[key] !== undefined) {
      difference[key] = [obj1[key], obj2[key]];
    }
  });

  return difference;
}

官方解題說明

https://leetcode.com/problems/differences-between-two-objects/editorial/

使用情境

  • 視覺化(Visualizations):直接顯示兩個 JSON 文件更改的內容,而非手動比對。例如 Redux DevTools 就是使用 JSON 差異工具作為核心功能的工具。

  • 有效儲存過去的檔案版本(Efficiently Storing Past Versions of a File):假設我們想在某些應用程式實作持續自動保存功能,該應用程式的核心是修改一個大型的 JavaScript 物件。最簡單的方法是在每次使用者執行動作時,將每個物件的副本存儲在文件中。然後,當使用者想要回復到較早版本時,他們只需選擇文件並載入它。然而,這樣做效率並不高,大量的數據只是從一個文件複製到下一個文件。另一個方案是使用更少的存儲空間,只儲存文件之間的差異。這將需要一些處理來創建所需的文件,通過應用更新,但將占用較少的存儲空間。

官方解法

官方解法也是用遞迴,發現自己在思考遞迴的基本情況的時候很容易想得太複雜。

  1. 如果 obj1 === obj2 表示兩者相等,回傳 {}。在這之後可以假定這兩個值互不嚴格相等 ===

  2. 如果任一值為 null,則返回 [obj1, obj2]。排除 typeof null"object" 的極端情況。

  3. 如果 typeof 任一值不是 "object",則返回 [obj1, obj2]

  4. 如果其中一個是陣列而另一個是物件,則返回 [obj1, obj2] 。用 Array.isArray(obj1) !== Array.isArray(obj2) 來判斷。

排除基本情況後,我們可以繼續假設我們有兩個可比較的物件或陣列。

下一步是遍歷兩個物件上存在的鍵。這最容易使用 for...in 迴圈來實現,並使用。if 語句來檢查該鍵是否也屬於另一個物件。需要注意的是,當對陣列應用 for...in 迴圈時,它會產生陣列的索引。

為了計算這些鍵的差異,我們可以使用遞迴呼叫來遞歸處理子物件。但是重要的是,我們只應在差異不是空物件 {} 時將這個差異附加到結果物件中。根據問題的要求,我們希望排除 {},因為這是不必要的資訊。需要注意的是,我們選擇在基本情況中將相同的基本型別表示為 {},因為這個表示方式與相同的物件/陣列的輸出匹配,使得它們可以通過單一條件進行過濾。

確認物件是否為空的一個簡單方法是檢查 Object.keys(obj).length === 0。這是因為當物件是空的時候,Object.keys(obj) 會返回一個空陣列,其長度為 0。

function objDiff(obj1: any, obj2: any): any {
    // 兩者嚴格相等
    if (obj1 === obj2) return {};
    // 任一值是 null (typeof 為 "object" 的極端情況)
    if (obj1 === null || obj2 === null) return [obj1, obj2];
    // 任一值不是 "object"
    if (typeof obj1 !== 'object' || typeof obj2 !== 'object') return [obj1, obj2];
    // 其中一個是陣列而另一個是物件
    if (Array.isArray(obj1) !== Array.isArray(obj2)) return [obj1, obj2];

    const returnObject = {};
    // 遍歷檢查 obj1 鍵
    for (const key in obj1) {
        // 若鍵存在於 obj2
        if (key in obj2) {
            // 遞迴比較兩者鍵值
            const subDiff = objDiff(obj1[key], obj2[key]);
            // 若比較回傳的結果物件不為空,表示兩者有差異
            if (Object.keys(subDiff).length > 0) {
                // 將比較結果作為值放到回傳的物件鍵
                returnObject[key] = subDiff;
            }
        }
    }
    return returnObject;
}

第 21 天:Chunk Array

題目說明

給定一個陣列 arr 和一個塊大小 size,返回一個被分塊的陣列。分塊後的陣列包含原始陣列 arr 的元素,但每個子陣列的長度為 size。如果 arr.length 不被 size 整除,最後一個子陣列的長度可能小於 size

您可以假設陣列是 JSON.parse 的輸出。換句話說,它是有效的 JSON。要在不使用 lodash 的 _.chunk 函式的情況下解決這個問題。

解題方法

直覺是用 Array.splice() 來切陣列。

解題程式碼

function chunk(arr: any[], size: number): any[][] {
    // 儲存分割後的陣列
    const chunkedArray: any[][] = [];
    // 複製一份原始陣列,以免 splice 改變原本的陣列
    let copiedArray = [...arr];

    while (copiedArray.length > 0) {
        // 使用 splice 方法將原陣列的前 size 個元素切割出來
        // 將其加入分割後的陣列
        chunkedArray.push(copiedArray.splice(0, size));
    }

    return chunkedArray;
};

官方解題說明

https://leetcode.com/problems/chunk-array/editorial/

使用情境

  • 分頁(Pagination):在網頁應用程式中實現分頁功能時,通常需要將大型項目清單拆分成小塊或頁面。這個分割操作可以將項目分成易於管理的部分,使數據的顯示和瀏覽更加容易。

      function paginateArray(array, pageSize, pageNumber) {
          // 計算當前頁面的起始索引
          const startIndex = (pageNumber - 1) * pageSize;
    
          // 根據每頁大小創建陣列分割塊
          const chunkedArray = array.slice(startIndex, startIndex + pageSize);
    
          return chunkedArray;
      }
    
      // 示例用法
      const data = [
          'Racoon 1', 'Racoon 2', 'Racoon 3', 'Racoon 4', 'Racoon 5',
          'Racoon 6', 'Racoon 7', 'Racoon 8', 'Racoon 9', 'Racoon 10'
      ];
    
      const pageSize = 3; // 每頁項目數
      const pageNumber = 2; // 當前頁碼
    
      const result = paginateArray(data, pageSize, pageNumber);
      console.log(result);
    
  • 平行處理(Parallel Processing):在並行處理或分散式系統中,資料通常被分割成塊並由多個處理器或節點同時處理。將資料分割可以有效地分配任務並對其進行並行執行,從而提高整體性能。

  • 圖像處理(Image Processing):在影像處理應用中,大型影像通常會分成較小的區塊或磚塊,以便以更細微的級別進行處理和分析。 每個磚塊可以獨立處理,允許並行化並有效利用計算資源。

  • 數據分析與聚合(Data Analysis and Aggregation):處理大型資料集時,最好將資料分割成較小的塊以進行分析和聚合。這種方法可以對其進行並行或分散式處理,從而加快資料處理速度並有效利用資源。

  • 文件上傳和傳輸(File Upload and Transfer):上傳或傳輸大型檔案時,資料通常會以較小的塊形式發送,以處理潛在的網路限制並確保可靠的傳送。接收端可以對每個塊獨立處理,並將它們重新組合以重建原始檔案。

官方解法 2:用 Array.slice()

function chunk(arr: any[], size: number): any[][] {
  const chunkedArray: any[][] = [];
  let index = 0;

  while (index < arr.length) {
    // slice 不會改變原本的陣列,會回傳包含起始到結束 index 的元素陣列
    chunkedArray.push(arr.slice(index, index + size));
    index += size;
  }

  return chunkedArray;
}

時間複雜度為 O(n)n 是輸入的長度或一個塊的大小;空間複雜度為 O(1)

官方解法 4:用 Array.reduce()

function chunk(arr: any[], size: number): any[][] {
  return arr.reduce((chunkedArray: any[][], element: any) => {
    const lastChunk = chunkedArray[chunkedArray.length - 1];
    if (!lastChunk || lastChunk.length === size) {
      chunkedArray.push([element]);
    } else {
      lastChunk.push(element);
    }
    return chunkedArray;
  }, []);
}

時間複雜度為 O(n)n 是輸入的長度或一個塊的大小;空間複雜度為 O(1)

官方解法 6:使用 Math.ceil()

Math.ceil() 函式會回傳大於等於所給數字的最小整數。

function chunk(arr: any[], size: number): any[][] {
  // 用 Array.from 建立一個長度等於所需分割塊數量的新陣列
  // 會分割成幾塊用輸入陣列的長度除以分割大小並使用 Math.ceil 進行四捨五入來計算
  return Array.from({ length: Math.ceil(arr.length / size) }, function(_: any, index: number) {
    // 從陣列提取每個分割塊的相對應的部分
    return arr.slice(index * size, index * size + size);
  });
}