一些用 TypeScript 刷題的小技巧

刷題(Leetcode / others)的重點是資料結構、演算法,而這篇文章只是想分享一些平常開發相對不常用,但卻能大大降低解題時間的小技巧。

由於 TypeScript 是 JavaScript 的超集,下文會用 TS 代稱,但同樣的概念可以被應用在 JavaScript 中,這篇文章面向使用 TS/JS 作爲主力語言的前後端工程師,請自行參考有趣的部分。

另外,我有把題目整理在 GitHub repository,并且使用 TypeScript 加上 markdown 整理不同題型的筆記,有需要可以參閲——realdennis/leetcode-ts

Photo by Belinda Fewings on Unsplash

大綱

  1. 快速 Swap 兩個 array item
  2. 透過 Array.from 初始化一、二維陣列初值
  3. 使用原生 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 有什麽好處呢,他第一個參數可以控制長度,第二個參數可以設定初值。

所以可以有以下的變體

  1. 初始化一個與 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 什麽是可被接受的假設與效能考量?

  1. Find Bottom Left Tree Value
  2. 請你設計一個 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 的排序如此不同》。 對於在自己在瀏覽器或是哪裏做的實驗了,我個人感謝賜教。

If any interest, 👉 https://realdennis.me.

If any interest, 👉 https://realdennis.me.