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

栏目: IT技术 · 发布时间: 4年前

内容简介：ARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是通过分享的方式来坚持学习。每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。本周的 ARTS 你将看到：

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 能力还很难掌握这些经验。甚至在未来的某个阶段这些经验会是我最需要学习的东西，这都很难说。

我暂时把这些「经验」叫做编程之禅。