小米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

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];
    }
};

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

同一个节点的最近分割点不就是自己吗?但是牛客网给的答案却不是。请知道的网友留言解答,谢谢。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

关于使用lazytag的线段树两种查询方式的比较研究

说到线段树,想来大家并不陌生——最基本的思路就是将其规划成块,然后只要每次修改时维护一下即可。 但是尤其是涉及到区间修改时,lazytag的使用往往能够对于程序...

3187
来自专栏大数据挖掘DT机器学习

文本分类中语料库的获取——搜狗语料库

这次主要总结搜过语料库的获取,因为老师要求20万数据,而我自己只爬了2万多,所以用到了搜狗的语料库. ? 在这个页面中,我选择的是一个月的数据,别小看一个月...

6588
来自专栏小鹏的专栏

windows下C++如何调用matlab程序

实验平台:    matlab R2016b   VS2013 思路: 1. 设置matlab的编译器,使用外部的VC或者gcc等编译器。 2. 编译m文件成d...

2249
来自专栏DOTNET

ASP.NET MVC编程——模型

1 ViewModel 是一种专门提供给View使用的模型,使用ViewModel的理由是实体或领域模型所包含的属性比View使用的多或少,这种情况下实体或领域...

3308
来自专栏用户画像

Python 使用正则表达式进行MongoDB条件查询

db.VideoProfile.find( {_id: { $regex: /^1_[0-9]{5,}$/} } ).count()

902
来自专栏机器学习从入门到成神

Pandas使用DataFrame进行数据分析比赛进阶之路(二):日期数据处理:按日期筛选、显示及统计数据

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

5451
来自专栏惨绿少年

Shell编程基础篇-下

1.1 条件表达式 1.1.1 文件判断 常用文件测试操作符 常用文件测试操作符 说明 -d文件,d的全拼为directory 文...

1870
来自专栏十月梦想

php代码之网站显示安全运行时间代码

上述就可实现网站计时功能,结合数组函数实现,后续可是使用js获取倒计时,时时显示!

1142
来自专栏Aloys的开发之路

一个比较全面的java随机数据生成工具包

        最近,由于一个项目的原因需要使用一些随机数据做测试,于是写了一个随机数据生成工具,ExtraRanom。可以看成是Java官方Random类的扩...

2629
来自专栏java系列博客

深入理解Java内存模型(七)——总结

1633

扫码关注云+社区