小米Git

恋喵大鲤鱼

发布于 2018-08-03 15:23:52

2510

发布于 2018-08-03 15:23:52

题目描述: 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];
    }
};

问题： 上面的实现可以通过上面给定的测试案例。但是在牛客网通不过下面的测试案例。