小米Git

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串vector 
     * @param versionA int整型 
     * @param versionB int整型 
     * @return int整型
     */
    vector<int> visited;
    int Git(vector<string>& matrix, int versionA, int versionB) {
        // write code here
        //节点数
        visited.resize(n, 0);
        return traverse(matrix, versionA, versionB, 0);
    }
    int traverse(vector<string>& matrix, int versionA, int versionB, int index) {
        if(index == versionA || index == versionB)
            return index;
        visited[index] = 1; //不走回头路
        vector<int> count;
        for(int i = 0; i < matrix.size(); i++) {
            if(matrix[index][i] == '1' && visited[i] == 0)  //遍历子节点
            {
                int temp = traverse(matrix, versionA, versionB, i);
                if(temp != -1)  //说明目标在此子节点中
                    count.push_back(temp);
                if(count.size() > 1) break;
            }
        }
        if(count.size() == 0) //没找到
            return -1;
        if(count.size() == 1)  // 说明位于一边或此分支上只有A/B
            return count[0];
        return index;  //两个值说明A、B位于当前节点两边
    }
};

class Solution {
public:
    int getLCA(vector<vector<int>>& tables, int index, vector<bool>& record, int a, int b) {
        if (index == a || index == b) {
            return index;
        }
        //检查每一条子树上面是否找到a或者b
        vector<int> lcas;
        for (const auto& num : tables[index]) {
            if (!record[num]) {
                record[num] = true;
                int lca = getLCA(tables, num, record, a, b);
                if (lca != -1) {
                    lcas.push_back(lca);
                }
            }
        }
        //找到a或者b
        if (lcas.size() == 1) {
            return lcas[0];
        }
        //找到了a和b
        else if (lcas.size() == 2) {
            return index;
        }
        //没有找到a或者b
        return -1;
    }
    
