小胡同的诗

什么是时间复杂度？我们先看看一些函数的渐近表达式：关于时间复杂度的基本要点：时间复杂度反映的是随着问题规模的变大，计算所需的时间的增长速度，与系数的多少关系不大算法的渐近时间复杂度，简称时间复杂度，很多时候为了便于理解，直接把时间复杂度等同于O（）是可以的。常见的时间复杂度，及其增长速度比较：O(1)＜O(log2n)＜O(n)＜O(nlog2n)＜O(n2)<O(n3)<O(2n)＜O(n!)＜O(nn)O(1)＜O(log_2n)＜O(n)＜O(nlog_2n)＜

前言我们知道，计算机在处理数据的时候会先把数据读入内存，然后做相应操作后再写回内存。例如排序，当你内存大小大于数据量的时候，排序所要考虑的时间复杂度仅仅只有在内存中的部分，我们称它为内部排序；相对地，当内存不够，数据量大时，我们就要考虑分阶段进行排序，并且还伴随着大量的 I/O 操作，我们称后者为外部排序。本文主要讲外部排序中的败者树、置换选择排序、最佳归并树的算法原理，至于代码细节不做考虑。原理对于外部排序的顶层设计，我们大致可以归纳为三大步骤：首先，尽可能地读入数据到内存中进行内部排序，之后我

前言有向图的表示结构有多种，由于其有向性，结构中要人为给它规定起点和终点。对于无向图，我们可以根据有向图的结构，加双向边进行实现，但除了空间翻倍外，在某些要对边进行标记的问题时，还要去找到反向边，有可能这个复杂度不是 O(1)O(1)O(1) 的，那么整体复杂度也会相应提升。于是，多重邻接表可以有效解决这个问题。本文主要介绍多重邻接表的概念、定义等。概念和十字链表类似，多重邻接表是无向图的一种链式存储结构，区别的是多重邻接表：对于结点的设置不再把出边和入边分成两张链表，而是一张链表表示邻边；对于

前言有向图有多种存储方式：邻接矩阵、邻接表、逆邻接表、十字链表等。本文主要介绍 十字链表 ，并给出其结构体定义以及相应图解。概念十字链表是有向图的一种链式存储结构，可以看成有向图的邻接表和逆邻接表结合出来的产物。他能根据一个结点的出度指针以及入度指针快速找到多条边以及计算结点的出入度。和邻接表类似，结点的结构顺序存储，边的结构链式存储，这样方便边去索引到结点。定义结点结构是一张顺序表，里面每个元素表示图中的一个结点，而指针域中的两个指针分别为出边和入边的弧链表。结点结构(VexNode)

前言顾名思义，广义表就是线性表的拓展。通俗地理解，就是对于之前定义的线性表只能操作本表内的逻辑，而广义表拓宽了这个定义，于是能指向其他广义表，也就是说表与表之间建立起了联系。概念简单地概况广义表：表元素可以是原子也可以是一个广义表地线性表的拓展结构。长度：最上层元素的个数，一个表可以指向其他广义表，此时其他广义表在本表中也抽象成一个元素；指向数据项也就是原子项，此时也为一个元素。深度：其指向其他广义表的最大深度，因为其他广义表还可能再指向另外的广义表，此时求这个拓展的最大深度。注意，这里是最大深

前言对于一个工程项目，在管理的时候可以将其按规模、功能等特征划分成不同的模块，而当各个小模块完成并进行整合后整个项目也就相应完成。在划分的方法中，主流的方法是按事件、活动的方式进行划分，并且为了直观表示，可以对应到一张有向图中（一般是DAG图）。对于管理者总是关心各个模块的完成时间节点以及整体模块的完成时间时间节点，这些节点我们对于到图中的点 Vertex ，也成为事件，表示这个时间节点 A 事件完成；对于模块完成所要付出的前置工作我们将其对于到图中的边 Edge，也叫做活动，表示完成事件 A 的前置任

Θ，读音：theta、西塔；既是上界也是下界(tight)，等于的意思。Ο，读音：big-oh、欧米可荣（大写）；表示上界(tightness unknown)，小于等于的意思。ο，读音：small-oh、欧米可荣（小写）；表示上界(not tight)，小于的意思。Ω，读音：big omega、欧米伽（大写）；表示下界(tightness unknown)，大于等于的意思。ω，读音：small omega、欧米伽（小写）；表示下界(not tight)，大于的意思。大O符号（英语：Big O n

