本文总结做过的题，和关键思路。
二分查找
| 题号 | 题目 | 描述 | 关键思路 |
|---|---|---|---|
| 数组 | |||
| 34 | Search for a range | 给int[] {5,7,7,8,8,10]，找到target=8出现的范围[3,4]。没找到返回[-1,-1] | 二分 |
| 35 | Search Insert Position | 有序无重数组[1,3,5,6],把target=5插入，问插入的位置=2 | 二分 |
| 74 | Search a 2D Matrix | 严格行、列、换行递增的二维数组，找target | 二分 |
| 240 | Search a 2D Matrix II | 行、列递增的二维数组，但换行不一定递增。找target | 每行二分，或从左下开始寻找 |
| 278 | First Bad Version | 版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号 | 二分，巧妙下标赋值 |
| 162 | Find Peak Element | 给一个数组。找峰值。相邻两个数都不一样。如果有多个峰值，就随便输出一个 | 二分 |
| 1901 | Find a Peak Element II | 二维数组。找四周峰值。相邻两个数都不一样。如果有多个峰值，就随便输出一个 | 二分 |
| 153 | Find Minimum in rotated sorted array | 找有序、无重、旋转数组（首位相接）中的最小值 | 二分 |
| 154 | Find Minimum in rotated sorted array II | 找有序、有重、旋转数组（首位相接）中的最小值 | 二分+精妙边界处理 |
| 33 | Search in Rotated Sorted Array | 从有序、无重、旋转数组（首位相接）中找target | 二分+精妙边界处理 |
| 81 | Search in Rotated Sorted Array II | 从有序、有重、旋转数组（首位相接）中找target | 二分+精妙边界处理 |
| 4 | Median of two Sorted Arrays | 找到两个有序数组的中位数 | 二分。太难了，没搞定。思路在《二分查找》里面 |
| 木材加工 | 把一些木头切成长度相同的小段木头，需要得到的小段的数目至少为 k。计算能够得到的小段木头的最大长度 |
将“最大长度”二分查找 | |
| 374 | Guess Number Higher or Lower | A出一个1~n之间的数字，B猜为k。每次调用guess(k)时，返回：-1=猜大了，1=猜小了，0=猜对了。实现一个函数，模拟B猜测数字的过程，最终输出A心里的数字 | 二分 |
数组与数
| 题号 | 题目 | 描述 | 关键思路 |
|---|---|---|---|
| 数组 | |||
| 88 | Merge Sorted Array | 给两个排序数组，A,B，将B合并进A | 从尾开始 |
| 349 | Intersection of Two Arrays | 求两个数组的交集 | 先排序 |
| 稀疏数组点乘 | 跳过0/建索引 | ||
| 第K大 | 堆、快速选择 |
二叉树与分治法
| 题号 | 题目 | 描述 | 关键思路 |
|---|---|---|---|
| 104 | Maximum Depth of Binary Tree | 求二叉树的最大深度 | 分治 |
| 110 | Balanced Binary Tree | 判断一个树是不是平衡二叉树 | 分治 |
| 236 ※ | Lowest Common Ancestor | 求两个节点的最近公共祖先 | 分治 |
| 124 | Binary Tree Maximum Path Sum | 给一个二叉树，找到从any node 到 any node最大路径和。路径可以在任何地方被结束掉 | 分治 |
| 226 | Invert Binary Tree | 将二叉树镜像反转（左右替换） | 分治 |
| 98 | Validate Binary Search Tree | 验证一个二叉树是不是搜索二叉树 | 分治 |
| 173 | Binary search Tree Iterator | 中序、依次输出搜索二叉树 | 中序遍历 |
| 108 | Convert Sorted Array to Binary Search Tree | 将有序数组转化为平衡二叉树 | 分治 |
| 109 | Convert Sorted List to Binary Search Tree | 将有序链表转化为平衡二叉树 | 中序遍历，骚操作 |
| 还有几道题。等之后二刷 | |||
| 102 | Binary Tree Level Order Traversal | 二叉树层序遍历 | 队列 |
| 107 | Binary Tree Level Order Traversal II | 二叉树层序遍历，从最下层开始 | 队列 |
| 103 | Binary Tree Zigzag Level Order Traversal | 输出二叉树的锯齿形、层序遍历 | 队列 |
| 199 | Binary Tree Right Side Viewl | 给一个二叉树。从最右边看去，能看到的数字都是几 | 队列 |
| 还有几道题。等之后二刷 | |||
| 144 | Binary Tree Preorder Traversal | 二叉树的前序遍历 | 栈 |
| 114 ※ | Flatten Binary Tree to Linked List | 将二叉树按照前序遍历的顺序变为只包含node.right的单链表 | 栈，巧妙只push right，还有两种骚操作 |
| 331 ※ | Verify Preorder Serialization of a Binary Tree | 验证一个序列是否是二叉树的前序遍历 | 分治法 |
| 145 ※ | Binary Tree Postorder Traversal | 二叉树的后序遍历 | 栈+hashset，还有一种栈+linkedList的骚操作 |
| 572 | Subtree of Another Tree | 给两个二叉树s和t。判断t是否是s的子树 | 两个二叉树同时遍历 |
| 106 | Construct Binary Tree from Inorder and Postorder Traversal | 用中序+后序恢复二叉树 | 分治 |
动态规划
| 题号 | 题目 | 描述 | 关键思路 |
|---|---|---|---|
| 64 | Minimum Path Sum | 从左上走到右下。只能向右向下走。求最小路径 | dp |
| 62 | Unique Paths | 从左上走到右下。只能向右向下走。求方案个数 | dp |
| 63 | Unique Paths II | 路上有障碍的上一题 | dp |
| 688 | Knight Probability in Chessboard | 给一个n*n的棋盘，每次可以走八个方向，如图所示。求从[r,c] 出发走K步之后它还停留在棋盘上的概率 | dp |
| 576 | Out of Boundary paths | 给一个m*n 的棋盘，每次可以走向上下左右四个方向。可以走回头路。求问在N步限制下，有多少种走出棋盘的方法 | dp |
| 70 | Climbing Stairs | 有一个楼梯，一步只能跨1/2步。问从0走到n层有多少层方案 | dp |
| 55 | Jump Game | 给一个数组A,A[i]表示在这里时最多可以跳A[i]步。只能向前跳。从数组A的第0位置出发，能不能跳到末尾。 | dp/贪心 |
| 45 | Jump Game II | 给一个数组A,A[i]表示在这里时最多可以跳A[i]步。只能向前跳。从数组A的第0位置出发跳槽最后一个位置（假设一定能跳到），问最少的跳的次数 | dp/贪心 |
| 300 ※ | Longest Increasing Subsequence | 求最长严格递增的子序列（子序列：可以跳着选 | dp |
| 354 ※ | Russian Doll Envelopes | 俄罗斯套娃信封。给一堆信封pair - [w,h] 。要求如果信封A的宽高都小于B的话，那么A就可以放入B。求这堆信封最多能套多少层 | dp |
| 673 | Number of Longest Increasing Subsequence | 求一个数组的最长递增子序列的个数 | dp |
堆
| 题号 | 题目 | 描述 | 关键思路 |
|---|---|---|---|
| 295 | Find Median from Data Stream | 求动态数组的实时中位数 | 两个堆，一个比中位数大，一个都比中位数小 |
| 347 | 给一个int[],输出频率最高的k个数字 | hashmap+堆 |