1.重心 什么是树的重心？ 物理学而言，重心是指地球对物体中每一微小部分引力的合力作用点，物体受力最集中的那一个点。数学上的重心是指三角形的三条中线的交点。 树的重心也称为质点，有一个很官方的定义：如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。 现根据一个具体树结构解释重心的获取过程。 删除节点1，得到3棵子树，其子树的节点数量依次为3、4、1,最大值为4。 删除节点2，可得到3棵子树，其子树的节点数量依次为1、1、6，最大值为6。 删除节点3，可得到3棵子树，其子树的节点数量依次为2、3、...

公众号：编程驿站 1.欧拉图 本文从哥尼斯堡七桥的故事说起。 哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个话题：怎样不重复地走遍七桥，最后回到出发点。这也是经典的一笔画完问题。 1736年瑞士数学家欧拉（Euler）发表了论文《哥尼斯堡七桥问题》。论文中使用图论理论解决哥尼斯堡七桥问题，欧拉图由此而来。论文中欧拉证明了如下定理：一个非空连通图当且仅当每个顶点的度数都是偶数时才会是欧拉图。 欧拉图的几个概念： 欧拉回路：指在图（无向图或有向图）中，经过图中所有边且只经过边一次所形成的回路，称为欧拉回路。具有欧拉回路的图称为欧拉图。如下图结构...

公众号：编程驿站更多好文等你来 给大学生讲解SPARK时，说spark相比其它的大数据框架，其运行速度更快，是其显著的特点之一。之所以运行速度快，其原因之一因其使用先进的DAG（DirectedAcyclicGraph，有向无环图）执行引擎。SPARK提供了名为RDD(弹性分布式数据集（ResilientDistributedDataset）的简称)抽象的数据集。DAG引擎用来保证RDD数据集之间依赖的有序性、可靠性。 不理解DAG具体为何物以及其底层原理，并不妨碍使用SPARK，使用者只需要调用其提供的API，用于分析处理不同领域的数据便可。但是，如果能理解DAG的底层结构，对理解和学习SP...

公众号：编程驿站 1.前言 抛开基因的影响，学霸和学渣到底是在哪一点上有差异？ 学霸刷完200道题，会对题目分类，并总结出解决类型问题的通用模板，我不喜欢模板这个名词，感觉到投机的意味，或许用方法或通用表达式更高级一点。而事实上模板一词更准确。 每一道题目在描述时，会套上一堆场景说词，可以说是契合真正的应用领域，或者说是出题人的故弄玄虚，弄了一些花里胡哨的迷糊你的外表，这时考核的不是专业知识，而是语文阅读能力。一旦脱出外壳，露出来的底层需求，就是书本上最基础的知识。 小学生学乘法表后，老师会布置很多应用题，不管应用题目的描述如何变化，一旦语文阅读理解过关，剩下的就是套用九九乘法表。为什么学霸学...

1.前言 权重图中的最短路径有两种，多源最短路径和单源最短路径。多源指任意点之间的最短路径。单源最短路径为求解从某一点出到到任意点之间的最短路径。多源、单源本质是相通的，可统称为图论的最短路径算法，最短路径算法较多： Floyd-Warshall算法。也称为插点法，是一种利用动态规划思想寻找权重图中多源点之间[最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授[罗伯特·弗洛伊德命名。 Bellman_ford算法。贝尔曼-福特算法取自于创始人理查德.贝尔曼和莱斯特.福特，暴力穷举法，算法效率较低。但是，能解决的问题范围较大，...

1.DFS序和时间戳 1.1DFS序 定义：树的每一个节点在深度优先遍历中进、出栈的时间序列。 如下树的dfs序就是[1,2,8,8,5,5,2,4,3,9,9,3,6,6,4,7,7,1]。 下图为生成DFS的过程。对于一棵树进行DFS序，除了进入当前节点时对此节点进行记录，同时在回溯到当前节点时对其也记录一下，所以DFS序中一个节点的信息会出现两次。 Tips：因为在树上深度搜索时可以选择从任一节点开始，所以DFS序不是唯一的。 DFS序的特点： 可以把树数据结构转换为线性数据结构，从而可以把基于线性数据的算法间接用于处理树上的问题。堪称降维打击。 相同编号之间的节点编号为以此编...

1.LCA（最近公共祖先） 倍增算法的基本思想在前面的博文中有较详细的介绍，本文不再复述。此文仅讲解如何使用倍增算法求解多叉树中节点之间的最近公共祖先问题。 什么是最近公共祖先问题？ 字面而言，指在树上查询两个（也可以是两个以上）节点的祖先，且是离两个节点最近的祖先。如下图所示： 节点12和节点11的公共祖先有节点4和节点1。 节点4是离12和11最近的祖先。即12和11的最近公共祖先是4。也可描述为LCA(12,11)=3。 Tips：LCA是（LowestCommonAncestor最近公共祖先）的简称。 LCA有如下几个特性： LCA(u)=u。单个节点的的最近公共祖先为自己...

1.前言 Hadoop是分布式计算系统，在分布式环境中，网络通信模块是其核心模块之一。要学好Hadoop，需理解其底层通信系统的基本工作原理。Hadoop提供有体系完整的RPC框架，实现了对底层网络通信过程的优雅封装。 本文将从RPC概念说起，一起聊聊HadoopRPC的实现细节。 先理解什么是RPC？ RPC中的R是单词Remote的首字母，P是Procedure的首字母，C是Call首字母。 翻译过来：远程过程调用。如果仅是翻译一下，说了等于没有说。 如需彻底理解RPC，则需理解过程的含义： 过程可以认为是方法或函数，甚至可以认为是一个对象或子程序。为了简化问题，本文所说过程指方法。 ...