小米Git

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix string字符串一维数组 
# @param versionA int整型 
# @param versionB int整型 
# @return int整型
#
class Solution:
    def Git(self , matrix: List[str], versionA: int, versionB: int) -> int:
        # 第一步：创建字典，记录父级及到根节点的距离
        dictMat = {}
        i = 0
        while i < len(matrix):
            beforeLen =  len(dictMat.keys())
            if i == 0 and not dictMat.__contains__(i):
                dictMat[i] = {
                    'parent': 0,
                    'times': 0
                }
            for j in range(0, len(matrix[i])):
                if matrix[i][j] == '1' and not dictMat.__contains__(j) and dictMat.__contains__(i):
                    dictMat[j] = {
                        'parent': i,
                        'times': dictMat[i]['times'] + 1
                    }
            # 有修改则重复
            if beforeLen != len(dictMat.keys()):
                i = 0
            else:
                i += 1
        
        # 第二步：分类循环比较
        while True:
            # 0 开头
            if versionA == 0&nbs***bsp;versionB == 0:
                return 0
            # 相同位置
            elif versionA == versionB:
                return versionA
            # 相同父级
            if dictMat[versionA]['parent'] == dictMat[versionB]['parent']:
                return dictMat[versionA]['parent']
            # 互为父子
            elif dictMat[versionA]['parent'] == versionB:
                return versionB
            elif dictMat[versionB]['parent'] == versionA:
                return versionA
            else:
            # 距离根节点远的向上爬
                if dictMat[versionA]['times'] > dictMat[versionB]['times']:
                    versionA = dictMat[versionA]['parent']
                else:
                    versionB = dictMat[versionB]['parent']