题目描述:
git是一种分布式代码管理工具,git通过树的形式记录文件的更改历史,比如:
base'<--base<--A<--A'
^
| --- B<--B'
小米工程师常常需要寻找两个分支最近的分割点,即base.假设git 树是多叉树,请实现一个算法,计算git树上任意两点的最近分割点。
(假设git树节点数为n,用邻接矩阵的形式表示git树:字符串数组matrix包含n个字符串,每个字符串由字符'0'或'1'组成,长度为n。matrix[i][j]=='1'当且仅当git树种第i个和第j个节点有连接。节点0为git树的根节点。)
输入例子:
[01011,10100,01000,10000,10000],1,2
输出例子:1
思路:
将输入例子的邻接矩阵画成图,画的比较丑,大家将就着看吧。
0<-1<-2
<-3
<-4
结合题目描述,得出关键信息两点。
1、1节点和2节点的分割点是1->0和2->1->0两条路径的第一个重合点。可以将此题转化为求两条有序链表的公共节点。
2、路径上的节点值一定是单调递减的。
所以我们可以从值较大的节点B出发,依次前往父节点B‘(有且仅有一个,根节点没有),每到达一个父节点就和另一个节点值A进行比较,如果相等,说明找到了分割点,如果B'小于A,则停止当前路径,从A继续出发找父节点。
关于父节点的寻找:设B所在行rowB,从matrix[rowB][rowB-1]开始向左遍历,遇到的第一个1就是父节点的编号。
public int getSplitNode(String[] matrix, int indexA, int indexB) {
if (indexA < 0 || indexB < 0 || matrix == null)
return -1;
if (indexA == indexB)
return indexA;
if (indexA < indexB) {
for (int i = indexB - 1; i >= 0; i--) {
if(matrix[indexB].charAt(i) == '1') {
return getSplitNode(matrix, indexA, i);
}
}
}
return getSplitNode(matrix, indexB, indexA);
}
PS:代码并没有通过牛客网的检查,提示如下,运行错误:请检查是否存在数组越界非法访问,野指针乱访问,空指针乱访问等情况。但我觉得思路应该没什么问题,还请前辈指教。