一些用 TypeScript 刷題的小技巧 II

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

前言

Photo by NeONBRAND on Unsplash

大綱

  1. 透過 ES6 的 Map 與 Set 來快速操作
  2. apply or spread 找陣列最大

話不多説我們趕緊開始!

最大初始值與最小初始值

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

  • Number.MAX_SAFE_INTEGER
  • Number.MIN_SAFE_INTEGER

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

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

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

傳統做法 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)

一些 Set 可以使用的例子(TS)

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) 的算法中,優化這個東西就有點沒必要。

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

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