记录了剑指offer中的题目，不会写的都在后面加了思路注释，重点复习不会写的就行
数组与矩阵
栈队列堆
- 9. 用两个栈实现队列
- 30. 包含 min 函数的栈 no 栈的数据进出顺序逻辑的应用 例如 在栈低的较大的数一定后出，那么最大栈的顶端一定得是它
- 31. 栈的压入、弹出序列 no 模拟栈的push pop流程 重点在如何代码简化这个逻辑
- 40. 最小的 K 个数 no 堆
- 41.1 数据流中的中位数 no 中位数 只关心中间大的那个数，因此只需要中位数左边序列最大的右边序列最小的即可，两个堆
- 41.2 字符流中第一个不重复的字符
- 59. 滑动窗口的最大值 no 和min函数栈很类似。同样从数据进出先后顺序的逻辑下手存储数据流中的最大值
双指针
- 57.1 和为 S 的两个数字
- 57.2 和为 S 的连续正数序列 no 先想到暴力枚举，再想双指针优化
- 58.1 翻转单词顺序列 no 面试不能用 split 那么就倒序用双指针确定每个单词的边界
- 58.2 左旋转字符串
链表
22. 链表中倒数第 K 个结点 快慢指针
24. 反转链表 用递归做的关键思路是 清楚递归函数的意义。此题递归函数 输入为链表头，输出为反转后的新的链表头。
1->2->3->4 例如从 2 开始递归 那么 把2递归完毕后 1->2 null<-3<-4 并且返回的要是节点4；而2->3依然存在因此在递归完2以后需要把2接上3后面，然后把之前的递归的节点返。
52. 两个链表的第一个公共结点 a->b c->b b->d 的距离分别为 a,b,c 则 a+c+b = b+c+a 相遇即为公共节点。
树
- 7. 重建二叉树
- 8. 二叉树的下一个结点 按照中序遍历的规则 分情况讨论
- 26. 树的子结构 递归
- 27. 二叉树的镜像
- 28. 对称的二叉树
- 32.1 从上往下打印二叉树 层序遍历 （BFS）
- 32.2 把二叉树打印成多行
- 32.3 按之字形顺序打印二叉树
- 33. 二叉搜索树的后序遍历序列 按照比较大小的方法递归 判断左右子树是否合法
- 34. 二叉树中和为某一值的路径
- 36. 二叉搜索树与双向链表 官方的方法是 中序遍历一定是按照大小顺序遍历到搜索树的每个节点的 因此设置一个 pre cur指针来迭代的更改指向即可。还可以分支的思想 递归左子树 和右子树 分别得到左右两个循环链表 再加上中间节点重组成一个新的双向链表 但是这种方法逻辑比较复杂。
- 37. 序列化二叉树 主要是 字符转分割操作 怎么用 stringstream
- 54. 二叉查找树的第 K 个结点
- 55.1 二叉树的深度
- 55.2 平衡二叉树 递归 要注意所有节点的左右子树高度差都得满足
- 68. 树中两个节点的最低公共祖先 这个题也是递归 但是套用递归的思路很巧妙。
贪心思想
- 14. 剪绳子 贪心思想。
- 63. 股票的最大利润 记录最低的买入价格，并尝试以当前价减去前面最低的买入价得到利润。遍历求最大利润即可。
二分查找
分治
- 16. 数值的整数次方 递归
搜索
- 12. 矩阵中的路径 DFS
- 13. 机器人的运动范围 DFS BFS都可
- 38. 字符串的排列 DFS 将每个字母轮换放在首位 然后递归剩下的字符串 注意相同字母去重
排序
- 21. 调整数组顺序使奇数位于偶数前面 快慢指针 or 首尾对象指针
- 45. 把数组排成最小的数 这道题关键是知道 字符串比较的 性质 例如 1991 > 1199 是默认按照从高到底字符顺序比较的。那么在自己自定义 cmp 函数的时候 使用这个性质来快速 比较 两个字符串谁放前面。看谁放前面组合成新的字符串哪个小。或者自己写快排
- 51. 数组中的逆序对 归并排序 稍加改进即可 因为归并排序递归到最后就是比较两个数的大小，同时又由于 归并的时候左右两边的都是有序的 所以比较次数少。
动态规划
48. 最长不含重复字符的子字符串 动态规划 or 双指针 动态规划 ！！！ 注意连续 这就和 子数组最大和设置dp的出发点相同了
49. 丑数 不能 试图 按着判断某个整数是不是丑数，会超时。因此要从递推的角度思考，第n个丑数 和 第 n-1个丑数的关系。第n个大的丑数一定是由 第n-1个丑数 x 2/3/5得来的 至于是乘的哪个 那肯定是选最小的喽。但是不是 dp[n] x 2/3/5 可能是 dp[i] x 2 dp[j] x3 … 以2/3/5，所以就要设置三个指针分别 记录。有点像 三个迈的步子分别为 1/3/5的三个人从同一个1的起点开始走。走的距离最短的人优先跳步…..
60. n 个骰子的点数 状态转移方程很好想 n个筛子 点数 由 n-1个筛子时的点数 + 1 +2 … + 6 (注意判断边界)
62. 圆圈中最后剩下的数 思考子问题 不要关注中间 怎么数 只关注 起始 和 结束
数学
- 39. 数组中出现次数超过一半的数字 空间复杂度O(1) 时间复杂度O(N) 的方法 摩尔投票法
- 66. 构建乘积数组 数学问题
- 43. 从 1 到 n 整数中 1 出现的次数 题目别理解错了 是 所以的数字中 所有的1的个数，不是说统计含有1的数字的个数。因此思路就是分别统计个位/十位/…分别为1的个数，最后求和
位运算
其它
- 17. 打印从 1 到最大的 n 位数 要考虑 越界 因此本质是全排列问题
- 19. 正则表达式匹配 太难了 待定
- 20. 表示数值的字符串 状态机 通过状态表实现 就是情况很多
- 44. 数字序列中的某一位数字 找规律
- 46. 把数字翻译成字符串 动态规划
- 61. 扑克牌顺子 找规律
- 64. 求 1+2+3+...+n 用 && 代替 条件判断 （(true) && (a+=b)）这种条件判断里也能使用+=
- 65. 不用加减乘除做加法 二进制加法 不进位和 = 异或 进位 = 与左移 另外要注意c++负数左移低位默认补1 所以要强转为无符号。
- 67. 把字符串转换成整数