[LeetCode] Interview Questions

49 - Group Anagrams @ leetcode solution
102 - Binary Tree Level Order Traversal - BFS @neetcode
150 - Evaluate Reverse Polish Notation：explanation

Array & Hashing

Range Sum Query - Immutable - LeetCode 303

解題邏輯

利用 Prefix Sum 的方法，只需要先算出這個 Array 從 0 到 end 累加到數值，假設取做 sumArray
要取得 L 到 R 的加總，只需要 sumArray[R] - sumArray[L - 1]
- 例外，如果 L = 0 則直接拿 sumArray[R]

Binary Search

Koko Eating Bananas - Leetcode 875

參考資料

題目描述

給定一組 array of numbers（piles）
需要在 h 次內消耗完所有數字
每次能消耗 k 個，但最多就是消耗完一個 pile，且消耗的速度（k）要約小越好

需要求 k 的值。

解題邏輯

題目有一個前提是 piles.length <= h，否則一定消耗不完
由於題目希望 k 越小越好，所以 k 最大就是等於 piles 裡面的最大值，超過這個數字也沒意義，也就是 k <= Max(piles)
這時候就可以列出所有可能 k，例如，[3, 6, 7, 11] 則可以列出 [1, ... 11]
最後，使用 Binary Search 找出符合的答案

參考程式碼

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, h) {
  let l = 1;
  let r = piles.reduce((acc, pile) => acc + pile);

  while (l <= r) {
    const m = Math.floor((l + r) / 2);
    const hours = piles.reduce((acc, pile) => acc + Math.ceil(pile / m), 0);

    // 1. 如果用的時間比規定的多，需要把一次消耗的量（k）加大
    if (hours > h) {
      l = m + 1;
    } else {
      // hours <= h
      r = m - 1;
    }
  }

  // 2. 之所以可以直接回傳 l 是因為我們要的是最小值
  return l;
};

Koko Eating Bananas

Trees

Binary Tree Level Order Traversal - LeetCode 102

參考資料

題目描述

透過 BFT（Breadth First Traversal）把所有元素以 two dimensional array 的方式呈現出來

需要以左到右的方式排列

解題邏輯

透過迴圈
- 把每一層的 node 都放到 queue 中
- 每次都會把 queue 的 node 清空，保存到該層所建立的 array 中
- 把下一層的 node 都放到 queue 中
- 重複這個邏輯...

範例程式碼

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  const result = [];
  const queue = [root];

  if (!root) {
    return result;
  }

  while (queue.length) {
    const level = [];
    // 因為 queue 會被改變，所以先把這個迴圈開始前的 length 記下來
    // 如此才知道怎麼每次把 queue 都清空
    const queueLength = queue.length;

    // 每次都把 queue 清空
    for (let i = 0; i < queueLength; i++) {
      const currentNode = queue.shift();
      level.push(currentNode.val);

      if (currentNode.left) {
        queue.push(currentNode.left);
      }

      if (currentNode.right) {
        queue.push(currentNode.right);
      }
    }

    result.push(level);
  }

  return result;
};

Invert Binary Tree - LeetCode 226

參考資料

題目描述

把所有 node 底下的 left 和 right 對調

解題邏輯

這題要想到用 recursive，把每一個 node 的 left 和 right 都進行交換

invert binary tree

參考程式碼

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
  if (!root) return null;

  const tempRoot = { ...root };
  root.left = invertTree(tempRoot.right);
  root.right = invertTree(tempRoot.left);

  return root;
};

Count Good Nodes in Binary Tree - LeetCode 1448

參考資料

題目描述

Good Node 指的是 Parent Node 中沒有比它值更大的
Root Node 是 Good Node
要計算整個 Tree 中，Parent Nodes 的數量

解題邏輯

使用 DFT（Depth First Traversal）或 BFT（Breadth First Traversal）都可以。

如果是使用 DFT 的話，可以使用 Pre-Order 的方式進行遍歷，一樣將問題縮限在一個小區域在用 recursive 重複此邏輯。

cout good nodes

範例程式碼

DFS
var goodNodes = function (root) {
  function dfs(node, maxValue) {
    let result = 0;
    let nextMaxValue = maxValue;

    // node 不存在就不用再往下找
    if (!node) return result;

    if (node.val >= maxValue) {
      // 修改 maxValue
      nextMaxValue = node.val;
      // GoodNode + 1
      result = 1;
    }

    result += dfs(node.left, nextMaxValue);
    result += dfs(node.right, nextMaxValue);

    return result;
  }

  return dfs(root, root.val);
};

