首页 > 代码库 > 小米Git
小米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
思路：刚开始看题没怎么看懂，后来结合别人的理解才明白。 首先说明一点，题目是求树上任意两点的最近分割点。会想到什么？这是一棵什么树，如果看过剑指offer的题的话，会想到有一道这样的题目：求树中两个节点的最低公共祖先，看起来很像。可是仔细研究后会发现，那里的题目中给的是树的链接形式，而这里给出的是邻接矩阵。在那道题目中，如果二叉树为普通的树，思路是先要分别求出两个节点到根节点的路径，然后将问题转化为两个链表的第一个公共节点，这样问题就容易解决了。所以，我们要考虑将邻接矩阵转化，可以转化为一个父亲节点的数组，每个索引值对应的位置存放着这个节点的父节点的索引值。然后我们可以根据这个父节点数组来进行遍历，找出两个节点到根节点的路径。其中，有一个问题，就是将邻接矩阵转化为父亲节点的数组时，可以用一个队列，类似于层序遍历的思想，将每个节点的父节点都找出来。这样的话，在找出两条路径后，就可以采用求两个链表的第一个公共节点的方法求。
需要注意的一点是，在利用堆栈判断两个路径元素时，一定将判断堆栈是否为空的条件写在前面，写在后面的话，会先判断栈顶元素，导致程序直接崩溃。
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; } if (indexA * indexB == 0){ // 若有一个节点为根节点，返回根节点 return 0; } int n = matrix.size(); // 节点的个数 vector<int> father(n,0); // 初始化father数组，存放每个结点的父节点 vector<int> flag(n); // 标志向量 father[0] = -1; // 根节点的父节点为-1 flag[0] = 1; // 根节点已经访问过 queue<int> children; // 用来层次遍历整个树 children.push(0); // 压入根节点 // 构造father 数组，从根节点开始,利用层次遍历的思想 while (!children.empty()){ int parent = children.front(); // 当前的节点 children.pop(); // 弹出当前节点 for (int i = 0; i < (matrix[parent].size()); i++){ // 遍历当前节点的下一层 if (flag[i] != 1 && matrix[parent][i] == ‘1‘){ //若与当前节点连接并且还没被访问过 father[i] = parent; // children.push(i); flag[i] = 1; } } } int ia = indexA; int ib = indexB; // 记录从根节点到a, b节点的路径 stack<int> pathtoA; stack<int> pathtoB; while (ia != -1){ pathtoA.push(ia); ia = father[ia]; } while (ib != -1){ pathtoB.push(ib); ib = father[ib]; } int tmp = 0; while ( !pathtoA.empty() && !pathtoB.empty() && pathtoA.top() == pathtoB.top()){ // 这个判断的条件尤其注意顺序 tmp = pathtoA.top(); pathtoA.pop(); pathtoB.pop(); } return tmp; } };
小米Git