面试算法-常用数据结构

1）算法和数据结构

2）判断候选人的标准

• 算法能力能够准确辨别一个程序员的功底是否扎实

数据结构

数组

链表

优点：
1）O(1)时间删除或者添加
灵活分配内存空间

缺点：
2）查询需要O（n) 时间

解题技巧：
1）利用快慢指针
2）构建一个虚假的链表头

如何训练技巧：
1）在纸上或者白班上画出节点之间的相互关系

2）画出修改的方法

栈

特点：后进先出（LIFO）

算法基本思想：

1）可以用一个单链表来实现
2）只关心上一次的操作
3）处理完上一次操作后，能在O（1）时间内查找到更前一次的操作

队列

特点：先进先出（FIFO)

常用场景：

广度优先搜索算法

双端队列

基本实现：
1）可以利用一个双链表

2）队列的头部和尾部都能在O（1）的时间内进行数据的查看，添加和删除

常用场景：
实现一个长度动态变化的窗口或者连续区间

树

树的共性：

1）结构直观
2）通过树问题来考察 递归算法掌握的熟练程度

面试中常考的树的形状有

1）普通二叉树
2）平衡二叉树
3）完全二叉树
4）二叉搜索树 （重点）
5）四叉树
6）多茶树

特殊的树：红黑树，自平衡二叉树

遍历：（递归和非递归）+ 分析时间复杂度
前序遍历
中序遍历
后续遍历

二叉搜索树的中序遍历：是从小到大排序好的