首页 > 试题广场 >

小米Git

[编程题]小米Git
  • 热度指数:3523 时间限制: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

输入

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

输出

1
示例2

输入

["0"],0,0

输出

0
这个题的思路还是很简单的:
  1. 建立一个子节点指向父节点的有向图,图结构用邻接表存储;
  2. 根据版本编号versionA和versionB从图中取出从versionA节点和versionB节点出发到根节点的单链表;
  3. 求出两个单链表的第一个公共节点。
主要的难点在于建图,因为给出的邻接矩阵无法直接确定边的方向,只能先建立无向图的邻接表,然后根据根节点为0的这个信息,自顶向下地把父节点指向子节点的边给删除掉,得到有向图的邻接表。
import java.util.*;

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

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;
        if(n == 1){
            return 0;
        }
        // 构建子节点指向父节点的图
        // 先建立无向图
        HashMap<Integer, TreeSet<Integer>> graph = new HashMap<>();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i].charAt(j) == '1'){
                    if(graph.containsKey(i)){
                        graph.get(i).add(j);
                    }else{
                        TreeSet<Integer> neighbors = new TreeSet<>();
                        neighbors.add(j);
                        graph.put(i, neighbors);
                    }
                    if(graph.containsKey(j)){
                        graph.get(j).add(i);
                    }else{
                        TreeSet<Integer> neighbors = new TreeSet<>();
                        neighbors.add(i);
                        graph.put(j, neighbors);
                    }
                }
            }
        }
        // 然后从根节点0该开始,自顶向下删除从父节点指向根节点的边
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while(!queue.isEmpty()){
            int cur = queue.poll();
            visited[cur] = true;
            if(graph.containsKey(cur)){
                LinkedList<Integer> neighbors = new LinkedList<>();
                Iterator<Integer> iterator = graph.get(cur).iterator();
                while(iterator.hasNext()){
                    int next = iterator.next();
                    if(!graph.containsKey(next) || visited[next]){
                        continue;
                    }
                    queue.offer(next);
                    neighbors.add(next);
                }
                // 删掉父节点指向子节点的边
                while(!neighbors.isEmpty()){
                    graph.get(cur).remove(neighbors.removeFirst());
                }
                if(graph.get(cur).isEmpty()){
                    graph.remove(cur);
                }
            }
        }
        // 构建从versionA节点指向根节点的链表,versionB节点指向根节点的链表
        int len1 = 0, len2 = 0;
        ListNode headA = new ListNode(versionA);
        ListNode curA = headA;
        while(graph.containsKey(curA.val)){
            curA.next = new ListNode(graph.get(curA.val).first());
            curA = curA.next;
            len1++;
        }
        ListNode headB = new ListNode(versionB);
        ListNode curB = headB;
        while(graph.containsKey(curB.val)){
            curB.next = new ListNode(graph.get(curB.val).first());
            curB = curB.next;
            len2++;
        }
        // 求两个链表的第一个交点
        return FindFirstCommonNode(headA, headB, len1, len2);
    }
    
    private int FindFirstCommonNode(ListNode pHead1, ListNode pHead2, int len1, int len2) {
        ListNode h1 = pHead1;
        ListNode h2 = pHead2;
        if(len1 > len2){
            while(len1 > len2){
                h1 = h1.next;
                len1--;
            }
        }else if(len2 > len1){
            while(len2 > len1){
                h2 = h2.next;
                len2 --;
            }
        }
        while(h1.val != h2.val){
            h1 = h1.next;
            h2 = h2.next;
        }
        return h1.val;
    }
}

发表于 2022-01-06 23:09:38 回复(0)
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位于当前节点两边
    }
};

发表于 2022-06-14 20:17:28 回复(1)
1. 根据邻接矩阵生成邻接表,注意邻接表中是双向的,所以后续搜索时需要vis数组标记
2. 递归求最近公共祖先,如果a,b恰好在当前节点u的两个支路中,那么u即为最近公共祖先

vector<vector<int>> graph; // 邻接表
vector<int> vis; // 标记是否遍历过
int dfs(int u, int a, int b) {
    if (u == a || u == b) 
        return u; // 遇到a或b即返回
    vector<int> res; // 各支路的搜索结果
    for (int v : graph[u]) {
        if (vis[v] == 0) {
            vis[v] = 1;
            int r = dfs(v, a, b);
            if (r >= 0) res.push_back(r);
        } 
    }
    if (res.empty()) return -1;
    else if (res.size() == 1)
        return res[0]; // a,b都在其中一路中
    return u; // a,b在两个支路中,u即为所求
}
int Git(vector<string>& matrix, int versionA, int versionB) {
    // write code here
    int n = matrix.size();
    graph.resize(n);
    vis.resize(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == '1') { // 注意不是有向图
                graph[i].push_back(j); // 要添加双向关系
                graph[j].push_back(i);
            }

        }
    }
    vis[0] = 1;
    return dfs(0, versionA, versionB);
}


