重学数据结构与算法
reference
https://kaiwu.lagou.com/course/courseInfo.htm?courseId=185
第一步,暴力解法。在没有任何时间、空间约束下,完成代码任务的开发。
第二步,无效操作处理。将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。
- 递归、二分法、排序算法、动态规划等常用的算法思维
第三步,时空转换。设计合理数据结构,完成时间复杂度向空间复杂度的转移。
- 数据结构
将“昂贵”的时间复杂度转换成“廉价”的空间复杂度
线性表
线性表是 n 个数据元素的有限序列
线性表真正的价值在于,它对数据的存储方式是按照顺序的存储。
如果数据的元素个数不确定,且需要经常进行数据的新增和删除时,那么链表会比较合适。
如果数据元素大小确定,删除插入的操作并不多,那么数组可能更适合些
链表
虽然链表在新增和删除数据上有优势,但仔细思考就会发现,这个优势并不实用。这主要是因为,在新增数据时,通常会伴随一个查找的动作
方法
- 链表的翻转
- 快慢指针
栈
顺序栈
数组
链式栈
链表
队列
顺序队列
依赖数组来实现,其中的数据在内存中也是顺序存储
假溢出
不惜消耗 O(n) 的时间复杂度去移动数据;
或者开辟足够大的内存空间确保数组不会越界
循环队列
当队列为空时,有 front 指针和 rear 指针相等。而现在的队列是满的,同样有 front 指针和 rear 指针相等。那么怎样判断队列到底是空还是满呢? 常用的方法是,设置一个标志变量 flag 来区别队列是空还是满
链式队列
依赖链表来实现,其中的数据依赖每个结点的指针互联,在内存中并不是顺序存储。链式队列,实际上就是只能尾进头出的线性表的单链表
防止删除最后一个有效数据结点后, front 指针和 rear 指针变成野指针,导致队列没有意义了。有了头结点后,哪怕队列为空,头结点依然存在, 能让 front 指针和 rear 指针依然有意义
- 约瑟夫环问题
数组
链表的长度是可变的,数组的长度是固定的,在申请数组的长度时就已经在内存中开辟了若干个空间
链表不会根据有序位置存储,进行插入数据元素时,可以用指针来充分利用内存空间。数组是有序存储的,如果想充分利用内存的空间就只能选择顺序存储,而且需要在不取数据、不删除数据的情况下才能实现
字符串
子串查找
树和二叉树
二叉树分类
- 满二叉树
- 完全二叉树
遍历方式
- 前序
- 中序
- 后序
二叉查找树
哈希表
如何设计哈希函数
- 直接定制法
- 数字分析法
- 平方取中法
- 折叠法
- 除留余数法
如何解决哈希冲突
- 开放定址法
- 线性探测法
- 链地址法
算法思维
降低时间复杂度
递归
汉诺塔
分治法
可采用分治法的问题的特征
难度在降低,即原问题的解决难度,随着数据的规模的缩小而降低。这个特征绝大多数问题都是满足的。
问题可分,原问题可以分解为若干个规模较小的同类型问题。这是应用分治法的前提。
解可合并,利用所有子问题的解,可合并出原问题的解。这个特征很关键,能否利用分治法完全取决于这个特征。
相互独立,各个子问题之间相互独立,某个子问题的求解不会影响到另一个子问题。如果子问题之间不独立,则分治法需要重复地解决公共的子问题,造成效率低下的结果
二分查找
必须有序
排序
冒泡
插入
归并:空间复杂度为 O(n)
快速:不稳定
动态规划
动态规划的基本方法
分阶段,将原问题划分成几个子问题。一个子问题就是多轮决策的一个阶段,它们可以是不满足独立性的。
找状态,选择合适的状态变量 Sk。它需要具备描述多轮决策过程的演变,更像是决策可能的结果。
做决策,确定决策变量 uk。每一轮的决策就是每一轮可能的决策动作,例如 D2 的可能的决策动作是 D2 -> E2 和 D2 -> E3。
状态转移方程。这个步骤是动态规划最重要的核心,即 sk+1= uk(sk) 。
定目标。写出代表多轮决策目标的指标函数 Vk,n。
寻找终止条件
一般而言,具有如下几个特征的问题,可以采用动态规划求解:
最优子结构。它的含义是,原问题的最优解所包括的子问题的解也是最优的。例如,某个策略使得 A 到 G 是最优的。假设它途径了 Fi,那么它从 A 到 Fi 也一定是最优的。
无后效性。某阶段的决策,无法影响先前的状态。可以理解为今天的动作改变不了历史。
有重叠子问题。也就是,子问题之间不独立。这个性质是动态规划区别于分治法的条件。如果原问题不满足这个特征,也是可以用动态规划求解的,无非就是杀鸡用了宰牛刀
解题方法论
复杂度分析。估算问题中复杂度的上限和下限。
定位问题。根据问题类型,确定采用何种算法思维。
数据操作分析。根据增、删、查和数据顺序关系去选择合适的数据结构,利用空间换取时间。
编码实现