ARTS 第7周 | LeetCode 最低公共祖先 | Golang Worker Pool 原型

ARTS

ARTS 是陳浩（網名左耳朵耗子）在極客時間專欄裏發起的一個活動，目的是通過分享的方式來堅持學習。

每人每週寫一個 ARTS：Algorithm 是一道算法題，Review 是讀一篇英文文章，Technique/Tips 是分享一個小技術，Share 是分享一個觀點。

本週內容

本週的 ARTS 你將看到：

經典題「樹中節點的最低公共祖先」
一個 Golang 多隊列的 worker-dispatcher 原型
關於編程的方法論

Algorithm

這周的算法題是「樹中節點的最低公共祖先」。

[235. Lowest Common Ancestor of a Binary Search Tree

]( https://leetcode.com/problems...

[236. Lowest Common Ancestor of a Binary Tree

]( https://leetcode.com/problems...

這兩道題相同之處都是需要求公共祖先，但不同的是「二叉樹」還是「二叉查找樹」的最低公共祖先。對於二叉樹，只能通過後序遍歷來求。但是如果給出的兩個節點如果互爲父子的話，就無法通過簡單的後序遍歷來判斷了，需要單獨判斷。這種方法對於任何的二叉樹都是適用的，當然也包含二叉查找樹 BST. 如果對 BST 的公共祖先也是用這種方式的話，因爲沒有利用 BST 本身的排序特性，必然時間複雜度上會喫虧。話不多說，直接上代碼吧，歡迎拍磚。

先是普通二叉樹節點的最低公共祖先代碼。

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // dfs 函數里的邏輯沒辦法包含 p q 互爲父子的情況
    // 這裏只能單獨判斷
    if isAcst(p, q) {
        return p
    }
    if isAcst(q, p) {
        return q
    }
    var ans *TreeNode
    var dfs func(node, p, q *TreeNode) (bool, bool)
    dfs = func(node, p, q *TreeNode) (bool, bool) {
        if node == nil {
            return false, false
        }

        leftFoundP, leftFoundQ := dfs(node.Left, p, q)
        rightFoundP, rightFoundQ := dfs(node.Right, p, q)
        foundP, foundQ := leftFoundP || rightFoundP, leftFoundQ || rightFoundQ
        // 因爲是後序遍歷，暫時想不到很好的剪枝辦法
        if ans == nil && (foundP && foundQ) {
            ans = node
            return true, true
        }

        if node == p {
            foundP = true
        }
        if node == q {
            foundQ = true
        }
        return foundP, foundQ
    }
    fp, fq := dfs(root, p, q)
    if ans == nil && (fp && fq) {
        ans = root
    }
    return ans
}

// return p if p is ancestor of q
func isAcst(p, q *TreeNode) bool {
    var found bool
    var find func(node *TreeNode)
    find = func(node *TreeNode) {
        if node == nil {
            return
        }
        if found {
            return
        }
        if node == q {
            found = true
            return
        }
        find(node.Left)
        find(node.Right)
    }
    find(p)
    return found
}

然後是 BST 中節點的最低公共祖先。

// 首先這是一棵 BST 祖先節點的值
// 利用 BST 的性質，祖先節點的 Val 介於 p.Val q.Val 之間
// 反之，如果不介於二者之間的值是 p q 的祖先節點， 那麼一定存在更底層的祖先節點 
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    var ans *TreeNode
    node := root
    for !in(node, p, q) {
        if node == nil {
            break
        }
        if node.Val > max(p, q).Val {
            node = node.Left
        }
        if node.Val < min(p, q).Val {
            node = node.Right
        }
    }
    if node != nil {
        ans = node
    }
    return ans
}

func in(node, p, q *TreeNode) bool {
    return node.Val >= min(p, q).Val && node.Val <= max(p, q).Val 
}

func min(p, q *TreeNode) *TreeNode {
    if p.Val < q.Val {
        return p
    }
    return q
}

func max(p, q *TreeNode) *TreeNode {
    if p.Val > q.Val {
        return p
    }
    return q
}

Review 文章推薦

本週的文章推薦是 Handling 1 Million Requests per Minute with Golang . 文中介紹了一個高併發場景下的 Golang 多隊列的 worker-dispatcher 模式原型，雖然是很久之前的文章，但目前來看類似的 w-d 模型依然大同小異。

但是跳出條框的舒服，上面文中的多隊列方式的 workerpool 和各種 channel 入門中提到的單隊列方式（一個協程寫 chan 多個協程併發讀 chan）的根本區別是什麼呢？

我目前的直觀感受就是，高併發的情況都各隊列的 chan 就能多緩存一些 job（這裏指使用 chan 的 buffer），相比單隊列 chan 在高併發量的情況下更不容易出現 chan 滿導致拒絕 job 請求。但我想這應該是在 cpu 處理能力足夠的前提下，如果 cpu 處理能力本身就不足那就談不上多隊列更高效這種可能。

其實類似的問題有很多，這種問題無法用公式和算法之類的東西確切描述，像極了常說的「經驗」。但是開發人員一般都是更願意想相信專家而不是經驗，這就很有意思了。

Tip 編程技巧

本週依然沒有技巧。嚎啕大哭。

Share 靈光一閃

這一週的靈光一閃是關於上面文章中提到的關於編程中那些「經驗」的一些看法。這些經驗經常可以在分佈式系統以及操作系統中找到，多數時候乍一看感覺非常正確，但有無法給出公式般準確的推導過程。給人一種既神祕又強大的感覺，以我目前的 conding 能力還很難掌握這些經驗。甚至在未來的某個階段這些經驗會是我最需要學習的東西，這都很難說。

我暫時把這些「經驗」叫做編程之禪。