LeetCode - JavaScript Topic (2 Hard)

tags: `JavaScript`

category: `LeetCode`

description: `LeetCode - JavaScript Topic (2 Hard)`

created_at: `2023/05/05 22:00:00`

cover image

前言

很久很久沒有打開 LeetCode 了，這次因為前幾天發現一些開發流程，~~感覺自己要被取代要失業了~~，所以就想說打開 LeetCode 來刷一下。

然後剛剛好 LeetCode 好像這陣子在推 JavaScript 的 Topic，然後看到題目也不多，就花了一天的零碎時間把所有的解了一遍，大多題目都很簡單，而這篇就寫當中唯二的 Hard 題目(雖然我覺得好像沒到 Hard?)

當中第一題 1456. Maximum Number of Vowels in a Substring of Given Length 不屬於這個系列(而是每日題目)，但想說要追求全部打勾(~~強迫症~~)，就順便解了一下。

哪兩題?

2630. Memoize II
2650. Design Cancellable Function

`2630. Memoize II`

這一題有比較簡單的版本，2623. Memoize，建議可以先從這題去試水溫。

這兩題主要都是在做同樣的事情，只是 II 變得比較彈性，~~非常適合來造輪子~~

所以先從簡單的開始看: 2623. Memoize

題目是這個樣子的:

給你一個 function，然後你要回傳一個具有記憶能力的 function，當我使用一樣的參數丟進去的時候，你就不要再重新呼叫了，直接拿之前的結果去用就好。

這其實也很像動態規劃的其中一個重要特性，算過的就不要重複算了~~浪費時間~~，用空間換取時間，只是以往解 dp，都是為了特定目的，而這題是要做出一個更共通的解法。

舉個例子，老樣子還是費式數列(fib)，~~因為這個例子最好懂，雖然有些人不認為 fib 屬於 dp 問題，但沒關係，懂意思就好~~

簡單複習一下 fib 是什麼:

if n <= 1: fib(n) = n
else: fib(n) = fib(n-1) + fib(n-2)

簡單來說就是當 n 小於等於一，就回傳 n，否則就是前兩項的和，寫成遞迴就像下面這樣

