首页 > 试题广场 >

小米Git

[编程题]小米Git
  • 热度指数:3956 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
Git 是一个常用的分布式代码管理工具,Git 通过树的形式记录文件的更改历史(例如示例图),树上的每个节点表示一个版本分支,工程师经常需要找到两个分支的最近的分割点。
例如示例图中 3,4 版本的分割点是 1。3,5 版本的分割点是 0。
给定一个用邻接矩阵 matrix 表示的树,请你找到版本 versionA 和 versionB 最近的分割点并返回编号。

注意:
1.矩阵中从第一行 (视为节点 0 )开始,表示与其他每个点的连接情况,例如 [01011,10100,01000,10000,10000] 表示节点 0 与节点 1 , 3 , 4相连,节点 1 与节点 0 , 2相连,其他点的以此类推。
2.并不保证是一棵二叉树,即一个节点有可能有多个后继节点,我们把节点 0 视为树的根节点。

数据范围:树上节点数量满足
示例图

示例1

输入

["01011","10100","01000","10000","10000"],1,2

输出

1
示例2

输入

["0"],0,0

输出

0
头像 zcr214
发表于 2021-12-16 17:26:37
本质上是一个求最近公共祖先的问题,关键要解决的问题是把输入转换成一个树形结构,这里仍然是用字典来存储: 针对给定的样例["01011","10100","01000","10000","10000"],1,2 以当前节点为key,关联节点为value列表,可以转换为: { 0:[1,3,4], 1: 展开全文
头像 牛客517057172号
发表于 2022-08-25 18:20:18
思路: 1、迭代创建节点字典,记录下所在父级节点、距离根节点的步数 2、比较输入的节点,分类操作:     相同,则直接返回;     互为父子,则直接返回父;     若无关联,选择距离远的节点,向上走一步, 展开全文
头像 攸宁biu
发表于 2022-03-18 19:35:58
使用数组记录节点的父子关系,转换为基本的求最近公共祖先的问题 /** * @param matrix string字符串一维数组 * @param versionA int整型 * @param versionB int整型 * @return int整型 */ function G 展开全文
头像 醒了不起的盖茨比0.0
发表于 2022-08-11 14:56:31
import java.util.*; public class Solution {          public void dfs(int  展开全文
头像 echofa
发表于 2022-04-05 21:12:15
直接用邻接矩阵解公共节点可能不容易,如果能转化成树的形式会方便很多: 用BFS构造map树结构; 用DFS遍历map,找到两个path表示versionA和versionB的路径,遍历path,第一个不相等的就是最近公共节点 class Solution { public: bool c 展开全文
头像 牛客692857968号
发表于 2022-01-14 17:56:21
class Solution { //树是特殊的图 采用递归思想 找子孙节点 // 参考 https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/ pri 展开全文
头像 bug_making()
发表于 2022-05-05 20:47:55
这个题目主要考察的是层序遍历写法,确定父节点就好了 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix string字符串ve 展开全文
头像 贪吃的迪恩顶呱呱
发表于 2024-04-28 18:20:21
1、使用BFS构建树2、使用DFS搜索树并得到两个节点各自的路径3、对比路径找到最后一个公共祖先 #include <queue> #include <unordered_map> #include <unordered_set> #include <vec 展开全文
头像 张白白zzz
发表于 2024-05-30 23:37:30
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix string字符串一维数组 展开全文
头像 牛客520451666号
发表于 2022-01-12 02:03:20
/** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 @param matrix string字符串一维数组 @param versionA int整型 @param versionB int整型 @return int整型 / /* 本来粗略读题应该就是转换为两个 展开全文