[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;
};
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;
};