首页 > 试题广场 >

小米Git

[编程题]小米Git

热度指数：3621 时间限制：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

输出

算法知识视频讲解

Java

寄了的潜伏者很想去夏威夷

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)

Java

旧情长街

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)

Java

蛋混小

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)

Java

牛客308772163号

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)

Java

整顿职场的外卷侠很年轻

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)

Java

驯鹿非鹿

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)

Java

pein531

这个题的思路还是很简单的：

建立一个子节点指向父节点的有向图，图结构用邻接表存储；
根据版本编号versionA和versionB从图中取出从versionA节点和versionB节点出发到根节点的单链表；
求出两个单链表的第一个公共节点。

主要的难点在于建图，因为给出的邻接矩阵无法直接确定边的方向，只能先建立无向图的邻接表，然后根据根节点为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)