一些用 TypeScript 刷題的小技巧 II

接續上篇，一些可被使用於刷題的小技巧。

realdennis

6 min readDec 23, 2021

前言

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

大綱

最大初始值與最小初始值
透過 ES6 的 Map 與 Set 來快速操作
apply or spread 找陣列最大

話不多説我們趕緊開始！

最大初始值與最小初始值

多用於DP類題目，或是需要動態去測定數字，比如判斷二元搜尋樹是否合法，就可以透過更新當前合法之最大最小值。

在 TypeScript 中的 Number 有兩個個好用的東西：

Number.MAX_SAFE_INTEGER
Number.MIN_SAFE_INTEGER

你可以用這兩個常數去設定最大/小初值。

98. Validate Binary Search Tree （合法 BST 驗證，設定初始合法範圍）
53. Maximum Subarray（求最大之題目，初始值設定MIN_SAFE_INTEGER）
63. Unique Paths II（有障礙物的DP，未知距離初值設最大）

注意：我們有另外兩個常數叫做 Number.MAX_VALUE & Number.MIN_VALUE ，而選擇這個較爲安全的常數原因在此篇文章。

透過 ES6 的 Map 與 Set 來快速操作

多用於需要 hashmap 、 hashset 之題型，例如字母頻率統計、快速 access item 、 sliding window。

傳統做法 Object & key

const dict = {};
dict['a'] = 0;if('a' in dict) {
  console.log(dict['a'])
  delete  dict['a']
}
console.log(dict);// 0
// {}

透過 ES6 Map 更加優雅

const dict:Map<string,number> = new Map();
dict.set('a', 0);if(dict.has('a')) {
  console.log(dict.get('a'));
  dict.remove('a');
}console.log(dict);// 0
// Map(0) {size: 0}

透過 ES6 Set 判斷存在狀態

const state:Set<string> = new Set();state.add('a');
state.add('b');console.log(state.has('a')) // trueif(state.has('b')) state.add('c')console.log(state.size);//3
state.delete('a');console.log(state) // Set(2) {'b', 'c'}

注意： ES6 map/set 的 runtime implementation 可以參考這篇，但還是必須得說這不是保證的，但我們可以在 interview / 白板，假設使用的是 unordered_map / using HashTable implement。

更多的 unordered_map vs ordered_map 可以參考這篇 map vs unordered_map in C++。

老話一句，如果 HashMap用來解決 High level 的題目可以大膽假設，但如果面試題為要求使用 balanced tree 實作 orderded_map ，請不要直接 call built-in API。

一些 Map 可以使用的例子（TS）

347. Top K Frequent Elements （統計頻率）
1. Two Sum （透過Array.prototype.map 來做單行 entries initial）
lodash memorize （source code）

一些 Set 可以使用的例子（TS）

133. Clone Graph （透過 Set 來做 visited state）
3. Longest Substring Without Repeating Characters （sliding window state）
200. Number of Islands （作爲 collections ）

apply or spread 找陣列最大

當我們要尋找陣列中最大的值，有幾種方法。

傳統做法1—邊運算邊保存

let ret = Number.MIN_SAFE_INTEGER;for(let i=0; i<N; i++) {
  const res = /*...*/
  if(res > ret) ret = res;
}

傳統做法2—最後 iteration

等價於上面的 code 只是另外多一次 iteration 去 pick 最大值。

TypeScript 做法1—apply

Math.max.apply(null, [1,2,3,4]); // 4

apply 的做法等於是傳入 arguments array，所以等價於 Math.max(1,2,3,4) ，想瞭解更多可以觀看這篇《函數原型最實用的 3 個方法 — call、apply、bind》

TypeScript 做法2—spread parameters

如果你壓根不想管，或是 call、apply 容易混肴，那麽直接 spread 吧！（如果面試官看不懂 spread 那可以推薦他來看我的文章。）

const arr = [1,2,3,4]
Math.max(...arr); // 4

更多解構相關的文章，可以查看這篇《解構賦值 — 設計函數時的小技巧》。

以上四種做法都是 O(N) ，唯獨差異在於第一個傳統做法是在 logic 中順便更新最大值狀態。如果你想 one-passed solution （如 Kandens’ algorithm pattern probs），可以在原邏輯中做掉。

不過你知、我知、獨眼龍也知道，O(N) + O(N) 還是 O(N)，且若是你的整體程式碼在 O(NlogN) or O(N*N) 的算法中，優化這個東西就有點沒必要。

一些用 TypeScript 刷題的小技巧 II

接續上篇，一些可被使用於刷題的小技巧。

前言

大綱

最大初始值與最小初始值

透過 ES6 的 Map 與 Set 來快速操作

apply or spread 找陣列最大

Written by realdennis