小米Git

[编程题]小米Git

热度指数：3956 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

Git 是一个常用的分布式代码管理工具，Git 通过树的形式记录文件的更改历史（例如示例图），树上的每个节点表示一个版本分支，工程师经常需要找到两个分支的最近的分割点。

例如示例图中 3,4 版本的分割点是 1。3,5 版本的分割点是 0。

给定一个用邻接矩阵 matrix 表示的树，请你找到版本 versionA 和 versionB 最近的分割点并返回编号。

注意：

1.矩阵中从第一行（视为节点 0 ）开始，表示与其他每个点的连接情况，例如 [01011,10100,01000,10000,10000] 表示节点 0 与节点 1 ， 3 ， 4相连，节点 1 与节点 0 ， 2相连，其他点的以此类推。

2.并不保证是一棵二叉树，即一个节点有可能有多个后继节点，我们把节点 0 视为树的根节点。

数据范围：树上节点数量满足 $1 \le n \le 100 \$

示例图

示例1

输入

["01011","10100","01000","10000","10000"],1,2

输出

示例2

输入

["0"],0,0

输出

算法知识视频讲解

.晚安

package main

func Git(matrix []string, versionA, versionB int) int {
    return f(matrix, versionA, versionB, 0, make([]bool, len(matrix)))
}

func f(matrix []string, versionA, versionB, n int, visited []bool) int {
    if n == versionA || n == versionB {
        return n
    }
    visited[n] = true
    a := -1
    for i, c := range matrix[n] {
        if c == '0' || visited[i] {
            continue
        }
        if b := f(matrix, versionA, versionB, i, visited); b >= 0 {
            if a >= 0 {
                return n
            }
            a = b
        }
    }
    return a
}

发表于 2022-02-10 17:24:31 回复(0)