发表于 2022-07-09 01:22:47 回复(0)
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);
    }
};

发表于 2022-07-30 21:17:58 回复(0)
import java.util.*;

public class Solution {
    public int Git(String[] matrix, int versionA, int versionB) {
        //build the tree, only the parent node is needed, so use an array
        int n = matrix.length;
        int[] parents = new int[n];
        // Arrays.fill(parents, -1);
        for (int i = 0, len = parents.length; i < len; i++) {
            parents[i] = -1;
        }
        //build in the order of BFS,&nbs***bsp;the root node errors will occur
        int[] queue = new int[n];
        int qf = 0, qr = 0;
        queue[qr++] = 0;
        qr %= n;
        while (qf != qr) {
            int i = queue[qf++];
            qf %= n;
            char[] cs = matrix[i].toCharArray();
            int pi = parents[i];
            for (int j = 0; j < pi; j++) {
                if (cs[j] == '1') {
                    parents[j] = i;
                    queue[qr++] = j;
                    qr %= n;
                }
            }
            for (int j = pi + 1, csl = cs.length; j < csl; j++) {
                if (cs[j] == '1') {
                    parents[j] = i;
                    queue[qr++] = j;
                    qr %= n;
                }
            }
        }
        int[] al = new int[n];
        int aln = 0;
        int[] bl = new int [n];
        int bln = 0;
        int cur = versionA;
        while (cur != -1) {
            al[aln++] = cur ;
            cur = parents[cur];
        }
        cur = versionB;
        while (cur != -1) {
            bl[bln++] = cur;
            cur = parents[cur];
        }
        int l = Math.min(aln, bln);
        int before = -1;
        int alnm1 = aln - 1;
        int blnm1 = bln - 1;
        for (int i = 0; i < l; i++) {
            int a = al[alnm1 - i];
            int b = bl[blnm1 - i];
            if (a == b) {
                before = a;
            } else {
                break;
            }
        }
        return before;
    }
}


发表于 2023-10-17 14:03:10 回复(0)
["0001","0001","0001","1110"] 3, 2
你自己看看这个测试用例合理吗?题干的示例全是正向生长的树,测试的时候给个倒过来的树,有你这么玩的吗?
发表于 2023-06-16 15:44:05 回复(0)
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);
        }
    }
}

发表于 2023-04-20 10:05:12 回复(0)
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;
    }
}







发表于 2022-11-13 19:13:12 回复(0)
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]);
    }
}
总之确定每个节点的父节点就行了,父节点是唯一的

发表于 2022-09-22 00:22:13 回复(0)
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;
    }
};

发表于 2022-09-15 20:31:29 回复(0)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @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']

发表于 2022-08-31 11:55:59 回复(0)
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
        Map<Integer, Integer> map = new HashMap<>();//节点 - 父节点
        Queue<Integer> queue = new LinkedList<>();
        
        //0号节点
        for(int j = 0; j < matrix[0].length(); j++){
            if(matrix[0].charAt(j) == '1'){
                map.put(j, 0);
                queue.add(j);
            }
        }
        
        //之后的节点
        
        while(!queue.isEmpty()){
            int i = queue.poll();
            int father = map.get(i);
            for(int j = 0; j < matrix[i].length(); j++){
                if(j == father){
                    continue;
                }
                if(matrix[i].charAt(j) == '1'){
                    map.put(j, i);
                    queue.add(j);
                }
                
            }
        }
        
        System.out.println(map);
        Set<Integer> set = new HashSet<>();
        while(true){
            set.add(versionA);
            if(versionA == 0){
                break;
            }
            versionA = map.get(versionA);
        }
        while(true){
            if(set.contains(versionB)){
                return versionB;
            }
            versionB = map.get(versionB);
        }
        
    }
}
发表于 2022-08-11 20:05:52 回复(0)
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);
    }


}

发表于 2022-04-17 23:38:38 回复(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);
        }
    }
}
发表于 2022-04-15 16:16:47 回复(0)
1、在层序遍历的过程中,记录下每个节点的父节点与层级;
2、根据 1 构建好的数组,使versionA和versionB处于同一层级;
3、当versionA和versionB不相等时,同时向上找父节点,直至相等即为结果。