    int Git(vector<string>& m, int a, int b) {
        if (a == b) {
            return a;
        }
        vector<vector<int>> tables(m.size(), vector<int>());
        for (int i = 0; i < m.size(); i++) {
            for (int j = 0; j < m[i].size(); j++) {
                if (m[i][j] == '1') {
                    tables[i].push_back(j);
                }
            }
        }
        vector<bool> record(m.size(), false); 
        return getLCA(tables, 0, record, a, b);
    }
};

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix string字符串一维数组
     * @param versionA int整型
     * @param versionB int整型
     * @return int整型
     */

    private List<Integer> alist; // 用来保存 a 的路径
    private List<Integer> blist; // 用来保存 b 的路径
    private Map<Integer, List<Integer>> tree; // 用来保存整理为字典的树形结构

    public int Git (String[] matrix, int versionA, int versionB) {
        // write code here
        alist = new ArrayList<Integer>();
        blist = new ArrayList<Integer>();
        tree = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < matrix.length; i++) {
            tree.put(i, new ArrayList<Integer>());
            char[] relation = matrix[i].toCharArray();
            for (int j = 0; j < relation.length; j++) {
                if (relation[j] == '1') {
                    tree.get(i).add(j);
                }
            }
        }
        walk(new ArrayList<Integer>(), 0, 0,versionA,versionB);
        int res = 0;
        while (!alist.isEmpty() &&
                !blist.isEmpty()) { // 逐个弹出首位比较，直到不相同或者路径为空
            int a = alist.remove(0);
            int b = blist.remove(0);
            if (a == b) {
                res = a;
            } else {
                break;
            }
        }
        return res;
    }

    private void walk(List<Integer> tmplist, int pre, int node,int versionA,int versionB) {
        tmplist.add(node);
        if (node == versionA) { // 找到 a，保存路径
            alist = new ArrayList<Integer>(tmplist);
        }
        if (node == versionB) { // 找到 b，保存路径，注意这里 a 和 b 可能是同一个值，所以不要用 else
            blist = new ArrayList<Integer>(tmplist);
        }
        for (int i : tree.get(node)) { // 遍历执行下级节点
            if (i == pre) { // 注意跳过来时的节点
                continue;
            }
            walk(tmplist, node, i,versionA,versionB);
            tmplist.remove(tmplist.size() - 1);
        }
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串一维数组 
     * @param versionA int整型 
     * @param versionB int整型 
     * @return int整型
     */
    public int Git (String[] matrix, int versionA, int versionB) {
        int n = matrix.length;
        int[] arr = new int[n];
        Arrays.fill(arr, -1);
        arr[0] = 0;
        getParent(matrix, n, 0, arr);
        ArrayList<Integer> list1 = dfs(arr, versionA, new ArrayList<>());
        ArrayList<Integer> list2 = dfs(arr, versionB, new ArrayList<>());
        for (int i : list1) {
            for (int j : list2) {
                if (i == j) {
                    return i;
                }
            }
        }
        return 0;
    }

    // 获取父节点数组arr
    public void getParent(String[] matrix, int n, int parent, int[] arr) {
        String s = matrix[parent];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1' && arr[i] == -1) {
                arr[i] = parent;
                getParent(matrix, n, i, arr);
            }
        }
    }

    // 获取目标版本从父节点到根节点的列表
    public ArrayList<Integer> dfs(int[] arr, int target, ArrayList<Integer> list) {
        list.add(target);
        if (target != 0) {
            dfs(arr, arr[target], list);
        }
        return list;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串一维数组 
     * @param versionA int整型 
     * @param versionB int整型 
     * @return int整型
     */
    public int Git (String[] matrix, int versionA, int versionB) {
        // write code here
        int n = matrix.length;
        int[] parent = new int[n];
        parent[0] = -1;
        boolean[] used = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size -- > 0) {
                int father = queue.poll();
                used[father] = true;
                char[] sons = matrix[father].toCharArray();
                for (int i = 0; i < n; i ++) {
                    if (sons[i] == '1' && !used[i]) {
                        parent[i] = father;
                        queue.offer(i);
                    }
                }
            }
        }
        List<Integer> listA = new ArrayList<>();
        List<Integer> listB = new ArrayList<>();
        findPath(parent, listA, versionA);
        findPath(parent, listB, versionB);
        int res = 0;
        int sizeA = listA.size();
        int sizeB = listB.size();
        while (sizeA > 0 && sizeB > 0) {
            int a = listA.get(sizeA - 1);
            int b = listB.get(sizeB - 1);
            sizeA --; sizeB -- ;
            if (a == b) res = a;
            else break;
        }
        return res;
    }

    void findPath(int[] parent, List<Integer> list, int version) {
        list.add(version);
        if (parent[version] == -1) return;
        findPath(parent, list, parent[version]);
    }
}
总之确定每个节点的父节点就行了，父节点是唯一的

