2019-06-26 文稿

剑指 offer 总结

重要的几点：

• 看清题目
• 对象初始化
• 智商全程在线
• 优先处理边界条件

剑指offer中的大多数题目都属于easy级别，大多数的题目指明了使用的数据结构，还有类似链表反转、链表合并、堆实现的基础题目，正式的在线笔试题会难于其中的题目。

熟悉常用数据结构：queue、stack、set、vector、list、map、heap(priority_queue)、string

• map/dict 的使用 链接

逻辑简单，以降低时间/空间为主

降低时间复杂度

常用的方法是将顺序搜索变为二分搜索，根据问题的特性快速剪枝，用空间换取时间。

• 在有序的二维数组中查找是否有指定数字 快速剪枝
• 非减排序数组旋转后找最小值 二分搜索
• 获取栈中最小元素(奇数个数、最大值、质数个数...)空间换时间
• 数字在排序数组中出现的次数 链接
• 滑动窗口的最大值 链接

降低空间复杂度

• 两个链表的第一个公共节点 链接
• 数组中只出现一次的数字 (1个/2个) 链接
• 数组中重复的数字 0~n-1数字在大小为n的数组中 链接

递归

• 根据前序遍历中序遍历重建二叉树 链接
• 二叉树镜像 链接
• 判断数组是否可能为二叉树的后序遍历 链接
• 二叉树根到叶子之和为指定大小所有路径 链接
  • 路径向下 开始为根 结束不固定 （代码基本相同 O(n) ）
  • 路径向下 开始不固定 结束为叶子 （方法1：迭代上一方法 O(n^2), 方法二：静态列表/双向链表从子节点搜索 O(n) ）
  • 路径向下 开始和结束都不固定 (每个节点记录到所有祖先节点的和)
  • 路径可上可下 (每个节点记录到任意节点的距离[二维数组])
  • 有环树（图）
• 字符串排列 链接
• 把数组排成最小的数 链接
• 平衡二叉树的判断 链接

DFS

• 矩阵中的路径 链接

转移函数

• 斐波那契数列 f(n)=f(n-1)+f(n-2) 链接
• 青蛙跳台阶(只能跳1级或2级) 链接
• 用1×2和2×1的矩形覆盖2×n的矩形 链接
• 连续子数组的最大和 f(n)=max{ f(n-1)+a[n], a[n] } 链接
• House robber f(n)=max{ f(n-1), f(n-2)+a[n] } 链接

数据结构的应用

堆的应用

• 数据流中的中位数 链接

• 求最小的k个数 链接

队列的应用

对用在BFS中非常常用。

• 按层打印二叉树/计算层数 链接
• 迷宫寻路 链接

栈的应用

栈在DFS中非常常用，也经常用于有序容器的转置。

链表

• 链表中环的入口节点 链接

数学问题

• 青蛙跳台阶(可以是任意级) 链接
• 丑数 链接

计算机底层问题

• 如何原地交换两个数字
• 求一个数二进制表示中1的个数 链接
• 不用加减乘除做加法计算 链接
• 大整数相乘 链接

---

其他

• 逆序数的求解 hard 归并算法的使用
• 顺时针打印矩阵 问题切分