Jiajie Zhuo

题目：

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

分析：

1. 分别倒序寻找两个节点与根结点（0节点）的连通路。
2. 将两条通路进行匹配，寻找最近的分割点（两条通路中第一个相同的点）。

算法代码：

int findClosestSeperatingPoint(char **GitTree, int n, int pointA, int pointB)
{
    int closestSeperatingPoint = 0;
    
    int Ai, Aj, Bi, Bj;
    Ai = Aj = pointA;
    Bi = Bj = pointB;
    
    int *pathA = new int[n];
    int *pathB = new int[n];
    
    int pathLenOfA, pathLenOfB;
    
    //find the path of A
    findPath(GitTree, pathA, pathLenOfA, pointA);
    
    //find the path of B
    findPath(GitTree, pathB, pathLenOfB, pointB);

    //find the closest seperating point
    closestSeperatingPoint = match(pathA, pathB, pathLenOfA, pathLenOfB);
    
    delete [] pathA;
    delete [] pathB;
    
    return closestSeperatingPoint;
}

void findPath(char **GitTree, int *path, int & pathLen, int point)
{
    int i, j;
    i = j = point;
    
    pathLen = 1;
    path[pathLen-1] = point;

    while (0 != i) {
        while ('1' != GitTree[i][j]) {
            j--;
        }
        
        pathLen++;
        path[pathLen-1] = j;
        
        i = j;
    }
}

int match(int pathA[], int pathB[], int pathLenOfA, int pathLenOfB)
{
    for (int i = 0; i < pathLenOfA; ++i) {
        for (int j = 0; j < pathLenOfB; ++j) {
            if (pathA[i] == pathB[j]) {
                return pathA[i];
            }
        }
    }
    
    return 0;
}

中间将寻找与根结点的通路代码和匹配两条通路的最近分割点代码封装起来了。

测试代码：

//
//  main.cpp
//  findClosestSeperatingPoint
//
//  Created by Jiajie Zhuo on 2017/4/2.
//  Copyright © 2017年 Jiajie Zhuo. All rights reserved.
//

#include <iostream>

using namespace std;

int findClosestSeperatingPoint(char **GitTree, int n, int pointA, int pointB);
void findPath(char **GitTree, int *path, int & pathLen, int point);
int match(int pathA[], int pathB[], int pathLenOfA, int pathLenOfB);

int main(int argc, const char * argv[]) {
    int n, pointA, pointB, closestSeperatingPoint;
    
    cout << "Please enter the nubmer of point: ";
    cin >> n;
    
    char **GitTree = new char*[n];
    
    cout << "Please enter the matrix of GitTree:" << endl;
    for (int i = 0; i < n; i++) {
        GitTree[i] = new char[n];
        for (int j = 0; j < n; j++) {
            cin >> GitTree[i][j];
        }
    }
    
    cout << "Please enter the two point A and B: ";
    cin >> pointA >> pointB;
    
    closestSeperatingPoint = findClosestSeperatingPoint(GitTree, n, pointA, pointB);
    
    cout << "The closestSeperatingPoint is " << closestSeperatingPoint << endl;
    
    for (int i = 0; i < n; ++i) {
        delete [] GitTree[i];
    }
    delete [] GitTree;
    
    return 0;
}

注：这里已知git树的节点数。

改进：

其中的path可以使用vector，添加元素和匹配时都会方便很多。

因为path中的元素都是倒序排列的，所以最后的match()匹配方法增加效率。

总结：