2018年10月6日 0条评论 2点热度 阅读全文

判断给定的二叉树是不是平衡二叉树 本文体中,高平衡二叉树定义为:二叉树中任意结点的左右子树深度差不超过1 Example 1: Given the following tree [3,9,20,null,null,15,7]: 3 / \ 9 20 / \ 15 7 Return true. Example 2: Given the following tree [1,2,2,3,3,null,null,4,4]: 1 / \ 2 2 / \ 3 3 / \ 4 4 Return false. 1:递归,在计算二叉…

2018年9月4日 0条评论 1点热度 阅读全文

    既然你搜索到了这篇文章,那么平衡二叉树的作用想必心中已经清楚了,我们接下来就直接来谈谈代码... 目录   知识准备   进阶讲解     代码实现 谢谢阅读 知识准备       啥?你又不知道,真拿你没办法,给你一篇讲的不错的文章: 《大话数据结构》片段 进阶讲解         喂,看完别走呀,我再讲点进阶的知识,我们知道,平衡二叉树…

2018年9月3日 0条评论 1点热度 阅读全文

最短路径 Dijkstra Bellman-Ford Dijkstra 该算法的基本思想为: 每次找到离源点最近的一个顶点,然后以该顶点为中心进行扩展最终得到源点到其余所有点的最短路径。 基本步骤如下: 将所有顶点分为两部分:已知最短路程的顶点集合P和未知最短路程的顶点集合Q。用book[i]表示,如果book[i]=1则表示这个顶点在集合P中,反之顶点在集合Q中。 设置源点s到自己的最短路径为0。其余按照实际情况进行设置。 在集合Q的所有定点中选择一个离源点s最近的顶点加入到集合P。并考察所有以点u为起点的边,对…

2018年8月22日 0条评论 2点热度 阅读全文

《啊哈!算法》之图的遍历——深度广度优先算法 什么是图 深度优先遍历 广度优先遍历 什么是图 简单地说,图就是由一些小圆点(称为顶点)和连接这些小圆点的直线(称为边)组成的 这些箭头代表着只能单向访问,比如只能A→B,不能B→A,为有向图,反之为无向图 数字代表着访问顺序 了解了什么是图过后那么我们怎么用程序把图表示出来 最常用的方法是用一个二维数组e来存储,如下: 上图二维数组中第i行第j列表示的就是顶点i到顶点j是否有边。1表示有边,∞表示没有边,这里我们将自己到自己(即 i=j)设为0。我们将这种存储图的方法…

2018年8月20日 0条评论 2点热度 阅读全文

拓扑排序可以帮助我们找到时间发生的顺序,即是先穿外套还是先穿内衣。拓扑排序的原理思想很简单,即先建立一个邻接表,临界表中记录有各个顶点的入度,我们只要一次找到入度变为0的即可。 方法如下: 敲黑板~~~~ 1. 找到没有前驱结点即入度为0的顶点,输出它; 2. 与这个顶点相连的顶点的入度减一; 3. 一直重复上述两步直至所有结点都遍历了  附上超超详细代码 ~(^-^)~ /*Graph.h *图的出度邻接表的申明 */ #define MAXV 1024 typedef int ElemType; //…

2018年6月16日 0条评论 1点热度 阅读全文

22.4 拓扑排序:如果包含边(u,v)则u的拓扑排序在v的前边 拓扑排序的算法: TOPOLOGICAL_SORT(G) 调用DFS计算每个结点v的结束时间v.f(就是设置为黑色时候的时间) 在每个结束时间计算出来的时候加入到链表的前部 返回链表   1. p n o s m x r y v w z u q t 按照深度优先搜索给出的f从大到小排序   2. 线性时间内求两个结点之间简单路径的数量。   运用递归算法: Sim_Path(u,v){ if (u==…

2018年2月26日 0条评论 2点热度 阅读全文

静态查找表:只进行查找操作的查找表 动态查找表:在查找过程中同时插入查找表中不存在的元素,或者删除已存在的元素 本文主要总结静态查找表 1.顺序表查找:从第一个或者最后一个记录开始,将每个记录的关键字与给定值比较,若相等则查找成功。 C++实现: for(int i=0;i<n;i++) {     if(a[i]==key)         return i; } return 0; 时间复杂度: 最好情况:O(1),第一次就找到 最坏情况:O(n…

2017年3月31日 0条评论 1点热度 阅读全文

Floyd Dijkstra Bellman-Ford spfa 四种最短路经典算法汇总 最短路 Problem Description 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?   Input 输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店…

2017年3月25日 0条评论 1点热度 阅读全文

#include<iostream> #include<cstdio> #define L 11 using namespace std; //定义结构体Node,包含26个子节点位置以及以该节点为根节点的树拥有的完整单词的数目 typedef struct Node{ int num;// struct Node *child[26]; Node(){ num = 0; int i; for(i=0;i<26;i++){ child[i] = NULL; } } }Node; //字…

2016年8月5日 0条评论 2点热度 阅读全文