function fib(n) {
    if (n <= 1) {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}

console.log(fib(0)) // 0
console.log(fib(1)) // 1
console.log(fib(2)) // 1
console.log(fib(3)) // 2
console.log(fib(4)) // 3
console.log(fib(5)) // 5
console.log(fib(6)) // 8

你喜歡的話也可以改一下寫法(?)

const fib = n => n <= 1 ? n : fib(n-1) + fib(n-2)

但這樣寫會有個問題，不管是第一種還是精簡過的第二種，都會有重複計算的問題，例如你把過程解開來看:

fib(6) = fib(5) + fib(4)
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0

可以看到 fib(4) 會被計算兩次，你可能沒感覺，但 fib(4) 重新計算的話，那換句話說 fib(2) 也會被計算兩次，這樣就會造成浪費，而且這只是最小估計(還沒實際展開)，如果 n 再大一點，那浪費的就更多了。

用一張圖來表示的話，就像下面這樣:

可以看到說有太多重複的地方，基本上大多右子樹都是浪費，或者說藍色節點就是重複計算的地方，沒必要再往下遞迴。

所以這時候就可以用 Memoize 來解決這個問題，把計算過的結果記錄下來，下次再遇到就直接拿來用，不用再重新計算一次。

假設我就簡單以 JavaScript 的物件來記錄，key 就是參數，value 就是結果，那 fib 就會變成這樣:

const dp = { 0: 0, 1: 1} // 先寫死初始狀態(前兩項)
function fib(n) {
    if (typeof dp[n] !== 'undefined') {
        return dp[n]
    }

    dp[n] = fib(n-1) + fib(n-2)
    return dp[n]
}

備註: 你也可以使用陣列當作 dp，只是這邊示意是使用 Object 形式去存。

這樣就可以避免重複計算了， fib(n) 會先檢查 dp 裡面有沒有 n 的結果，如果有就直接回傳，沒有的話就計算一次，並且把結果記錄下來，下次再遇到就可以直接拿來用。

可以先戳戳看舊版的 fib，帶入一個值，不用很大，大概 40 你就會很有感覺他很慢了。

而新版的 fib 你可以帶入 100 甚至更大的值，也都是瞬間出來結果。(~~但你也不要太故意，會超過遞迴深度~~)

進入正題

回顧一下上面講到的題目敘述:

就有點像是說你寫第一版的 fib ，丟到我這個函數之後，我生出第二版的給你用。

function fib(n) {
    if (n <= 1) {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}

fib = memoize(fib)
console.log(fib(100))

而上面這個 memoize 就是這個題目要實作的部分:

只是這題是簡單版的，只要實現三個函數就可以了:

sum: 接收兩個整數 a 與 b，回傳 a + b
fib: 接收一個整數 n，回傳 n <= 1 就回傳 n，否則就回傳 fib(n-1) + fib(n-2)
factorial: 接收一個整數 n，回傳 n <= 1 就回傳 1，否則就回傳 factorial(n-1) * n

不過我不喜歡寫死，所以還是寫一個共通的版本:

function memoize(fn) {
    const dp = {}
    return function(...args) {
        const key = JSON.stringify(args)
        if (typeof dp[key] !== 'undefined') {
            return dp[key]
        }

        dp[key] = fn(...args)
        return dp[key]
    }
}

只是這是一個很暴力的作法，但是很好懂(?)，就是把參數轉成字串當作 key，然後把結果記錄下來，下次再遇到就直接拿來用。

~~上面這段是 Copilot 幫我寫的，實際上我當初寫法就跟 II 解法很像~~

這邊也附上我當初解這題的 code

function memoize(fn) {
    const root = {}
    return function(...args) {
        let head = root
        for (let i = 0; i < args.length - 1; i++) {
            const arg = args[i]
            if (typeof head[arg] === 'undefined') {
                head[arg] = {}
            }
            head = head[arg]
        }

        const key = args[args.length-1]
        if (typeof head[key] === 'undefined') {
            head[key] = fn(...args)
        }

        return head[key]
    }
}

有點像是鏈結串列(LinkedList)的解法(~~雖然實際上是樹Tree~~)，因為我假設他參數都會乖乖丟固定的，不會有一下一個參數一下兩個參數的問題，所以我就把他當作單純鏈結串列來處理，每個參數都是一個節點，然後最後一個參數就是值。

也就是說我假設 sum 這個函數只會 sum(1, 2) 或是 sum(2, 3) 之類的，不會有 sum(1, 2, 3) 的呼叫方式。

假設我照下面的順序去呼叫:

sum(1, 2)
sum(1, 3)
sum(2, 4)
sum(2, 3)
sum(1, 2)
sum(2, 4)

那他的過程會像這樣 []代表結果

sum(1, 2)

root -> 1 -> 2 -> [3]

sum(1, 3)

root -> 1 -> 2 -> [3]
          -> 3 -> [4]

sum(2, 4)

root -> 1 -> 2 -> [3]
          -> 3 -> [4]
     -> 2 -> 4 -> [6]

sum(2, 3)

root -> 1 -> 2 -> [3]
          -> 3 -> [4]
     -> 2 -> 4 -> [6]
          -> 3 -> [5]

sum(1, 2): 已存在，直接用，拿到結果 3

root -> 1 -> 2 -> [3]
          -> 3 -> [4]
     -> 2 -> 4 -> [6]
          -> 3 -> [5]

sum(2, 4): 已存在，直接用，拿到結果 6

root -> 1 -> 2 -> [3]
          -> 3 -> [4]
     -> 2 -> 4 -> [6]
          -> 3 -> [5]

就像上面這個流程去解決這一題。

進入正題 `II`

這題就是 2623. Memoize 的進階版，題目不再規定你只能處理固定參數的函數，而是可以處理任意參數的函數。

而且參數還不限定型別，只要是 === 就算是一樣的，所以你可以傳 function 進去，也可以傳 object 進去，只要是 === 就好。

這樣的話就不能夠單純使用 Object 來記錄了，因為 Object 的 key 只能是可 string 或是 symbol，所以這邊就要使用 Map 來記錄。

而且因為參數不固定，所以也不能使用單純的型態當作節點，而是要記錄當前的節點是不是有值以及下一個節點。

文字上可能有點模糊，但這邊跟字典樹(Trie)有點像，都要去紀錄當前走訪到的節點是不是有資料。

假設下面是一個 Trie，他有著以下資料

app
apple
car
cat
category

綠色的節點就是有資料的節點，其他都只是過場而已。

而這邊的 Memoize II 就是要做出一個類似的結構，只是他的節點不是字元，而是參數，而且參數可以是任意型別。

function memoize(fn) {
    const valueKey = Symbol('value')
    const defaultValue = Symbol('undefined')
    const root = new Map()
    root.set(valueKey, defaultValue)

    return function(...args) {
        let head = root
        for (let i = 0; i < args.length; i++) {
            const arg = args[i]
            if (!head.has(arg)) {
                const node = new Map()
                node.set(valueKey, defaultValue)
                head.set(arg, node)
            }
            head = head.get(arg)
        }

        const node = head
        if (node.get(valueKey) === defaultValue) {
            node.set(valueKey, fn(...args))
        }

        return node.get(valueKey)
    }
}

在 Trie 當中是無根樹，而這邊因為有可能沒帶入參數，所以根節點也有可能有資料。

基本上跟上一題的邏輯沒有差太多，只是剛剛解第二次，所以稍微整理了一下 code。

解這題算是滿順利的，跟我以前對 LeetCode 的 Hard 題目印象不太一樣，總感覺沒有到 Hard 的等級(?)

`2650. Design Cancellable Function`

這題題目是這樣的:

給你一個 generator，然後你要回傳一個陣列，裡面包含兩個值，一個是 cancel 函數，一個是 promise。

然後題目有說道，你可以假設 generator 只會 yield promise，而你的函數要負責把 promise 的結果回傳給 generator，如果 promise 回傳 reject，你的函數要把 error 丟回給 generator。 ~~這邊他範例測資就有 yield 42，42 並不是一個 promise，所以你還是得處理~~

然後如果 cancel 被呼叫，那你的函數要丟出一個錯誤給 generator，錯誤訊息是 Cancelled，如果 error 被 catch，那你的函數要回傳下一個 yield 或是 return 的值，否則就是回傳 reject 的 error。

當 generator 完成的時候，你的函數要回傳 generator 的結果，如果 generator 丟出 error，那你的函數要回傳 reject 的 error。

這題看起來就比較有 Hard的感覺了(?)，~~至少題目滿繞的~~

解這題之前你必須要先了解 generator 與 promise 的概念，而 promise 會看這篇的人應該都知道，所以這邊就不多做解釋。~~至少我覺得 promise 應該是大家都會的~~

而 generator 的話，我就稍微講一下，因為我覺得這題的重點就在 generator 上。~~雖然 promise 也很重要~~

generator 是一種特殊的函數，他可以被暫停，然後可以被重啟，而且可以傳值給他，也可以從他取值。

舉個例子，假設我有一個 generator，他長這樣:

function* gen() {
    console.log('start')
    const a = yield 1
    console.log('a', a)
    const b = yield 2
    console.log('b', b)
    const c = yield 3
    console.log('c', c)
    return 4
}

然後我要用一個變數去接他:

const g = gen()

這時候他並不會執行，因為他只是一個函數，你必須要呼叫他才會執行，而且他也不會執行到底，他會執行到第一個 yield，然後暫停，等待你傳值給他。

所以你可以這樣呼叫:

const g = gen()
console.log(g.next()) // { value: 1, done: false }

可以看到說他回傳了一個物件，裡面有兩個值，一個是 value，一個是 done，value 就是 yield 後面的值，而 done 就是說他是否執行完畢，如果 done 是 true，那就代表他執行完畢了，否則就是 false。

而且他確實只執行到 yield 1，因為你可以看到說他只印出了 start，而沒有印出 a。

然後後面的同理，你可以這樣呼叫:

const g = gen()
console.log(g.next()) // { value: 1, done: false }
console.log(g.next()) // { value: 2, done: false }
console.log(g.next()) // { value: 3, done: false }
console.log(g.next()) // { value: 4, done: true }

然後你會看到一堆 console.log，那些 a、b、c 都是 undefined，因為你沒有傳值給他，next() 是可以傳值的

const g = gen()
console.log(g.next(100)) // { value: 1, done: false }
console.log(g.next(200)) // { value: 2, done: false }
console.log(g.next(300)) // { value: 3, done: false }
console.log(g.next(400)) // { value: 4, done: true }

你會得到這樣的輸出

a 200
b 300
c 400

為什麼 a 不是 100?

為了清楚解釋這個，我稍微畫了幾張圖:

首先是斷點的部分(黑色線)

接著是 yield 的值傳的位置

再來是 next

接著把斷點跟 next 一起看，就可以知道為什麼 a 是 200 了

最後再把全部一起看，可以看出來到藍色線為止是一個批次，然後從紅色線開始。

換做文字描述的話就是以下:

g.next(100): 執行到 yield，得到 1，然後暫停，等待傳值
g.next(200): 傳值 200 給 a，執行到 yield，得到 2，然後暫停，等待傳值
g.next(300): 傳值 300 給 b，執行到 yield，得到 3，然後暫停，等待傳值
g.next(400): 傳值 400 給 c，執行到最後且有個 return，所以得到 4。

所以 a 是 200，b 是 300，c 是 400。

大概是上面這個運作流程。

`Generator` 的 `throw`

而這題還需要用到 generator 的 throw，他可以丟出一個錯誤給 generator，然後 generator 可以用 try...catch 來接。

舉個例子: (假設我要觸發 yield 2)

function* gen() {
    try {
        yield 1
    } catch {
        yield 2
    }
}

如果你只有一昧的 next，那你會得到 1，因為你沒有丟出錯誤，所以 catch 不會被執行，也就是 yield 2 不會被執行。

const g = gen()
console.log(g.next()) // { value: 1, done: false }
console.log(g.next()) // { value: undefined, done: true }

提示: 為什麼第二個 next 會得到 undefined，因為 yield 1 之後沒有 return 東西，所以他會得到 undefined。

如果你要讓 catch 被執行，執行到 yield 2，那麼就要丟出錯誤，這時候就要用到 throw。

const g = gen()
console.log(g.throw())

這時會得到錯誤

caught undefined

且這時你在呼叫 next() 也沒有意義了，因為他沒捕捉到錯誤，可是你可能會問，不對阿不是有 catch 嗎? 為什麼沒有執行到 yield 2?

這時回去看看前面的流程，你必須先呼叫一次 next() 到達斷點之後，才會進入 try...catch 的區塊內，所以你必須要這樣呼叫:

const g = gen()
console.log(g.next()) // { value: 1, done: false }
console.log(g.throw()) // { value: 2, done: false }
console.log(g.next()) // { value: undefined, done: true }

這樣才會正常拿到 yield 2 的值。

理解完 `generator` 基本操作之後，開始解題

先整理一下題目的需求:

寫一個函數，接收一個 generator，回傳一個陣列，裡面包含兩個值，一個是 cancel 函數，一個是 promise。
需要把 promise 的結果回傳給 generator，如果 promise 回傳 reject，要把 error 丟回給 generator。
如果 cancel 被呼叫，要丟出一個錯誤給 generator，錯誤訊息是 Cancelled，如果 error 被 catch，要回傳下一個 yield 或是 return 的值，否則就是回傳 reject 的 error。
當 generator 完成的時候，要 resolve generator 的結果，如果 generator 丟出 error，要回傳 reject。

上面的步驟有點多，所以直接附上整理過的 Code 加上註解解釋吧:

var cancellable = function(generator) {
    let canceled = false  // 定義一個變數，用來判斷是否被取消

    const next = (currentResult) => {
        return new Promise(async (resolve, reject) => {
            try {
                const {value, done} = currentResult  // 抓出當前的 value 跟 done
                try {
                    const val = await Promise.resolve(value) // 把 value 轉成 promise 並解析
                    if (canceled) {  // 如果被取消
                        throw 'Cancelled' // 丟出錯誤
                    } else if (done) { // 如果已經完成
                        resolve(val) // 回傳結果
                    } else { // 如果還沒完成
                        resolve(next(generator.next(val))) // 呼叫 next，並把結果 resolve
                    }
                } catch (e) { // 如果 value 是 reject 或 throw 的話
                    const nextResult = generator.throw(e) // 丟出錯誤給 generator，如果有處理就會往下，沒處理就會跑到 catch
                    if (canceled) { // 如果被取消
                        resolve(await nextResult.value) // 把結果 resolve
                    } else { // 如果沒被取消
                        resolve(next(nextResult)) // 呼叫 next，繼續往下執行
                    }
                }
            } catch (e) { // 如果 generator 丟出錯誤
                reject(e) // 回傳 reject
            }
        })
    }


    return [
        () => canceled = true,
        new Promise((resolve, reject) => {
            return next(generator.next()).then(resolve).catch(reject) // 呼叫 next，並把結果 resolve 或 reject
        })
    ] // 回傳一個陣列，第一個是 cancel 函數，第二個是 promise
};

上面讀起來很單純，但強烈建議親自下去寫一遍，其實沒有那麼簡單，你必須很理解 generator 跟 promise 的互動，才能夠寫出來。

如果還是不理解，我嘗試用一張圖來解釋這題到底在幹嘛:

就拿他最複雜的 Example 6 來說，他的流程是這樣的: (從星星處開始看)

理解完第一次循環後，後面我一次把他全部展開，你可以看到說他的流程是這樣的:(順序為「黑」、「藍」、「紅」、「紫」)

過程中可能有少一些線，但你懂我意思就好，~~不太會畫圖~~

避免不確定 Cancel 的流程，所以拿 Example 5 當作範例，再來畫一張圖:

(因為這可能是比較容易有問題的，為什麼他 Cancel 卻還是 resolved)

線有點多，總之就是按照順序看(從星星處開始，由上往下)。

主要重點是他在第二次的 yield new Promise(res => setTimeout(res, 100)); 解析完之後發現被 Cancel 了，所以拋出錯誤。

總結

雖然平時幾乎不會用到 generator (~~也可能是我沒用到而已~~)，但這題還是滿有趣的，而且也算是滿有挑戰性的，也可以讓你更了解 generator 跟 promise 的互動，強烈建議親自下去寫一遍。

最後更新時間: 2023年05月05日.

LeetCode - JavaScript Topic (2 Hard)

tags: JavaScript

category: LeetCode

description: LeetCode - JavaScript Topic (2 Hard)

created_at: 2023/05/05 22:00:00

前言

哪兩題?

2630. Memoize II