算法基础学习结构梳理
由2019.10面试经历总结而来。
常见的数据结构
- 数组
- vector容器
- 链表
- 栈
- 哈希表
- 跳表
- 二叉树
- 堆
- 队列
- 图
经典算法和方法
- 各种排序算法
- 二分法
- 递归
- BFS，DFS
- 贪心算法
- 回溯算法
- 分治
- 动态规划
常见的数据结构
数组
内存连续的线性表，用来存储相同类型的数据
线性表：每个数据前后只有一个数据相连，比如链表，队列，栈
随机访问
vector容器
与数组类似，支持动态扩容，实现分为arraylist和linkedlist，一般来说arraylist访问效率高，linkedlist插入删除效率高（需分场景），常用的为arraylist
链表
链表相关代码注意事项：
- 链表为空的处理
- 链表长度为一或二时的处理
- 头尾节点的处理
- 可使用哨兵法简化一些特殊情况的处理
栈
先进后出
栈数组的实现
class MyStack:
self.items = [] # 数据
self.size = 0 # 容量
self.top = 0 # 当前元素index
经典场景：函数调用
队列
先进先出
队列数组的实现
class MyQueue:
self.items = [] # 数据
self.head = 0 # 头index
self.tail = 0 # 尾index
经典场景：生产者消费者模型
哈希表
散列函数选择，装载印子影响扩容效率
散列冲突解决方法：开放寻址，拉链法
与链表配合使用可实现LRU
跳表
多级链表
Redis中SortedSet实现方法
二叉树
特殊的二叉树：满二叉树，完全二叉树，可以用数组存储
堆
由完全二叉树实现，分为最大堆和最小堆，python heapq是最小堆，可用于实现堆排序，优先队列
heapq常用方法
heapq.heapify(x)
heapq.heappush(heap, item)
heapq.heappop(heap, item)
heapq.heappushpop(heap, item)
heapq.heapreplace(heap, item)
图
表示方法：邻接表，邻接矩阵
经典算法和方法
各种排序算法
评价标准：时间复杂度、是否原地排序(空间复杂度)、是否稳定排序、元素移动次数
冒泡排序
插入排序：每次插入新元素，遍历查找应该插入的位置
选择排序：每次从未排序区间找到最小元素放到已排序区间的末尾，非稳定排序
归并排序：分治，down-top，把数组分成前后两部分，对前后两部分分别排序，再合并有序数组，非原地排序
快速排序：分治，top-down，选择pivot，把数组分成三部分，再对pivot左右两部分排序
桶排序：分成n个桶，遍历一编数组放入桶，再在桶内部排序。要求：要可以分桶，要考虑桶均匀性
基数排序(radix sort)：按照每一位数排序一遍。要求：可以分割出”‘位”进行比较，位之间有递进关系
二分法
递归实现和循环实现
要求：依赖顺序表结构，针对有序数据，不适合数据量太小或太大的情况
二分查找变体：
- 第一个值等于给定值的元素
- 最后一个值等于给定值的元素
- 第一个大于等于给定值的元素
- 最后一个大于等于给定值的元素
递归
父问题分为小问题的组合+最小问题的解法
防止堆栈溢出