一些用 TypeScript 刷題的小技巧
刷題(Leetcode / others)的重點是資料結構、演算法，而這篇文章只是想分享一些平常開發相對不常用，但卻能大大降低解題時間的小技巧。
--
由於 TypeScript 是 JavaScript 的超集，下文會用 TS 代稱，但同樣的概念可以被應用在 JavaScript 中，這篇文章面向使用 TS/JS 作爲主力語言的前後端工程師，請自行參考有趣的部分。
另外，我有把題目整理在 GitHub repository，并且使用 TypeScript 加上 markdown 整理不同題型的筆記，有需要可以參閲——realdennis/leetcode-ts。
大綱
- 快速 Swap 兩個 array item
- 透過 Array.from 初始化一、二維陣列初值
- 使用原生 Array 方法來完成 stack & queue
3.1. 可被接受的假設與效能考量
由於篇幅原因先寫三點，希望能加快閲讀速度與理解時間。
快速 Swap 兩個 array 中的 item
常見於大小對換、位置交換、backtracking。
傳統做法：
function swap(arr, idx1, idx2) {
let temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}TS 快速做法：
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];驗證：
const arr = ['a','e','i','o','u'];
[arr[0], arr[1]] = [arr[1], arr[0]];
console.log(arr);> VM308:3 (5) ['e', 'a', 'i', 'o', 'u']
另外其實 Tree left/right 也可以換，不過我不推薦，容易亂掉。
注意：前一行一定要加分號，不然會被錯判成再為前一行取 property value。
透過 Array.from 初始化一、二維陣列初值
常見於動態規劃題目或用於複製陣列
const dp = Array.from({length:10}, ()=>1);
console.log(dp);>(10) [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
這個 Array.from 有什麽好處呢，他第一個參數可以控制長度，第二個參數可以設定初值。
所以可以有以下的變體
- 初始化一個與 input 長度一致的一維陣列
const N = nums.length;
const dp = Array.from({length: N}, ()=>0);2. 初始化二維陣列
const M = grid.length,
N = grid[0].length;const dp = Array.from({length:M}, ()=>Array.from({length:N}, ()=>0))
3. 客制化初始值
const dp = Array.from({length:10}, (_,idx)=>idx+1);
> (10) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]4. 複製并且修改初始值
const nums = [1,3,5];
const temp = Array.from(nums, val=>2*val);
console.log(temp);
> [2,6,10]當然你也可以用 map。
注意：你或許會覺得 new Array() + fill 有相似用法，但若是二維陣列你透過此來初始化：
const dp = new Array(3);
dp.fill(new Array(3));
dp.forEach(inner=>inner.fill(0))
// [[0,0,0],[0,0,0],[0,0,0]];dp[0][0] = 1;
console.log(dp);// [[1,0,0],[1,0,0],[1,0,0]]
你可能沒有察覺，但是第二行的 dp.fill 塞進去的是同個 instance ，他們具有同個 reference ，所以最好的方法還是透過 callback + delay calculate 避免傳到同個參。
v.s.
const dp = Array.from({length:3}, ()=> Array.from({length:3},()=>0))
dp[0][0] = 1;
console.log(dp);// [[1,0,0],[0,0,0],[0,0,0]]
3. 使用原生 Array 方法來完成 stack & queue
Array 有四大方法分別是 push /pop / unshift /shift ，對應的是右推、右出、左推、左出。
通常狀況下你不會用到 unshift ，所以這個方法可以跳過。
- push / pop 就是 stack
- push / shift 就是 queue
用 push + shift = queue ，BFS 印出 level-order 爲例子。
如果你覺得這張圖很眼熟，源自於之前寫的文章《你其實不用在 JavaScript 實作一個 Queue》。
不過 unshift 會推到整個 array 結構，如果有 performance concern 要注意一下，不過這邊不討論 runtime implementation。[1]
由於打到這邊看到前一篇文下面在討論這不算 queue 之類的討論，我想看到這篇文章的讀者介紹一下“怎樣叫做有 performance concern”的狀況。
3.1 什麽是可被接受的假設與效能考量？
- Find Bottom Left Tree Value
- 請你設計一個 O(1) insert O(1) delete 的 queue
如果是 2. 請你認命的跟 interviewer 確認想要看到的，以及 assessment 的標準，也許對方是想看到 linked-list 實作 v.s. Array 實作的分析，届時請不要直接用 built-in API 敷衍對方。
無論哪個語言都一樣，實作資料結構也是考點，透過資料結構實作算法也是考點。
若今天的題目是 high-level 的，比如需要用到 monotonic-queue 或是 BFS traversal 只是其中一個小的 sub-problem ，請不要花大把時間那邊刻一個queue。（我建議啦…）
一場面試約莫只有45分鐘，請你透過假設的方式，假設 standard library 環境是最佳化去解決這個問題。
同樣的狀況在 Heap (priority-queue) 中亦是如此，TypeScript 并沒有 built-in 的 heap 結構，在 Leetcode 環境中可以使用 datastructure-js/priority-queue (yes, I’m also a contributor) & datastructure-js/queue，請查閲 Leetcode docs。
注釋區（可跳過）
[1] JavaScript 在不同環境有不同的 implementation ，若是 unshift / shift 使用的是 C++ 的 deque，勢必能達到 FIFO O(1) unshift 的效果。
不過，這類的實作規範并不會寫在一個語言的文檔，且各家 browser 也有各自的 performance improvement 以及考量，可以查看之前那篇 《[JavaScript] 從 Array 的 sort 方法，聊到各瀏覽器的實作，沒想到 Chrome 和FireFox 的排序如此不同》。 對於在自己在瀏覽器或是哪裏做的實驗了，我個人感謝賜教。