import java.util.*;

public class Solution {
    public int Git (String[] matrix, int versionA, int versionB) {
        int[][] tree = new int[matrix.length][2];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(0);
        while (!queue.isEmpty()) {
            int curr = queue.removeFirst();
            int layer = tree[curr][1] + 1;
            for (int i = 0; i < matrix[curr].length(); i++) {
                if (matrix[curr].charAt(i) == '1' && tree[curr][0] != i) {
                    tree[i][0] = curr;
                    tree[i][1] = layer;
                    queue.addLast(i);
                }
            }
        }
        while (tree[versionA][1] > tree[versionB][1]) versionA = tree[versionA][0];
        while (tree[versionA][1] < tree[versionB][1]) versionB = tree[versionB][0];
        while (versionA != versionB) {
            versionA = tree[versionA][0];
            versionB = tree[versionB][0];
        }
        return versionA;
    }
}


发表于 2022-03-24 20:28:37 回复(0)
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
        if(versionA==versionB){
            return versionA;
        }
        int num_node = matrix.size();
        vector<int> tree(num_node,-1);
        queue<int> q;
        q.push(0);
        while(!q.empty()){
            int node = q.front();
            q.pop();
            for(int i=1;i<num_node;i++){
                if(matrix[node][i]=='1'&&(tree[i]==-1)){
                    tree[i] = node;
                    q.push(i);
                }
            }
        }
        unordered_set<int> us;
        int node = versionA;
        us.insert(versionA);
        while(tree[node]!=-1){
            us.insert(tree[node]);
            node = tree[node];
        }
        node = versionB;
        if(us.find(node)!=us.end()){
            return node;
        }else{
            us.insert(node);
        }
        while(tree[node]!=-1){
            if(us.find(tree[node])!=us.end()){
                return tree[node];
            }else{
                us.insert(tree[node]);
            node = tree[node];
            }
        }
        return 0;
    }
};

感觉用了个特别复杂的思路,用vector记住每个节点的双亲结点,之后使用unordered_set不断放入节点双亲 直到出现重复就代表分支出现
发表于 2022-03-04 19:40:45 回复(0)
我的思路是,从0节点开始深度遍历,每次传入目标节点的信息,数组信息,当前节点号和上一个节点号(防止从0遍历到2,对2遍历时又遍历0这种情况)。

每次找的时候,先判断当前节点是否是目标节点,如果是,则记录下当前位置,返回查找成功;如果不是,则对该节点所连的节点进行遍历,如果找到从所连节点处找到目标节点,则记录当前位置,返回查找成功;

对两个目标节点查找完毕后,会形成两个数组,这两个数组的位置信息中从目标节点到根节点的位置信息,从最后开始查找,直到找到两个不同的节点,那么上一个相同的节点,就是需要返回的位置。

int logInfo[2][100] = {0};
int logLoc[2] = {0};
int numNo = 0;
int searchNode( int aimNode, char** matrix, int matrixLen, int loc, int pre)
{
    int i = 0, j = 0;

    if( loc == aimNode)
    {
        logInfo[numNo][logLoc[numNo]] = loc;
        logLoc[numNo]++;
        return 1;
    }
    for( i = 0; i < matrixLen; i++)
    {
        if( i == pre)
        {
            continue;
        }
        if( '1' == matrix[loc][i])
        {
            if( 1 == searchNode(aimNode, matrix, matrixLen, i, loc))
            {
                logInfo[numNo][logLoc[numNo]] = loc;
                logLoc[numNo]++;
                return 1;
            }
        }
    }
    return 0;
}
int Git(char** matrix, int matrixLen, int versionA, int versionB ) {
    // write code here
    int numA = 0; 
    int numB = 0;
    int i = 0;

    searchNode( versionA, matrix, matrixLen, 0, -1);
    numNo++;
    searchNode( versionB, matrix, matrixLen, 0, -1);
    
    numA = logLoc[0] - 1;
    numB = logLoc[1] - 1;
    
    for( i = 0; (i <= numA) && (i <= numB);i++)
    {
        if( logInfo[0][numA - i] != logInfo[1][numB - i])
        {
            return ( logInfo[0][numA - i + 1]);
        }
    }
    
    if ( i == (numA + 1))
    {
        return  logInfo[0][0];
    }
    else 
    {
        return logInfo[1][0];
    }
}


发表于 2022-02-12 11:28:18 回复(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)