算法基础学习结构梳理

由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):按照每一位数排序一遍。要求:可以分割出”‘位”进行比较,位之间有递进关系

二分法

递归实现和循环实现
要求:依赖顺序表结构,针对有序数据,不适合数据量太小或太大的情况
二分查找变体:

  • 第一个值等于给定值的元素
  • 最后一个值等于给定值的元素
  • 第一个大于等于给定值的元素
  • 最后一个大于等于给定值的元素

递归

父问题分为小问题的组合+最小问题的解法
防止堆栈溢出

BFS,DFS

贪心算法

分治

回溯算法

动态规划