时间复杂度
时间复杂度O与高数中无穷小o的区别
O可以理解为“同阶无穷大” ； O(f(n))算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。
.png)
在不确定具体位置的查找中，时间复杂度为什么算作O(n)，n的含义是至多全部元素遍历一次？
加权平均耗时为 (3n+1)/4。用大 O 表示法来表示，去掉系数和常量，加权平均时间复杂度仍然是 O(n)。
需要按情景考虑：最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized time complexity）
线性表
单链表设置头节点的作用,带与不带的区别（待仔细研究，听课，看书）
头结点：在单链表的第一个结点之前附加一个结点，称为头结点。头结点的Data域可以不设任何信息，也可以记录表长等相关信息。
-
优势1：第1个位置的插入删除更加方便
-
优势2:统一空表和非空表的处理
线性表两种储存结构的优缺点
双向循环链表的优点
单循环链表尾节点
静态链表的设计理念
简答题
- (1)试述顺序存储结构和链式存储结构的特点,并比较顺序存储结构和链式存储结构的优、缺点。
2017真题:已知某线性表采用链式存储结构，链表第一个结点的指针为ist；结点类型定义为
typedef struct node { int data; /数据域/ struct node link; /指向该结点的直接后继结点的指针域 /i }LinkList
请写一算法，删除链表中数据域值相同的多余结点，即：对于链表中具有相同数据域值的结点，只保留其中一个，其余结点均从链表中删去，使得到的链表中所有结点的数据域值都不相同。
// 选择排序
void sort_list(LinkList list) {
LinkList i=min=list,j;
while(i) {
for(j=i;j;j++) {
if(j->data < min->data) {
LinkList temp = j;
j = min;
min = temp;
}
}
LinkList temp = i;
i = min;
min = temp;
i++;
}
}
void delete_multi(LinkList list) {
while(list) {
LinkList i = list;
// 查找相同值的位置
do {
i++;
} while(i && i->data == list->data)
// 根据查找位置移动指针
if (i == list) {
list++;
} else {
list = i++;
}
}
}
栈与队列
堆栈和队列是两种在操作上受到限制的线性表。栈只允许在栈顶插入和删除，队列只允许在队尾rear插入（进队），在对头front删除（出队）。
栈
顺序堆栈的储存结构可以用一个具有M个元素的数组表示STACK[M],M表示最大容量，定义一个整形变量top作为堆栈的栈顶指针，STACK[0]为第一个进入堆栈的元素，当堆栈为空栈时，top = -1。
简答题
- 3.31 假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”
- 3.28 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
树
基本术语
节点的度：节点拥有的子数目成为该节点的度。树的度：树中各节点度的最大值被定义为该树的度。
叶子节点：度为0的节点称为叶子节点或者终端节点。分支节点：度不为0的节点称为分支节点。
节点的层次：从根节点所在层开始，根节点为第1层，根节点的孩子节点为第2层。。。
树的深度：树中节点的最大层次数被定义为该树的深度或者高度。
基本性质
性质一：非空树的节点总数等于树中所有结点的度之和加1
性质二：度为k的非空树的第i层最多有k^i-1个节点(i>=1)
性质三：深度为h的k叉树最多有(k^h-1)/(k-1)个节点
性质四：具有n个节点的k叉树的最小深度为[logk(n(k-1)+1)]
哈夫曼树：
构造过程：
1 输入所有的值，分别生成单独的树，将lchild，rchild置为0，共构成n棵树的森林。
2 在树林中选则两棵根的权值最小的子树，合并为根节点权值为和的二叉树。（全局选取，若最小的两个子树是高度为1刚生成的树，则选取这两颗）
3 重复2.
算法题：
18. 已某哈夫曼树采用二叉链表存储，根结点指针为 T，各叶结点的 data 域中已经存放了对应的权值。请写一非递归算法，该算法的功能是计算该哈夫曼树的带权路径长度（WPL）。
二叉树后续遍历，VISIT逻辑为
if (p->lchild == NULL && p->rchild == NULL) {
WPL += p->data * (top + 1);
}
P = NULL; //千万记得在判断外面，否则无限循环
17. 结点的祖先定义为从根结点到该结点的所有分支上经过的结点。已知非空二叉排序树采用二叉链表存储结构，根结点指针为 T。请写一非递归算法，依次打印数据信息为 item 的结点的祖结点。设节点的数据信息分别为整数，并且假设该结点的祖先结点存在。
// 利用排序树的特点,一次遍历既可打印所需信息
While(p) {
If (p->data == element) {
Break;
} else if (p->data < element) {
Printf(“%d “, p->data);
P = p->lchild
} else if（p->data > element) {
Printf(“%d “, p->data);
P = p->rchild
}
16. 已知二叉树采用二链表存储结构，根结点的地址为 T。请写出判断二又树是否为二又排序树的非递归算法。若是二又排序树，算法返回 1, 否则，返回 0。（假设各结点的数据互不相同）
key:排序树中,中序遍历能得到一组顺序数列
中序遍历后的数列检验是否为顺序排列: 加入数列时检验是否大于前一项
*15.* 已知非空二叉树采用二又链表结构，请写出生成该二又树的中序线索二又树的非递归算法
生成线索二叉树会考吗？
14. 已知非空二树采用二叉链表结构，根点指针为 T。请利用二树遍历的非递归算法写出求二叉树中由指针 q 所指结点（设 q 所指结点不是二叉树的根结点）的兄弟结点的算法。若二又树中存在该兄弟结点，算法给出该兄弟结点的位置，否则，算法给出 NULL。
后续遍历，增加一个堆栈，存储是否为左子树，访问逻辑：若等于element，则取出STACK1[]栈顶数据，访问另一端子树。
12. 已知二树采用二叉链表存储结构，根结点的地址为 T。请写一算法，打印该二叉树所有左子树的根结点的数据信息
13. 已知非空二叉树采用二叉链表结构，根点指针为 T。请写出求 p 所指结点的双亲结点的递归算法。
11. 已知二又树采用二又链表存储结构，根结点的地址为 T。请写一算法，按层次从上到下，每层从右到左的顺序依次列出二叉树所有结点的数据信息。
内排序
分类:
1 按工作量划分:简单排序法,先进排序法,基数排序法
2 按策略划分:插入排序,选择排序,交换排序,归并排序,基数排序
插入排序
简单插入排序法
核心逻辑:第i趟排序将序列中的第i+1个元素k(i+1)(i=1,2,…,n-1)插入到一个已经按值有序的子序列的合适位置,得到一个的长度为i+1且仍然保持按值有序的子序列.
时间复杂度:比较次数n^2/4, O(n^2)
稳定排序
需要一个元素的辅助空间
折半插入排序法
核心逻辑:在简单插入排序法的基础上,每次插入时,用折半查找的方法确定被插入元素在该有序序列中的合适位置.
时间复杂度:最坏O(n^2),最好O(nlog2n)
不稳定排序
选择排序
核心逻辑:第i趟排序将序列中的第后n-i+1(i=1,2,…,n-1)个元素中选择一个值最小的元素与该n-i+1个元素的最前面那个元素交换位置,即与整个序列的第i个位置上的元素交换位置.如此下去,知道i=n-1,排序结束. 换言之:每一趟排序从序列中未排好序的那些元素中选择一个值最小的元素,然后将其与这些排好序的元素的第1个元素交换位置.
时间复杂度:最坏O(n^2),最好O(nlog2n)
不稳定排序
泡排序
核心逻辑:通过相邻元素之间的比较与交换,使值较小的元素逐步从后面移到前面,值较大的元素从前面移到后面. (最大的元素被安置在序列最后的位置,再缩小范围冒泡), 排序的总趟数不一定为n-1,结束条件之一为:“在一趟排序过程中没有进行过元素交换的动作”.
时间复杂度:最坏O(n^2),最好O(n)
稳定排序
谢尔排序
核心逻辑:通过相邻元素之间的比较与交换,使值较小的元素逐步从后面移到前面,值较大的元素从前面移到后面. (最大的元素被安置在序列最后的位置,再缩小范围冒泡), 排序的总趟数不一定为n-1,结束条件之一为:“在一趟排序过程中没有进行过元素交换的动作”.
时间复杂度:最坏O(n^2),最好O(n)
稳定排序
快速排序
快速排序由C. A. R. Hoare在1962年提出。
核心逻辑:
时间复杂度:最坏O(n^2),平均O(nlog2n)
不稳定排序
leetcode题目分类及刷题顺序推荐
https://leetcode-cn.com/circle/article/48kq9d/
一. 数组
题目分类 题目编号
数组的遍历 485、495、414、628
统计数组中的元素 645、697、448、442、41、274
数组的改变、移动 453、665、283
二维数组及滚动数组 118、119、661、598、419
数组的旋转 189、396
特定顺序遍历二维数组 54、59、498
二维数组变换 566、48、73、289
前缀和数组 303、304、238
题解 数组篇
二. 字符串
题目分类 题目编号
字符 520
回文串的定义 125
公共前缀 14
单词 434、58
字符串的反转 344、541、557、151
字符的统计 387、389、383、242、49、451、423、657、551、696、 467、535
数字与字符串间转换 299、412、506、539、553、537、592、640、38、 443、8、13、12、273、165、481
子序列 392、524、521、522
高精度运算 66、67、415、43、306
字符串变换 482、6、68
字符串匹配 28、686、459、214
中心拓展法 5、647
三. 数与位
题目分类 题目编号
数字的位操作 7、9、479、564、231、342、326、504、263、190、191、 476、461、477、693、393、172、458、258、319、405、171、168、 670、233、357、400
简单数学题 492、29、507
快速幂 50、372
四. 栈与递归
题目分类 题目编号
用栈访问最后若干元素 682、71、388
栈与计算器 150、227、224
栈与括号匹配 20、636、591、32
递归 385、341、394
五. 链表
题目分类 题目编号
链表的删除 203、237、19
链表的遍历 430
链表的旋转与反转 61、24、206、92、25
链表高精度加法 2、445
链表的合并 21、23
六. 哈希表
题目分类 题目编号
哈希表的查找、插入及删除 217、633、349、128、202、500、290、532、 205、166、466、138
哈希表与索引 1、167、599、219、220
哈希表与统计 594、350、554、609、454、18
哈希表与前缀和 560、523、525
七. 贪心算法
题目分类 题目编号
数组与贪心算法 605、121、122、561、455、575、135、409、621、179、 56、57、228、452、435、646、406、48、169、215、75、324、517、 649、678、420
子数组与贪心算法 53、134、581、152
子序列与贪心算法 334、376、659
数字与贪心 343
单调栈法 496、503、456、316、402、321、84、85
八. 双指针法
题目分类 题目编号
头尾指针 345、680、167、15、16、18、11、42
同向双指针、滑动窗口 27、26、80、83、82、611、187、643、674、 209、3、438、567、424、76、30
分段双指针 86、328、160、88、475
快慢指针 141、142、143、234、457、287
九. 树
题目分类 题目编号
树与递归 100、222、101、226、437、563、617、508、572、543、 654、687、87
树的层次遍历 102、429、690、559、662、671、513、515、637、103、 107、257、623、653、104、111、112、113、129、404、199、655、 116、117
树的前序遍历 144、589
树的前序序列化 606、331、652、297、449
树的后序遍历 145、590
树的中序遍历与二叉搜索树 94、700、530、538、230、98、173、669、 450、110、95、108、109
重构二叉树 105、106
二叉树的展开 114
最近公共祖先 235、236
Morris中序遍历 501、99
四叉树 558、427
十. 图与搜索
题目分类 题目编号
图的建立与应用 565
深度优先搜索 17、397
回溯法 526、401、36、37、51、52、77、39、216、40、46、47、31、 556、60、491、78、90、79、93、332
回溯法与表达式 241、282、679
回溯法与括号 22、301
回溯法与贪心 488
广度优先搜索 133、200、695、463、542、130、417、529、127、126、 433、675
并查集 547、684、685
拓扑排序 399、207、210
有限状态自动机 65、468
十一. 二分查找
题目分类 题目编号
二分查找应用(简单) 374、35、278、367、69、441
二分查找应用(中等) 34、540、275、436、300、354、658、162、4
二分查找与旋转数组 153、154、33、81
二分查找与矩阵 74、240
二分答案法 378、668、410、483
十二. 二进制运算的应用
题目分类 题目编号
异或的应用 89、136、137、260、268
与或非的应用 371、318、201
十三. 动态规划
题目分类 题目编号
数组中的动态规划 509、70、338、45、55、198、213、650、91、639、 552、123、188、309、32、264、313、403
子数组、子序列中的动态规划 689、413、446、368、416、279
背包问题 322、518、474、494、377
矩阵中的动态规划 62、63、64、120、576、688、221、629、174、96、 329
动态规划与字符串匹配 583、72、97、115、516、132、131、139、140、 514、10、44
状态压缩动态规划 464、691、698、638、473
区间中的动态规划 486、664、375、312、546
树形dp 337、124
数位dp 233、600
十四. 数据结构
题目分类 题目编号
数据结构设计——栈与队列 225、232、284、622、641、155
数据结构设计——哈希表 676、355、380、381
数据结构设计——哈希与双向链表 432、146、460
前缀树 208、211、648、386、677、472、421、212、336、440
堆 23、373、378、632、347、692、502、630、407、295、480
树状数组 307、315、493、327、673
线段树 699
平衡树(set/map) 352、218、363
十五. 采样
题目分类 题目编号
按权值采样 528、497
蓄水池抽样 382、398
拒绝采样 470、478、519
十六. 计算几何
题目分类 题目编号
计算几何基础 593、447、223、149
分类讨论法 335
凸包 587
覆盖问题 391
十七. 常用技巧与算法
题目分类 题目编号
博弈论 292
分块 239、164
倍增法 330
拓展欧几里得算法 365
洗牌算法 384
找规律 390、672
分治法 395、667
排序算法 147、148
线性筛 204
摩尔投票法 229