class Solution {
    
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串vector 
     * @param versionA int整型 
     * @param versionB int整型 
     * @return int整型
     */
    int Git(vector<string>& matrix, int versionA, int versionB) {
        // write code here
        return dfs(matrix, 0, versionA, versionB);
    }
    int dfs(vector<string>& matrix, int index, int versionA, int versionB){
        if(index == versionA || index == versionB)
            return index;
        vector<int> find(matrix.size(),-1);
        string childs = matrix[index];
        for(int i=0; i< childs.size();i++){
            if(childs[i] == '1' ){
                matrix[i][index] = '0';
                int val = dfs(matrix, i, versionA, versionB);
                find[i] = val;
            }
        }
        int count = 0;
        int id = -1;
        for(int i=0; i< find.size(); i++){
            if(find[i] >= 0){
                count++;
                id = i;
            }  
        }
        if(count == 2)
            return index;
        else if(count == 1)
            return find[id];

        return -1;
    }
};

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @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']

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串一维数组 
     * @param versionA int整型 
     * @param versionB int整型 
     * @return int整型
     */
    
    // 构建树，多叉树的最近公共祖先
    class TreeNode {
        int val;
        LinkedHashSet<TreeNode> next;

        public TreeNode(int val) {
            this.val = val;
            next = null;
        }
    }

    public int Git(String[] matrix, int versionA, int versionB) {
        // write code here
        if (versionA == versionB) return versionA;
        TreeNode root = treeify(matrix);

        return lowestCommonAncestor(root, versionA, versionB);
    }

    private int lowestCommonAncestor(TreeNode root, int versionA, int versionB) {
        if (root == null) return -1;
        if (root.val == versionA || root.val == versionB) return root.val;
        int size = root.next == null ? 0 : root.next.size();
        if (size == 0) return -1;
        int[] res = new int[size];
        Arrays.fill(res, -1);
        Iterator<TreeNode> iterator = root.next.iterator();
        for (int i = 0; i < size; i++) {
            res[i] = lowestCommonAncestor(iterator.next(), versionA, versionB);
        }
        int sum = 0;
        int oneSide = -1;
        for (int a : res) {
            sum += a == -1 ? 0 : 1;
            if (a != -1)
                oneSide = a;
        }
        if (sum == 2) return root.val;
        return oneSide;
    }

    private TreeNode treeify(String[] matrix) {
        Map<Integer, TreeNode> map = new HashMap<>();
        for (int i = 0; i < matrix.length; i++) {
            map.put(i, new TreeNode(i));
        }
        for (int i = 0; i < matrix.length; i++) {
            String s = matrix[i];
            TreeNode node = map.get(i);
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == '1') {
                    if (node.next == null) {
                        node.next = new LinkedHashSet<>();
                    }
                    node.next.add(map.get(j));
                }
            }
        }
        // 去重
        Queue<TreeNode> queue = new ArrayDeque<>();
        Map<TreeNode, Boolean> visited = new HashMap<>();
        queue.add(map.get(0));
        visited.put(map.get(0), true);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                visited.put(node, true);
                if (node != null && node.next != null) {
                    for (TreeNode n : node.next) {
                        n.next.remove(node);
                        if (!visited.getOrDefault(n, false)) {
                            queue.offer(n);
                        }
                    }
                }
            }
        }
        return map.get(0);
    }


}

• DFS记忆集深搜记录根到节点的路径。
• 将其中一个路径取反，并从头开始取节点判断另一路径是否存有该节点即可。

import java.util.*;


public class Solution {
    //邻接表方式存储图 
    HashMap<Integer,Node> nodes = new HashMap<>();
    List<Node> resultA;
    List<Node> resultB;
    boolean scuess = false;
    class Node{
        List<Node> nexts = new ArrayList<>();
        int id;
        public Node(int id){
            this.id = id;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串一维数组 
     * @param versionA int整型 
     * @param versionB int整型 
     * @return int整型
     */
    public int Git (String[] matrix, int versionA, int versionB) {
        // write code here
        for(int i = 0; i < matrix.length; i++){
            if(!nodes.containsKey(i)){
                nodes.put(i, new Node(i));
            }
            Node cur = nodes.get(i);
            for(int j = 0; j < matrix[0].length(); j++){
                if(matrix[i].charAt(j) == '1'){
                    if(!nodes.containsKey(j)){
                        nodes.put(j, new Node(j));
                    }
                    cur.nexts.add(nodes.get(j));
                }
            }
        }
        getPath(0, versionA, new ArrayList<>(), new boolean[matrix.length]);
        scuess = false;
        getPath(0, versionB, new ArrayList<>(), new boolean[matrix.length]);

        Collections.reverse(resultA);
        for(Node node : resultA){
            if(resultB.contains(node)){
                return node.id;
            }
        }
        return 0;
    }

    private void getPath(int cur, int target, List<Node> list, boolean[] used){
        if(cur == target){
            list.add(nodes.get(cur));
            if(resultA == null) resultA = new ArrayList<>(list);
            else resultB = new ArrayList<>(list);
            scuess = true;
            return;
        }else{
            Node node = nodes.get(cur);
            list.add(node);
            used[cur] = true;
            for(Node next : node.nexts){
                if(!used[next.id] && !scuess)
                    getPath(next.id, target, list, used);
            }
            if(scuess) return;
            used[cur] = false;
            list.remove(list.size() - 1);
        }
    }
}

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
}