#yyds干货盘点# 解决名企真题：小米Git

#yyds干货盘点# 解决名企真题：小米Git

1.简述：

描述

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

2.代码实现：

import java.util.*;import java.util.ArrayList;import java.util.List;import java.util.Stack;public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix string字符串一维数组 * @param versionA int整型 * @param versionB int整型 * @return int整型 */ public static int Git(String[] matrix, int indexA, int indexB) { //如果查找节点相同，返回该节点本身。 if(indexA==indexB){ return indexA; } //如果查找的节点不相等，执行以下操作 int tmp=0; int len=matrix.length; int[][] arr = new int[len][len]; //转化为二维数组 for(int i=0;i Apath = DFS(arr,indexA); List Bpath=DFS(arr,indexB); int plen=Apath.size()>Bpath.size()?Bpath.size():Apath.size(); for (int i = 0; i < plen; i++) { if(Apath.get(i)==Bpath.get(i)) { tmp= Apath.get(i);//记录共同节点的值，并返回 } } return tmp; } //深度优先遍历，并返回到indexA的节点列表 private static List DFS(int[][] arr, int indexA) { //分别创建标记数组，栈，动态列表。并用根节点初始化 boolean[] flag=new boolean[arr.length];//访问标记数组 flag[0] = true; Stack stack = new Stack();//创建栈对象 stack.push(0); List path = new ArrayList();//创建路径列表 path.add(0); //在栈中查indexA（目标节点） while(stack.peek() != indexA){//深度遍历 boolean findNext=false;//局部变量标志查找下一个节点 int u = stack.peek();//暂存栈顶对象 for(int j=0;j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。