小米Git

[编程题]小米Git

热度指数：3621 时间限制：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 \le n \le 100 \$

示例图

示例1

输入

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

输出

示例2

输入

["0"],0,0

输出

算法知识视频讲解

zcr214

发表于 2021-12-16 17:26:37

本质上是一个求最近公共祖先的问题，关键要解决的问题是把输入转换成一个树形结构，这里仍然是用字典来存储：针对给定的样例["01011","10100","01000","10000","10000"],1,2 以当前节点为key，关联节点为value列表，可以转换为： { 0:[1,3,4], 1: 展开全文

攸宁biu

发表于 2022-03-18 19:35:58

使用数组记录节点的父子关系，转换为基本的求最近公共祖先的问题 /** * @param matrix string字符串一维数组 * @param versionA int整型 * @param versionB int整型 * @return int整型 */ function G 展开全文

牛客517057172号

发表于 2022-08-25 18:20:18

思路： 1、迭代创建节点字典，记录下所在父级节点、距离根节点的步数 2、比较输入的节点，分类操作：相同，则直接返回；互为父子，则直接返回父；若无关联，选择距离远的节点，向上走一步，展开全文

醒了不起的盖茨比0.0

发表于 2022-08-11 14:56:31

import java.util.*; public class Solution { public void dfs(int 展开全文

牛客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 展开全文

echofa

发表于 2022-04-05 21:12:15

直接用邻接矩阵解公共节点可能不容易，如果能转化成树的形式会方便很多：用BFS构造map树结构；用DFS遍历map，找到两个path表示versionA和versionB的路径，遍历path，第一个不相等的就是最近公共节点 class Solution { public: bool c 展开全文

bug_making()

发表于 2022-05-05 20:47:55

这个题目主要考察的是层序遍历写法，确定父节点就好了 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix string字符串ve 展开全文

牛客520451666号

发表于 2022-01-12 02:03:20

/** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 @param matrix string字符串一维数组 @param versionA int整型 @param versionB int整型 @return int整型 / /* 本来粗略读题应该就是转换为两个展开全文