前言二叉树的遍历方式按顺序划分可分成前序、中序、后序遍历，其中，遍历的时间复杂度为 O(n)O(n)O(n)，空间复杂度为 O(logn)O(logn)O(logn)。在部分情况下，例如二叉树退化成链表，空间复杂度为 O(n)O(n)O(n)，这是因为无论是递归或者是非递归的遍历方式，都避免不了栈的开销。非递归只不过是把系统的递归栈自己手动实现罢了。Morris 遍历可以在增加时间复杂度的常数，但是实际的时间复杂度仍然是 O(n)O(n)O(n)，把空间复杂度优化到 O(1)O(1)O(1)，并实现二叉

出栈序列给定正整数 n，编程计算左边轨道车皮编号依次为 1，2，…，n 时，在右边轨道 最多可 以得到多少个不同的车皮编序方案。 例如当 n=3 时，最多得到 5 组不同的编序方 案如下：123132213231321思路：对于一个栈来进行搜索回溯操作，栈有内容时可以进行入栈和出栈两次操作，否则只入栈。注意回溯还原栈的内容时，应从输出队列中拿上一个回来，而不是只是单纯地移动游标，...

题目链接：LeetCode236思路：由于是单次的查询，且是二叉链表的存储方式，所以这里采用O(n)O(n)O(n)的遍历方式维护单词询问，核心逻辑是基于后序遍历的dfsdfsdfs。逻辑如下：当root是p、q其中之一时显然root就是LCA(T, p, q);当root非q且非p时要往左右两边搜索，如果恰好一边一个，那么root是LCA(T, p, q)；否则返回搜到非空结点的那一...

题目链接：LeetCode235思路：根据BST的性质可以得到以下逻辑：当root介于p、q之间时，LCA(T, p, q) == root；否则LCA要往p、q所在的区间去搜索。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * ...

算法描述倍增算法在ST表中的应用是直接在第二维的dp中直接以二进制的形式展现；而对于树上的问题则可以这样设计：设fa[i][j]表示i结点的第2^j个祖先，显然的是fa[i][0]等于i的父节点，假设父节点的祖先结点都已经更新完毕，我们就可以根据父亲的祖先来更新本结点的祖先，于是状态转移方程就成了fa[i][j]=fa[fa[i][j-1]][j-1]，这是根据二进制中可以拆分成两个相同小一次的...

算法描述tarjan算法在求强联通分量效率十分高，核心思想是维护的dfn和low数组；而对于树上公共祖先问题也能离线地处理询问，算法复杂度O(n+q)O(n+q)O(n+q)。算法是：后序遍历树上的结点，每次的子孙结点的祖先集合合并到其父亲结点中（并查集），之后去查询当前结点是否有询问，有询问且两个点都已经访问过那么这个两个点的LCA是另外那个点的祖先。由于是后序遍历的缘故，当前结点和另外那个结...

前言关于之前写的非递归遍历二叉树的一份代码由于当时图省事几乎没有注释，导致今天再次看代码时比较费劲。这份代码是纯C写的，设计到许多栈、指针的操作，可读性不高，于是现在通过这份博客对于非递归后序遍历二叉树进行一个总结回顾。以及完善当时的部分注释。文章链戳这里正文进入正题，关于遍历二叉树常用的方法是递归遍历。优点是代码量小，逻辑精炼，可读性高。而对于递归实际上在底层的汇编代码中，是开辟了一个系...

前言关于二叉树先、中、后遍历序列给一个中序序列以及其他一个就能够推出另一个序列，而如果单单只有先序与后序序列只能得到某两个结点的父子关系而不能确定一个唯一的二叉树。算法主要流程就是搜索，每次通过先序确定根节点，然后根据中序序列确定两个子树的规模，递归下去。复杂度分析在平均情况：T(n)=2∗T(n/2)+nT(n)=2*T(n/2)+nT(n)=2∗T(n/2)+n得：复杂度：O...

Hash表的平均查找长度包括查找成功时的平均查找长度和查找失败时的平均查找长度。　　查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数；查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数，可以理解为向表中插入某个元素，该元素在每个位置都有可能，然后计算出在每个位置能够插入时需要比较的次数，再除以表长即为查找不成功时的平均查找长度。下面举个例子：将...

目录前言性质抽象实现前言堆的数据结构是一个完全二叉树，其能实现优先队列的功能，主要的作用是能够动态地维护一个有关优先级的序列，使其在插入和删除都能在O(logn)O(logn)O(logn)时间内完成，查询能在O(1)O(1)O(1)完成。性质对于小根堆而言，这个二叉树形的结构只要满足所有的父节点都小于子节点就是小根堆，显然，这是个递归的定义。对于大根堆则是父节点大于子节点。抽象...

