题目描述: 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
git树: 根据上面的输入,可以很容易构造出如下git树:
解题思路: (1)分别求出给定节点的前驱节点,一直找到根节点0为止。这里有个约定就是节点的前驱节点下标是小于当前节点的,这是我的理解,不知道有没有错误。因此,节点2的前驱节点(包括自己)分别为[2,1,0],节点1的前驱节点分别为[1,0]。
(2)求出两个节点的前驱节点的第一个公共节点,就是要求的两点的最近分割点。比如[2,1,0]和[1,0]的第一个公共节点就是1。这里有点类似于求两个链表的第一个公共节点。
实现代码:
class Solution {
public:
/**
* 返回git树上两点的最近分割点
*
* @param matrix 接邻矩阵,表示git树,matrix[i][j] == '1' 当且仅当git树中第i个和第j个节点有连接,节点0为git树的跟节点
* @param indexA 节点A的index
* @param indexB 节点B的index
* @return 整型
*/
int getSplitNode(vector<string> matrix, int indexA, int indexB) {
if(indexA==indexB)
return indexA;
int nodeNum=matrix.size();
vector<int> indexAForwardNode;
vector<int> indexBForwardNode;
//查找节点A的前驱节点
int nearestForwardNodeA=indexA;
while(nearestForwardNodeA>=0){
indexAForwardNode.push_back(nearestForwardNodeA);
int i=nearestForwardNodeA-1;
for(;i>=0;--i){
if(matrix[nearestForwardNodeA][i]=='1'){
nearestForwardNodeA=i;
break;
}
}
if(i==-1)//已经找到了根节点
break;
}
//查找节点B的前驱节点
int nearestForwardNodeB=indexB;
while(nearestForwardNodeB>=0){
indexBForwardNode.push_back(nearestForwardNodeB);
int i=nearestForwardNodeB-1;
for(;i>=0;--i){
if(matrix[nearestForwardNodeB][i]=='1'){
nearestForwardNodeB=i;
break;
}
}
if(i==-1)//已经找到了根节点
break;
}
//寻找最近f分割点
stack<int> stackForwordNodeA;
stack<int> stackForwordNodeB;
for(int i=0;i<indexAForwardNode.size();++i)
stackForwordNodeA.push(indexAForwardNode[i]);
for(int i=0;i<indexBForwardNode.size();++i)
stackForwordNodeB.push(indexBForwardNode[i]);
int commonIndex=stackForwordNodeA.size();
while(stackForwordNodeA.top()==stackForwordNodeB.top()){
stackForwordNodeA.pop();
stackForwordNodeB.pop();
--commonIndex;
if(stackForwordNodeA.empty()||stackForwordNodeB.empty())
break;
}
return indexAForwardNode[commonIndex];
}
};
问题: 上面的实现可以通过上面给定的测试案例。但是在牛客网通不过下面的测试案例。
同一个节点的最近分割点不就是自己吗?但是牛客网给的答案却不是。请知道的网友留言解答,谢谢。