BFS
var goodNodes = function (root) {
  let result = 0;

  if (!root) return result;

  // type Queue = [TreeNode, MaxValue][]
  const queue = [[root, root.val]];

  while (queue.length) {
    const queueLength = queue.length;

    for (let i = 0; i < queueLength; i++) {
      let [currentNode, maxValue] = queue.shift();
      if (currentNode.val >= maxValue) {
        maxValue = currentNode.val;
        result++;
      }

      if (currentNode.left) {
        queue.push([currentNode.left, maxValue]);
      }

      if (currentNode.right) {
        queue.push([currentNode.right, maxValue]);
      }
    }
  }

  return result;
};

Sliding Window

Longest Substring Without Repeating Characters - LeetCode 3

參考資料

題目描述

回傳字串 s 中不重複 substring 的長度

解題邏輯

使用 Sliding Window 的作法：

先定義 l = 0
r 則透過迴圈依序增加

使用 Set 來判斷單字是不是已經保存過：

把單字依序加入 Set 中，如果 Set 中已經重複，就要刪到該重複的字為止，例如 abcbb ，當 [abc] 在遇到下一個 b 時，需要把原本 Set 裡的 ab 都刪掉

參考答案

var lengthOfLongestSubstring = function (s) {
  let result = 0;

  // 使用 Set 來判斷單字是不是出現過
  const charSet = new Set();

  // 定義 sliding window 的 l 和 r
  let l = 0;
  for (let r = 0; r < s.length; r++) {
    // 如果 charSet 中已經存在這個字，要把所有這個字以左的都一併從 Set 中刪除
    while (charSet.has(s[r])) {
      charSet.delete(s[l]);
      l++;
    }

    charSet.add(s[r]);

    // 也可以寫 result = Math.max(result, charSet.size);
    result = Math.max(result, r - l + 1);
  }

  return result;
};

Dynamic Programming

Longest Palindromic Substring - LeetCode 5

參考資料

題目描述

從一個字串（s）中找出最長的回文字串，有兩種可能
- 答案是奇數次（odd），例如，aba、dcacd
- 答案是偶數次（even），例如，baab、caab

解題邏輯

把某一個字當成中點（n），往左右兩邊找（l, r）

只要 l >= 0 且 r <= s.length，且 s[l] === s[r] 就可以一直找

範例程式碼

while 裡面的內容基本上是重複的，可以考慮抽成 function

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let result = '';
  let resultLength = 0;

  [...s].forEach((_, idx) => {
    // handle odd length cases
    let l = idx;
    let r = idx;
    while (l >= 0 && r <= s.length && s[l] === s[r]) {
      const length = r - l + 1;
      if (length > resultLength) {
        result = s.slice(l, r + 1);
        resultLength = length;
      }
      l--;
      r++;
    }

    // handle even length cases
    l = idx;
    r = idx + 1;
    while (l >= 0 && r <= s.length && s[l] === s[r]) {
      const length = r - l + 1;
      if (length > resultLength) {
        result = s.slice(l, r + 1);
        resultLength = length;
      }
      l--;
      r++;
    }
  });

  return result;
};

Palindromic Substrings - LeetCode 647

參考資料

解題邏輯

這題的思路和 Longest Palindromic Substring（LeetCode 5）是一樣的。

參考答案

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function (s) {
  function countPali(l, r) {
    let count = 0;
    while (l >= 0 && r <= s.length && s[l] === s[r]) {
      count++;
      l--;
      r++;
    }
    return count;
  }

  let result = 0;
  [...s].forEach((_, idx) => {
    // handle old cases
    result += countPali(idx, idx);

    // handle even cases
    result += countPali(idx, idx + 1);
  });
  return result;
};

Decode Ways - LeetCode 91

參考資料

題目描述

把每一個大寫英文字母編碼，"A" 是 1、"B" 是 2、...、"Z" 是 26
題目會給一個字串作為 input，回傳所有「合法」結果的次數。例如，當 input 是 12，可能的結果為 (1, 2) 和 (12)，所以答案是 2；當 input 是 06，因為它無法組成任何合法的數字，所以答案是 0。

解題邏輯

合法的 digit

最多是兩位數，所以它會是一個 binary 的 decision tree
從最左邊開始，每次可以決定要拿一位數或兩位數，例如，如果是 121，則開始有 1 或 12 兩種可能

數字會是 1 ~ 26

如果第一個數字是 0，一定是不合法的
如果第一個數字是 1，後面可以是 0 ~ 9
如果第一個數字是 2，後面可以是 0 ~ 6
如果第一個數字 > 2，後面不能有任何數字

參考答案

s 裡的數字實際上是 string 而非 number

這題要特別留意，要把 s 裡的數字實際上是 string，而不是 number，因此在做判斷式（例如 === '0' 或產生 0 ~ 6 的陣列時，記得元素要是字串。

DP（Dynamic Programming）

個人覺得用 DP 的角度，從字串的後面開始比較好思考，假設數字是 123

