计算git树上任意两点的最近分割点。

红太狼 2022-08-04 00:59 12阅读 0赞

1.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树的根节点。）

#include<vector>
    #include<string>
    #include<iostream>
    using namespace std;
    int getSplitNode(vector<string> matrix, int indexA, int indexB) {
    	
    	int m = matrix.size();
    	vector<vector<int>> fu(m);
    	for (int i = 0; i < m; i++)
    		for (int j = i+1; j < m; j++)
    		{
    			if (matrix[i][j] == '1')
    				fu[i].push_back(j);
    		}
    	vector<int> a;
    	vector<int> b;
    	int t1 = 0;
    	a.push_back(indexA);
    
    	int t2 = 0;
    	b.push_back(indexB);
    	while (indexA != 0){
    		for (int i = 0; i < fu.size(); i++)
    		{
    			for (int j = 0; j < fu[i].size(); j++){
    				if (fu[i][j] == indexA)
    				{
    					a.push_back(i);
    					indexA = i;
    					break;
    				}
    			}
    			if (indexA == 0)
    				break;
    		}
    	}
    	
    	while (indexB > 0){
    		for (int i = 0; i < fu.size(); i++){
    			for (int j = 0; j < fu[i].size(); j++){
    				if (fu[i][j] == indexB)
    				{
    					b.push_back(i);
    					indexB = i;
    					break;
    				}
    			}
    			if (indexB == 0)
    				break;
    		}
    	}
    	t1 = a.size();
    	t2 = b.size();
    	t1--;
    	t2--;
    	while (a[t1] == b[t2]){
    		
    		t1--;
    		t2--;
    		if (t1 < 0 || t2 < 0)
    			break;
    	}
    	return a[++t1];
    
    }
    int main()
    {
    	vector<string> matrix = { "011001", "100010", "100100", "001000", "010000","100000" };
    	/*matrix[0] = "01011";
    	matrix[1] = "10100";
    	matrix[2] = "01000";
    	matrix[3] = "10000";
    	matrix[4] = "10000";*/
    	cout << getSplitNode(matrix, 5, 3) << endl;
    	getchar();
    }