#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<len;i++){
for(int j=0;j<len;j++){
arr[i][j] = Integer.parseInt(String.valueOf(matrix[i].charAt(j))) ;
}
}

//找出共同路径，返回最后一个共同节点；
List<Integer> Apath = DFS(arr,indexA);
List<Integer> 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<Integer> DFS(int[][] arr, int indexA) {
//分别创建标记数组，栈，动态列表。并用根节点初始化
boolean[] flag=new boolean[arr.length];//访问标记数组
flag[0] = true;
Stack<Integer> stack = new Stack<Integer>();//创建栈对象
stack.push(0);
List<Integer> path = new ArrayList<Integer>();//创建路径列表
path.add(0);
//在栈中查indexA（目标节点）
while(stack.peek() != indexA){//深度遍历
boolean findNext=false;//局部变量标志查找下一个节点
int u = stack.peek();//暂存栈顶对象
for(int j=0;j<arr.length;j++){//查找没有被访问并且相邻的第一个节点元素进栈
if(!flag[j] && arr[u][j] ==1){
u=j;
stack.push(u);
flag[u] = true;
path.add(u);
findNext = true;
break;
}
}

if(!findNext){//如果没有连接的节点
stack.pop();//最后一个元素不是查找的节点元素，则出栈
path.remove(path.size()-1);//列表中删除该元素
}
}
return path;
}

}