position = 3，表示到底了，count + 1
position = 2，數字是 3，後面沒東西，有一種可能
position = 1，數字是 2 ，如果它
- 只有一位數字的話（2_3），後面的 3 有 cache.get(2) 的可能
- 接兩位數字的話（23_），後面沒東西，則會有 cache.get(3) 的可能
position = 0，數字是 1，如果它
- 只有一位數字的話（1_23），後面的 23 會有 cache.get(position + 1) 的可能
- 接兩位數字的話（12_3），後面的 3 會有 cache.get(position + 2) 的可能

decode_ways

使用 dynamic programming
/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
  const cache = new Map([[s.length, 1]]);
  const appendixOfTwo = Array.from({ length: 7 }, (_, i) => i.toString());

  // 121
  // 從最後面開始
  for (let i = s.length - 1; i > -1; i--) {
    if (s[i] === '0') {
      cache.set(i, 0);
    } else {
      // 只有一位數
      // result = dfs(i + 1)
      cache.set(i, cache.get(i + 1));
    }

    // 有兩位數的可能
    if (
      // 如果有兩位數
      i + 1 < s.length &&
      // 且介於 10 ~ 26
      (s[i] === '1' || (s[i] === '2' && appendixOfTwo.includes(s[i + 1])))
    ) {
      cache.set(i, cache.get(i) + cache.get(i + 2));
    }
  }

  return cache.get(0);
};

Recursion with Memoization

/**
 * @param {string} s
 * @return {number}
 */

// 226
// dfs(3) = 1;
// dfs(2) = dfs(3) = 1;
// dfs(1) = dfs(2) + dfs(3) = 1 + 1 = 2;
// dfs(0) = dfs(1) + dsf(2) = 2 + 1 = 3;

// 121
// dfs(3) = 1;
// dfs(2) = dfs(3) = 1;
// dfs(1) = dfs(2) + dfs(3) = 1 + 1 = 2;
// dfs(0) = dfs(1) + dsf(2) = 2 + 1 = 3;
var numDecodings = function (s) {
  // 如果 position = s.length，表示該字串是空的，例如 121，則 s[3] 會是空字串，表示已經它是終點，沒有下一個，所以 count 是 1
  // Map<Position, count>
  const cache = new Map([[s.length, 1]]);
  const appendixOfTwo = Array.from({ length: 7 }, (_, i) => i.toString());

  // "i" is the position(index) of the input "s"
  function dfs(i) {
    if (cache.has(i)) {
      return cache.get(i);
    }

    // 如果開頭是 0 的話一定不能接下一個
    if (s[i] === '0') {
      return 0;
    }

    let result = dfs(i + 1);

    if (i + 1 < s.length && (s[i] === '1' || (s[i] === '2' && appendixOfTwo.includes(s[i + 1])))) {
      result += dfs(i + 2);
    }

    cache.set(i, result);
    return result;
  }

  return dfs(0);
};

Array & Hashing​

Range Sum Query - Immutable - LeetCode 303​

解題邏輯​

Binary Search​

Koko Eating Bananas - Leetcode 875​

題目描述​

解題邏輯​

參考程式碼​

Trees​

Binary Tree Level Order Traversal - LeetCode 102​

題目描述​

解題邏輯​

範例程式碼​

Invert Binary Tree - LeetCode 226​

題目描述​

解題邏輯​

參考程式碼​

Count Good Nodes in Binary Tree - LeetCode 1448​

題目描述​

解題邏輯​

範例程式碼​

Sliding Window​

Longest Substring Without Repeating Characters - LeetCode 3​

題目描述​

解題邏輯​

參考答案​

Dynamic Programming​

Longest Palindromic Substring - LeetCode 5​

題目描述​

解題邏輯​

範例程式碼​

Palindromic Substrings - LeetCode 647​

解題邏輯​

參考答案​

Decode Ways - LeetCode 91​

題目描述​

解題邏輯​

參考答案​

DP（Dynamic Programming）​

Recursion with Memoization​

Array & Hashing

Range Sum Query - Immutable - LeetCode 303

解題邏輯

Binary Search

Koko Eating Bananas - Leetcode 875

題目描述

解題邏輯

參考程式碼

Trees

Binary Tree Level Order Traversal - LeetCode 102

題目描述

解題邏輯

範例程式碼

Invert Binary Tree - LeetCode 226

題目描述

解題邏輯

參考程式碼

Count Good Nodes in Binary Tree - LeetCode 1448

題目描述

解題邏輯

範例程式碼

Sliding Window

Longest Substring Without Repeating Characters - LeetCode 3

題目描述

解題邏輯

參考答案

Dynamic Programming

Longest Palindromic Substring - LeetCode 5

題目描述

解題邏輯

範例程式碼

Palindromic Substrings - LeetCode 647

解題邏輯

參考答案

Decode Ways - LeetCode 91

題目描述

解題邏輯

參考答案

DP（Dynamic Programming）

Recursion with Memoization