小米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的使用往往能够对于程序...

33370
来自专栏跟着阿笨一起玩NET

T4模板语法

T4,即4个T开头的英文字母组合:Text Template Transformation Toolkit。

17310
来自专栏用户画像

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

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

10620
来自专栏决胜机器学习

有趣的算法(四)——一致性Hash算法模拟redis集群

有趣的算法(四)——一致性Hash算法模拟redis集群 (原创内容,转载请注明来源,谢谢) 一、概述 redis的集群,对key存储在哪个服务器的问题上,采...

40470
来自专栏java系列博客

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

17830
来自专栏Ceph对象存储方案

简谈RGW的index shard计算

在RGW里面每个存储到rados的Object都需要先计算出对应元数据存储的shard number,之后再将元数据信息更新到shard number对应的Ob...

30660
来自专栏用户画像

H5 新增的input元素的类型

search类型用于搜索域,如站点搜索或Google搜索。search域显示为常规的文本域。

7730
来自专栏about云

日志分析实战之清洗日志小实例7:查看样本数据,保存统计数据到文件

问题导读 1.如何从所有数据中,抽取样本查看? 2.如何保存结果到hdfs? 3.saveAsTextFile的作用是什么? 上一篇 日志分析实战之清洗...

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

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

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

1.1K10
来自专栏惨绿少年

Shell编程基础篇-下

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

20600

扫码关注云+社区

领取腾讯云代金券