乐趣区

关于git:Git-中的算法最近公共祖先

大家好,我是 lucifer。明天给大家分享 Git 中的算法。

这是本系列的第二篇 –《Git 中的最近公共先人》,第一篇在
这里

<!– more –>

git merge-base

git merge-base A B 能够查找 A 提交和 B 提交的最近公共先人提交。而因为 分支和标签
在 Git 中仅仅是提交的别名,因而 A 和 B 也能够是分支或者标签。


         o---o---o---B
        /

---o---1---o---o---o---A

如上图的 Git 提交状况,那么 git merge-base A B 会间接返回提交 1 的哈希值。

更多对于 merge-base的用法细节能够参
考官网文档

如何查找公共先人呢?

咱们晓得 git 每次提交,实际上都是新建了一个提交对象,外面记录一些元信息。比方:

  • 提交人
  • 提交工夫
  • 哈希
  • 上一次提交的援用
  • 。。。

而上一次提交的援用导致了 git 提交是一个链表构造。而 git 反对创立分支,并基于分支
进行开发,因而 git 提交实质上是有向无环图构造。

如上图,咱们基于提交 2 创立了新分支 dev,dev 上开发后咱们能够将其合并到主分支
master。

而当咱们执行合并操作的时候,git 会先应用 merge-base 算法计算最近公共先人。

如果最近公共先人是被 merge 的 commit,则可执行 fast-forward。如下图,咱们将 dev
合并到 master 就能够 fast-forward,就如同没有创立过 dev 分支一样。

最初举一个更简单的例子。如下图,咱们在提交 3 上执行 git merge HEAD 提交 6。会发
生什么?

答案是会找到提交 2。那怎么找到 2 呢?

如果从提交 6 登程一直找父节点,找到 1,并将其放到哈希表中。接下来再从提交 3 登程
同样一直找父节点,如果父节点在哈希表中存在,那么咱们就找到了公共先人,因为是找到
的第一个公共先人,因而其是最近公共先人,间接返回即可。

力扣中刚好有一个题目,咱们来看下。

力扣真题

题目地址(236. 二叉树的最近公共先人)

https://leetcode-cn.com/probl…

题目形容

给定一个二叉树, 找到该树中两个指定节点的最近公共先人。百度百科中最近公共先人的定义为:“对于有根树 T 的两个节点 p、q,最近公共先人示意为一个节点 x,满足 x 是 p、q 的先人且 x 的深度尽可能大(一个节点也能够是它本人的先人)。”示例 1:输出:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输入:3
解释:节点 5 和节点 1 的最近公共先人是节点 3。示例 2:输出:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输入:5
解释:节点 5 和节点 4 的最近公共先人是节点 5。因为依据定义最近公共先人节点能够为节点自身。示例 3:输出:root = [1,2], p = 1, q = 2
输入:1


 

提醒:树中节点数目在范畴 [2, 105] 内。-109 <= Node.val <= 109
所有 Node.val 互不雷同。p != q
p 和 q 均存在于给定的二叉树中。

前置常识

  • 二叉树
  • 树的遍历
  • 哈希表

思路

这道题是给你一个二叉树,让你从二叉树的根登程。

这和 Git 是不一样的,Git 中咱们须要从两个提交节点登程往父节点找。

那是不是意味着下面办法不能够套用了?

也不是。咱们能够在遍历二叉树的时候保护父子关系,而后问题就转化为了后面的问题。

代码

  • 语言反对:Java

Java Code:


class Solution {HashMap<Integer, TreeNode> map = new HashMap<>(); // 关系为:key 的父亲是 value
    HashSet<TreeNode> set = new HashSet<>();

    public void dfs(TreeNode root) {if (root.left != null) {map.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {map.put(root.right.val, root);
            dfs(root.right);
        }
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {dfs(root);
        // 从 p 登程,找到 p 的所有先人节点,将其放入 HashSet
        while (p != null) {set.add(p);
            p = map.get(p.val);
        }
        // 从 q 登程找到第一个能在 HashSet 中找到的节点,即为最近公共先人
        while (q != null) {if (set.contains(q)) {return q;}
            q = map.get(q.val);
        }
        return null;
    }
}

复杂度剖析

令 n 为链表长度。

  • 工夫复杂度:$O(n)$
  • 空间复杂度:$O(n)$

优化

实际上该算法效率并不高。如果咱们仓库提交很多,也就是 N 十分大,也是会慢的。

有没有优化的可能?

当然能够。而且优化的角度有很多。

这不,这位同学就想到了预处理
,链接在这里。
即第一次保护好了节点信息,将其存到文件里,那么当前执行 merge-base,就不须要对已
经解决过的节点进行遍历了。** 实践上,不论 merge-base 多少次,咱们都仅遍历一次节
点 **。

真的这么现实么?

很惋惜不是的。比方我执行了 rebase,reset 等操作扭转了节点怎么解决?这里的细节很
多,我就不在这里开展了。感兴趣的能够退出我的力扣群探讨。

总结

git merge-base 实质上就是一个寻找最近公共先人的算法。

而这个算法最奢侈的就是先从一个节点应用哈希表预处理,而后从另外一个节点开始遍历,
找到的第一个在哈希表中呈现的节点就是最近公共先人。

这个算法也有优化空间,而优化后又须要思考各种边界条件,即缓存生效问题。

以上就是本文的全部内容了。大家对此有何认识,欢送给我留言,我有工夫都会一一查看回
答。更多算法套路能够拜访我的 LeetCode 题解仓库
:https://github.com/azl3979858…。目前曾经 40K star 啦。大家也能够关
注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,致力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你
辨认套路,高效刷题。

退出移动版