小米Git

题目描述

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

题目解析

题目的实质是指就是查找树的两个节点的第一个共同祖先。步骤如下：

１. 由邻接矩阵得到各节点的父节点数组
２. 得到两个节点到根节点的路径，翻转路径
３. 从头比较两条路径，最后一个相同的节点就是第一个共同祖先

参考答案

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) {
		vector<bool> used(matrix.size(), false);
		vector<int> node_parent(matrix.size(),-1);
	
		queue<int> nums;
		nums.push(0);
		node_parent[0] = -1;
		used[0] = true;
	
		while (!nums.empty())
		{
			int size = nums.size();
	
			for (int i = 0; i < size; ++i)
			{
				int n = nums.front(); nums.pop();
				
				for (int j = 0; j < matrix[n].size(); ++j)
				{
					if (matrix[n][j] == '1' && !used[j])
					{
						node_parent[j] = n;
						used[j] = true;
						nums.push(j);
					}
				}
			}
		}
	
		vector<int> va;
		vector<int> vb;
		
		while (indexA != -1)
		{		
			va.push_back(indexA);
			indexA = node_parent[indexA];
		}
		
		while (indexB != -1)
		{
			vb.push_back(indexB);
			indexB = node_parent[indexB];
		}
	
		reverse(va.begin(),va.end());
		reverse(vb.begin(), vb.end());
	
		int idx = 0;
		for (int i = 0; i < min(va.size(), vb.size()) ; ++i)
		{
			if(va[i] == vb[i])
				idx = va[i];
			else 
				break;
		}
		return idx;
	}    
};