线性表链式存储查找元素时间复杂度
最好的情况就是k=1的时候,也就是查找在头结点后面一个结点时,时间复杂度为O(1)
最坏的情况是k=n+1的时候,也就是查找最后面一个结点时,时间复杂度为O(n)
平均复杂度为O(n)
钉子户4
递归(嵌套调用)用栈是经典
这里n取特殊值为4,也就是栈空间总共就4个,当栈1存了4个后(也就是栈满了),栈1的指针top[1]就是等于5,而栈2一个都没有存,栈2的底部是top[2]=4,两个差值为1
讲解地址:2021年下半年第57题_哔哩哔哩_bilibili
钉子户5
这里随便取M为6,所以队头是5,然后队列长度Q.len为3,那Q.rear是1,代进去求队头看看下面公式求出结果是不是5,其实就是代特殊值
讲解地址:2010年下半年第57题_哔哩哔哩_bilibili
这里我一开始是以为左边可以理解为是一个栈,这是错的,应该是打通的
讲解地址:2013年上半年第53题_哔哩哔哩_bilibili
两个栈是可以模拟一个队列的,但是两个队列是无法模拟一个栈的操作的,因为队列进出的顺序是一样的,而栈进出顺序是倒置的
钉子户6
讲解地址:2014年下半年第60题_哔哩哔哩_bilibili
这种题我是会做,但是我说不清,勉强说说做题技巧
首先next数组前面两个是01,这是固定的,然后我是直接求最后一个字母的next值
例如上面的abaac最后一个字母是c,在c前面的模式串是abaa,然后求这个模式串的next值(也就是当要求那个字母的next值时就是求它左边的那一串next的最大值)
长度为1时,abaa的最前面一个字母和最后面一个字母都是a,说明相等,那么next值为长度+1也就是1+1=2
长度为2时,abaa的最前面两个字母组合是ab,最后面的两个字母是aa,不相等,那么next的值为1
长度为3时,abaa的最前面的三个字母的组合是aba,最后面的三个字母的组合是baa,不相等,那么next值为1
长度为4时串的前缀和后缀都是同一个串,不合法,不用计算,所以取next值最大的作为最后一个字母的next值,也就是2,所以选B
总之,就是从长度1开始到(模式串-1)一个个的去求,只要前缀和后缀相同,那next值就是对应长度+1,不同那就是1
钉子户7
这公式理解了就很好记,其实也不用记,都不考
钉子户8
树的四个性质
二叉树的性质
给定结点数n,求二叉树的形态数量公式如下
链式存储
对于二叉链表来说,n个结点就有2n个指针域,然后n个结点就有n-1个分支,也就是n-1个指针不为空,那么为空的指针域就是2n-(n-1)=n+1个空指针域
总结:对于二叉链表来说,n个结点就有n+1个空指针域
对于三叉链表来说,n个结点有3n个指针域,这里多了一个父指针域,也就是第二个指针域的位置是指向父指针域的,那么n个结点就有n-1个分支和n-1个父指针域,所以空指针域是3n-(n-1)-(n-1)=n+2个空指针域
总结:对于三叉链表来说,n个结点就有n+2个空指针域
平衡二叉树
这是平衡二叉树,但是下面两个都不是平衡二叉树,完全二叉树一定是平衡二叉树,平衡二叉树不一定是完全二叉树 ,结点如果没有左右子树高度就是0,A结点的左子树高度是3,右子树高度是2,注意这里高度不是从A开始算,是从A的孩子结点开始算的
二叉排序树
上面的就是二叉排序树,也就是根结点大于左子树的所有结点,小于右子树的所有结点
最优二叉树(哈夫曼树)
最核心的就是权值相同加末尾,从左往右画好图
这里主要是知道权值相同时怎么处理(能够正确画好下面两个题就说明知道怎么处理了),然后一定记得是左小右大,画完最好检查一下符不符合这个左小右大,我经常忘了这个规则!
最优二叉树的判断是只有度为0和度为2的结点
讲解地址:构造最优二叉树例子_哔哩哔哩_bilibili
给定义一个序列画哈夫曼树
哈夫曼编码
记得左0右1就行
哈夫曼编码压缩比
这里是跟等长编码进行比较,2x>=n,x是要多少个等长编码,n是指有多少个字符,上面有5个字符,所以n=5,求出x=3,然后就可以算出压缩比了,注意这里求WPL的时候的路径长度怎么看,别跟结点所在高度搞混淆了,其实就是看那个路径在第几层那路径长度就是几。
讲解地址:哈夫曼编码压缩比_哔哩哔哩_bilibili
钉子户9
连通图和强连通图
这里注意
连通图是对于无向图来说的,所以一般称为无向连通图
无向连通图的最少边是n-1,最多边是n(n-1)/2
上面的是无向连通图,我一开始以为2-5没有边连接起来所以不是无向连通图,但是2-5是可以通过2-3-4-5实现的,也就是它不用必须直接把两个顶点用边连接起来,所以才会有上面的最少边和最多边的情况
强连通图是对于有向图来说的,所以一般称为有向强连通图,
有向强连通图的最少边是n,最多边是n(n-1)
这个图不是强有向连通图,因为顶点2并没有能够到达1和4的箭头
总的来说,不管是连通图还是强连通图,它们的核心判断就是看任意两个顶点能不能互相跑通,不一定要直接一口气跑到,可以跑到这再跑到那最后跑到目的顶点
无论是无向图还是有向图,它们所有顶点的度数之和都是边数的两倍
邻接矩阵表示法
也就是用矩阵来存储图,矩阵横表示i,竖表示j,有向图中A[i][j]=1表示顶点i指向顶点j,例如上面有向图中
A[1][2]=1说明顶点1指向顶点2,然后顶点1的出度就是数i=1的那一横有多少个1,入度就是数j=1的那一列有多少个1,例如上面的有向图中顶点1横着数有3个1,那就是出度为3,竖着数有1个1那就是入度为1
总结:矩阵横表示i,竖表示j,有向图中A[i][j]=1表示顶点i指向顶点j,横着指向竖着
邻接链表表示法
有向图的非0元素是e,无向图的是2e
钉子户10
深度优先搜索
深度优先搜索有回溯操作,而且搜索序列不唯一
讲解地址:深度优先遍历_哔哩哔哩_bilibili
当图用邻接矩阵表示时,那深度优先搜索的时间复杂度为O(n2)
当图用邻接链表表示时,那深度优先搜索的时间复杂度为O(n+e)
n为顶点数,e为边数
广度优先搜索
广度优先搜索序列也不唯一
讲解地址:广度优先遍历和时间复杂度_哔哩哔哩_bilibili
当图用邻接矩阵表示时,那广度优先搜索的时间复杂度为O(n2)
当图用邻接链表表示时,那广度优先搜索的时间复杂度为O(n+e)
n为顶点数,e为边数
钉子户11
例如上面的614325这个拓扑序列中,6在4的前面,那么可能存在弧6指向4,一定不存在弧4指向6,可能存在6到4的路径,一定不存在4到6的路径
讲解地址:拓扑排序_哔哩哔哩_bilibili
钉子户12
顺序查找就是从左往右查,不需要有序,适用于顺序和链式存储方式,平均查找长度为(n+1)/2
二分查找要求顺序存储并且是有序存储
这里首先我第一次做直接就把123给丢了,看题不仔细,其次二分法没学透,所以我选了C。
这里要先把下标从1标出来,然后求中间值,中间值如果是小数,那就用下取整的方法求,例如上面的(1+10)/2=5.5,向下取整为5(所谓的向下取整就是取小于这个数的最大整数),然后下标5对应的是55<95,说明在55的右边,那就是从62开始,也就是舍弃55这个中间值,55不参与下一轮的比较
总结:下标求中间值(比较值),中间值为小数则向下取整,比较后舍弃中间值进行下一轮比较
讲解地址:2010年下半年第60题_哔哩哔哩_bilibili
这里还要比较一次M【4】,这里我是没看懂就一个数还比较个屁,可能是最后确认一下
这里有个有意思的技巧,做这样的题目有个规律
关键字序列中有四种规律
大大大大大大一直大下去
小小小小小小一直小下去
小大小大一直这样小大下去
大小大小一直这样大小下去
看不懂直接去讲解地址看视频就知道了
讲解地址:2015年上半年第60题_哔哩哔哩_bilibili
(这个规律是折半查找的,别跟堆搞混淆了,我就把这个规律用到了下面题目中,想笑)
钉子户13
哈希函数的构造法知道除留余数法就行,就是求余
m的取值一般为不大于n但接近n的质数,n是指关键序列有多少个数字(记得有这句话就行)
散列表地址一般是从0开始(参考真题2就懂了这句话的意思)
解决冲突的方法
知道开放定址法就行了,说白了就是如果冲突了那就把那个数放到右边一位,如果还冲突那就继续往右推一位,直到不冲突为止,也就是把那个数放进去为止(这是线性探测法)
这个说白了就是如果冲突的话那就放到右边一位,如果还是冲突那就放到左边一位,这里的左边一位是以最开始冲突位置为原点的,再冲突就放到右边第4位,再冲突就放到左边第4位,以此类推
讲解地址:处理冲突拓展和装填因子_哔哩哔哩_bilibili
这里我一开始以为是地址只从0-7,其实地址应该是取0-m,这个m在这里是13,也就是取模的那个数,所以这地址是0-12
讲解地址:2011年上半年第61题_哔哩哔哩_bilibili
这里关键码10的哈希地址是10,65也是10,然后向右移动一位,但是发现右边没位置了,那就放到哈希地址0,可以把它想象成循环链表,10和1是拼在一起成为一个圈的
钉子户14
这里我主要是不记得这两个东西是什么玩意,因为太久没看了
就是给你一个序列,让你画出对应的大顶堆(大根堆)或小顶堆(小根堆)就行了
先根据序列顺序画一颗满二叉树,然后在一个个换位子,大顶堆要保证父结点比孩子结点要大,小顶堆要保证父结点比孩子结点小
钉子户15
所有排序的时间和空间复杂度
快速排序的空间复杂度是O(log2n),上面是错的
直接插入排序稳定不归位(归位就是能够在排序时确定最终排序的位置),适用于基本有序的情况
讲解地址:直接插入排序_哔哩哔哩_bilibili
希尔排序不稳定不归位
讲解地址:bilibili.com/video/BV1UP4y1A79a?p=35
计数排序适合序列里只有1-9的数字排序,说白了就是把要排序的数统计一下有多少个
讲解地址:直接插入、希尔、计数排序动画演示_哔哩哔哩_bilibili
简单选择排序不稳定归位
讲解地址:简单选择排序_哔哩哔哩_bilibili
堆排序不稳定归位
讲解地址:堆排序_哔哩哔哩_bilibili
冒泡排序稳定归位
讲解地址:冒泡排序_哔哩哔哩_bilibili
快速排序不稳定归位,对于基本有序的序列用快速排序效率是最低的,时间复杂度是最坏的情况O(n2),快速排序是采用分治法的思想
讲解地址:快速排序_哔哩哔哩_bilibili
归并排序稳定不归位,采用分治法的思想
讲解地址:归并排序_哔哩哔哩_bilibili
麻辣心得
1、希简快堆冒归位,其他就是不归位
2、归堆的时间复杂度都是nlgn(nlog2n)
3、空间复杂度除了快速排序O(log2n)归空排序O(n),其他都是O(1)
4、直接归冒泡稳定(直接插入排序、归并排序、冒泡排序稳定)
5、希尔直接冒泡最好时间复杂度为O(n),快归堆O(nlgn)最好,简单O(n2)
6、归堆O(nlgn)最坏,其他都是O(n2)
7、平均快归堆O(nlgn),希尔O(n1.3),其他为O(n2)
直接插入排序适用于基本有序的的序列,这个时候是比较次数最少的时候
讲解地址:2012年下半年第62、63题_哔哩哔哩_bilibili
这里我一开始是觉得65应该选C,也就是插入排序的平均时间复杂度,但是它这里是算最好的时间复杂度,这是因为它已经说了基本有序了,这是最好的情况,所以求的也是最好的时间复杂度
这里知道怎么转新堆就差不多了
讲解地址:堆排序_哔哩哔哩_bilibili
冒泡排序稳定归位
讲解地址:冒泡排序_哔哩哔哩_bilibili
快速排序不稳定归位,对于基本有序的序列用快速排序效率是最低的,时间复杂度是最坏的情况O(n2)
快速排序是采用分治法的思想,用i指针指向第一个,j指针指向最后一个,设置个p=第一个值,然后j指针指向的数字和p值比较,如果比p小那就把j指针指向的值赋值到i指针指向的值,如果比p大,那就j指针向左移动一位,然后阿巴阿巴,讲起来太抽象,建议直接看视频
讲解地址:2009年下半年第64、65题_哔哩哔哩_bilibili
讲解地址:2020年下半年第62、63题_哔哩哔哩_bilibili
这里归并排序没掌握,多看看
讲解地址:2011年上半年第65题_哔哩哔哩_bilibili
搞到这里我承认我真的麻了!!!