(笔试题)小米Git
Git 小米 笔试
2023-09-14 08:59:06 时间
题目:
git是一种分布式代码管理工具,git通过树的形式记录文件的更改历史,比如: base'<--base<--A<--A' ^ | --- B<--B' 小米工程师常常需要寻找两个分支最近的分割点,即base.假设git 树是多叉树,请实现一个算法,计算git树上任意两点的最近分割点。 (假设git树节点数为n,用邻接矩阵的形式表示git树:字符串数组matrix包含n个字符串,每个字符串由字符'0'或'1'组成,长度为n。matrix[i][j]=='1'当且仅当git树种第i个和第j个节点有连接。节点0为git树的根节点。)
输入例子:
[01011,10100,01000,10000,10000],1,2
输出例子:
1
思路:
git只是引入题目的一个背景,其实题目问题是:给一个多叉树,寻找多叉树上任意两点的最近共同父节点。多叉树通过邻接矩阵来表示,节点0表示根节点。
方法:寻找两点间的最近共同父节点,需要从两个节点出发,不断地往上回溯,直到找到最近的共同的父节点。那么我们需要记录每个点的父节点信息,通过该信息可以在某个节点处往上回溯,进而找到父节点。
父节点怎么记录?题目给出的是邻接矩阵,可以将邻接矩阵转为邻接链表,这样从根节点出发,即根节点入栈,然后出栈,先找到与根节点相邻的点,即树的一层(根节点为第0层),记录第二层节点的深度(即根节点+1),父节点(即根节点),然后将第二层的节点入栈,依次出栈,重复上述过程。这样就可以得到所有节点的深度和父节点信息。
代码:
class Solution { public: /** * 返回git树上两点的最近分割点 * * @param matrix 接邻矩阵,表示git树,matrix[i][j] == '1' 当且仅当git树中第i个和第j个节点有连接,节点0为git树的跟节点 * @param indexA 节点A的index * @param indexB 节点B的index * @return 整型 */ int getSplitNode(vector<string> matrix, int indexA, int indexB) { int n=matrix.size(); vector<vector<int> > adjList(n); vector<int> parent(n,-1); vector<int> depth(n,0); for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(matrix[i][j]=='1'){ adjList[i].push_back(j); adjList[j].push_back(i); } } } vector<int> stk; stk.push_back(0); int count=0; // depth[0]=0; while(!stk.empty() && count<n){ int node=stk.back(); stk.pop_back(); for(int k=0;k<adjList[node].size();k++){ int v=adjList[node][k]; if(parent[v]!=-1) continue; parent[v]=node; depth[v]=depth[node]+1; stk.push_back(v); count++; } } int a=indexA; int b=indexB; while(depth[a]>depth[b]) a=parent[a]; while(depth[a]<depth[b]) b=parent[b]; while(a!=b){ a=parent[a]; b=parent[b]; } return a; } };
相关文章
- [Git] git shortlog 找出最懒的程序员
- [Git] 给git命令起别名
- Git 基础 - 查看提交历史
- git分享(二)git checkout
- [Git] Use git add --patch for better commit history and mitigating bugs
- [Practical Git] Clean up commits with git rebase
- 详解Git工作区、暂存区、历史记录区以及git reset、git revert、git checkout等撤销命令的区别
- git的一些操作命令
- (笔试题)小米Git
- 【学习总结】Git学习-GIT工作流-千峰教育(来自B站)
- [Git] Recover Local Changes from `git reset --hard` with `git reflog`
- [Practical Git] Filter commit history with git log arguments
- [Practical Git] Format commit history with git log arguments
- 详解Git工作区、暂存区、历史记录区以及git reset、git revert、git checkout等撤销命令的区别
- git常用操作命令整理大全(含github操作)
- shell 写一个简单的 git 提交代码脚本
- git for c#, commit本地,pushserver
- Git知识总览(四) git分支管理之rebase 以及 cherry-pick相关操作
- Git知识总览(一) 从 git clone 和 git status 谈起
- 一文带你精通 Git(Git 安装与使用、Git 命令精讲、项目的推送与克隆)
- 【Git技巧】第七篇 git分区原理(超级详细)
- 史上最全Git学习教程
- Git 安装教程
- Git版本控制系统安装部署(二)
- [Git & GitHub] Windows安装git和环境变量配置