前言每次选三个数（第一个、最后一个、倒二个），以到二个作为中位数进行分治排序#include <bits/stdc++.h>using namespace std;#define ElemType int#define M 10ElemType arr[1000005], arr2[1000005];int vis[1000005];void SelectSort...

一、顺序队列的实现利用顺序表的特性，定义一个队列游标的结构，头front指向队列的头（注意！这里为了好操作不直接让头等于队列头，因为以后可以利用头追上尾表示队空，这个标准使得循环队列更易理解），尾rear等于队尾。然后就是几个基本的初始化、增加、减少、删除等操作。顺序的循环队列由于无法释放不需要的内存，相对循环队列，链队列而言容易造成假溢出。代码略，你可以用一个结构体数组模拟上述过程。二、链队列的...

链接：滑动窗口题目详情：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[...

题目：链接：https://www.nowcoder.com/questionTerminal/47d9d6dce7f140a5a2654fb852f118c8?toCommentId=379084来源：nowcoder一位大连理工的老师的评论解析：这道题答案个人觉得应该为D。虽然确实比较次数最多是m+n次。1.贡献时间复杂度的不是“移动”次数，而是“比较”，如果从“移动”的角度上考虑...

链接：和为S的连续序列题目详情：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!分析：很容易...

链表的生成利用链表实现一元多项式的+、-、*运算，注意具体的思路是判断同类项，对其进行合并同类项，在乘法运算达到了O(n^3)，可以优化的地方是先对结果链表C进行预处理，先复制这个链表给C，然后表C的操作过程就将了一维，变成O(n^2)，并且每次可以利用链表的有序性这一点进行二分，但这是链表啊！怎么二分？还没想到，干脆把链表先导入数组中，然后在操作？这样就O(nlogn)了？....扯远了，就先O...

循环链表的生成在之前带有头结点的链表的基础上，构建链表的时候，最后一个结点的指针域指向头结点的后继，即尾结点的后驱为头结点的后继。在之后功能的Coding中，要注意遍历完整个链表一次的标志是到达头结点的后继！要求实验四、线性表应用--约瑟夫环问题1 实验目的用循环链表解决约瑟夫问题。2 实验内容约瑟夫问题是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k...

一、二叉树的实现二叉树是计算机一个重要的结构，许多复杂算法都是由二叉树演变而来，其具有的性质和树相类似，但注意：二叉树和树不是同一个概念，他的孩子有左右之分。在二叉树的代码实现中，可以利用栈来实现，递归可以快速地生成二叉树，并且代码较简洁，但许多公司的面试题会考到二叉树的非递归实现方法，下面我用栈这个数据结构实现二叉树的构建，先序、中序、后序遍历以及销毁。这里需要C语言的指针掌握。二、二叉...

一、循环队列的实现由于顺序队列的实现可能会造成假溢出，这里引入一个循环队列，当然，这里你要知道数据在队列中的最大规模，否则循环队列慢之后想拓展就会变得非常麻烦！要求：实验七、实现循环队列各种基本运算的算法1 实验目的本实验是要实现循环队列的各种基本运算，通过该实验更深刻地理解线性结构的队列的特点。 2 实验内容实现循环队列的各种基本运算，并在此基础上设计一个主程序完成以下功能：(1) 初始化队列(...

一、顺序栈的实现顺序栈利用到顺序表的一些知识，当然你可以联想到数组，把其中一端固定为base，这里我们采用严蔚敏《数据结构》中的规范--空递增的方式。栈满后可以利用realloc拓展。具体实现代码如下：#include&lt;stdio.h&gt;#include&lt;stdlib.h&gt;//******宏定义参数******#define OK 1#define NO 0#de...

实验思路1.构建链表；2.各个功能的函数3.调试要求：1 实验目的本实验是要实现求集合（用单链表表示）的并、交和差运算，通过该实验更深刻地理解线性结构的链表的特点。 2 实验内容实现集合（用单链表表示）的并、交和差运算，并在此基础上设计一个主程序完成以下功能：(1) 初始化集合A{'c','a','e','h'}、B{'f','h','b','g','d','a'}和空集合C(2) 分别创建三个链...

快速排序是基于一种分治思想的排序，它的时间复杂度为O(nlogn),至于怎么分治呢？它的原理是：每次找一个标志数，本次函数的目的是为了找到他的正确位置。进而递归的找出所有数的正确位置，当然，在找的同时会把它左右两边的数有序！这里的有序是指它左边的数一定小于它（从小到大），右边的数一定大于它，不满足的话就交换两边的那对不符合要求的数。然后递归，去找两堆的数按这个规则继续“治理”。那么，既然是递归，我...

链表的生成上学期学链表的时候掌握了点皮毛，马马虎虎写了不带头结点的链表，这学期学数据结构觉得写代码要规范点才行，于是写了带头结点的链表。链表，顾名思义就是一串像链子的表格串接起来，当你不够用了，再开辟块内存接在这个链表的尾部，这时，就可以动态得分配内存大小，既不用担心拿多了内存造成浪费，也不用“处心积虑”地去考虑要存的数据到底需要多少。但是，相对于顺序表，链表的弊端还是有的，没错，就是要查哪个位置...

前言线性代数中对于一段数字序列的排列情况有这样一个定义：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。一个排列中所有逆序总数叫做这个排列的逆序数。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素...

实验十一、构造赫夫曼树1 实验目的本实验是要实现赫夫曼树的构造和编码，通过该实验更深刻地理解赫夫曼树的构造和编码过程。2 实验内容根据表11.1构造一棵赫夫曼树，输出对应的赫夫曼编码和带树路径长度。表11.1 单词及出现的频度单词 The of a to and in that he is at on for His are be频度 1192 677 541 518 462 45...

实验十二、无向图的邻接矩阵存储及广度优先搜索遍历1 实验目的本实验实现无向图的邻接矩阵存储，并输出邻接矩阵, 以及该无向图的广度优先遍历序列。2 实验内容建立如图所示的无向图G的邻接矩阵，并输出该矩阵。输出广度优先遍历序列Code：#include<stdio.h>#include<stdlib.h>#include<windows.h&gt...

由于栈是一种后进先出的数据结构，而队列是一种先进先出的数据结构，两者互相实现时要借助一个辅助的栈/队列，主要的思想还是根据两个相同的数据运算来达到互相实现。1，两个栈实现队列保证辅助栈为空，而数据栈来进行入队操作，这样在入队复杂度为O(1)O(1)O(1)每次出队或者取队头的时候，由于该元素在栈底，借助辅助栈把它还原到栈顶，然后取出或删去，剩下的数据要记得还原！否则顺序就会改变了。复杂度...

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。思路：利用两个栈来进行操作，一个存正常的栈数据，另一个辅助栈存放当前最小值。入栈时：如果当前没有最小值或者加入的数字小于等于当前的最小值则更新辅助栈，即push新数据，否则不操作，这里注意定义为小于等于就加入，而不是小于，因为比如出现两个相等最小，靠后那个数字被pop掉了此时最小还...

思路：维护两个栈，逻辑如下：奇数层的遍历明显从右到左，其下一层反向所以这层入栈的子树也应该从右到左偶数层反向注意在维护STL的时候指针参数地传递，关于对象的赋值要处理好，可以用指针减少不必要的麻烦！在处理遍历方向时候通过根节点加入不同的栈能够完成顺序地完全对称遍历，也就是本来是之字形遍历变为S型遍历Code：/*struct TreeNode { int val; ...

思路：该二叉树能够还原的充分条件是这两个序列必含有一个中序遍历序列。因为通过中序遍历序列以及之外的任意一个序列能够退出左右子树的规模，然后递归地构建父亲节点。Code:/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *rig...

题目：给两个长度均为N的升序序列，求两个序列的所有元素的中位数。定义一个长度为L的升序序列S，其L/2L/2L/2位置的数为中位数。思路：PS：这里网上挺多答案包括标准答案都是取靠中间的前一个作为中位数，但根据题目的意思似乎是靠中间的后一个才是中位数吧？很直观地能想到合并数组直接O(1)O(1)O(1)查找，时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n)对于这样...

实验十五、基于Dijsktra算法的最短路径1 实验目的掌握求解最短路径的Dijsktra算法。2 实验内容建立如图所示的邻接矩阵；2）根据Dijsktra算法求其从指定源点的最短路径。算法复杂度：O(N^2)补充：dijkstra可以利用堆的数据结构完成优化达到nlogn的时间复杂度Code：#include<stdio.h>#include<s...

实验十四、最小生成树1 实验目的本实验实现最小生成树的prime算法。2 实验内容建立如图所示的邻接矩阵；2）根据prime算法求其最小生成树，如从顶点A出发生成的最小生成树为：利用前缀点数组完成记录最小生成树建立的过程Code：#include<stdio.h>#include<stdlib.h>#define MAX_SIZE 20...