1. collections模块
collections模块提供了一些内置数据结构的扩展
namedtuple：让tuple属性可读
deque：可以方便实现deque/stack
counter：需要计数器的地方使用
orderedDict：key的顺序是第一次插入的顺序
defaultDict：带有默认值的字典
2. dict底层结构
dict底层使用的哈希表
- 为了支持快速查找使用了哈希表作为底层结构
- 哈希表平均查找时间复杂度O(1)
- cpython解释器使用二次探查解决哈希冲突问题
3. list/tuple区别
- 都是线性结构，支持下标访问
- list是可变对象，tuple保存的引用不可变
- list没法作为字典的key，tuple可以（可变对象不可hash）
4. 什么是LRUCache？
least-recently-used替换掉最近最少的对象
字典用来缓存，循环双端列表用来记录访问顺序
5. 排序+查找，重中之重
- 常考排序算法：冒泡排序、快速排序、归并排序、堆排序
- 线性查找、二分查找等
- 能独立实现代码（手写），能够分析时间空间复杂度
常用排序算法的时空复杂度
6. python数据结构常考题
- 常见的数据结构，链表、队列、栈、二叉树、堆
- 使用内置结构实现高级数据结构，比如内置的list/deque实现栈
- leetcode或者剑指offer上的常见题
链表
- 如何使用python来表示链表结构
- 实现链表常见的操作，比如插入节点，反转链表，合并多个链表等
206 leetcode，反转链表
队列
队列是先进先出结构
- 使用python的list或者collections.deque实现队列
栈
- 使用python的list或者collections.deque实现队列
如何用两个栈实现队列
实现获取最小值的栈
字典与集合
- 哈希表的实现原理，底层其实就是一个数组
- 根据哈希函数快速定位一个元素，平均查找O(1)，非常快
- 不断加入元素会引起哈希表重新开辟空间，拷贝之前元素到新数组
二叉树
前序：根左右
中序：左根右
后序：左右根
递归处理三种遍历
二叉树的镜像
层序遍历二叉树
堆
堆：可以看做是完全二叉树的数组对象
heapq标准库，堆排序
topK问题
链表
- 熟悉链表的定义和常见操作
- 237 删除一个链表节点
- 21 合并两个有序的链表
7. 白板编程
- 刷题
- 真正理解掌握
- 打好基础
- 常见排序算法和数据结构能手写
- 多写多练
- 一般可能一次很难写对
- 尝试自己先思考，先按照自己的方式编写代码，提交后发现问题
- 如果实在没有思路可以搜题解
网友评论