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 视为树的根节点。 数据范围:树上节点数量满足 示例图-笔试面试资料

这是qklbishe.com第19855 篇笔试面试资料
提供答案分析,通过本文《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 视为树的根节点。
数据范围:树上节点数量满足
示例图-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

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 视为树的根节点。
数据范围:树上节点数量满足 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 视为树的根节点。          数据范围:树上节点数量满足       示例图
示例图
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 视为树的根节点。          数据范围:树上节点数量满足       示例图
Java

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. 建立一个子节点指向父节点的有向图,图结构用邻接表存储;
  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)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 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 视为树的根节点。 数据范围:树上节点数量满足 示例图-笔试面试资料

提供最优质的资源集合

立即查看 了解详情