怎样解题
解算法题和解数学题非常相似，我们推荐的的解题方法和步骤参考了波利亚的《怎样解题 - 数学思维的新方法》。
1. 理解题目
“... 必须理解该题目的语言陈述，教师在一定程度上能对此进行检查；他请学生复述该陈述，而学生应该能够流畅地阐述该题目。学生还应该能指出题目的主要部分，即未知量，已知数据以及条件。”
最常见的错误是没有理解题目后就开始解题，所以解题的第一步是先找到题目的未知量，已知数据，条件，然后通过这些内容用自己的语言来重新阐述题目，并使用例子来证明已经理解了题目，例如：
“给定一个整数数组 nums ，找到一个具有最大和的连续子数组，并返回其最大和。”
对于这个题目，我们可以找到以下内容：
- 未知量：数组 nums 中连续子数组和最大的值
- 已知数据：nums 的数字范围为 1 到 2^31-1，nums 有重复元素
- 条件：合格的子数组为连续子数组
- 重新阐述：一个只包含正整数的数组中，找到和最大的一个子数组的和
- 例子：nums = [4, 6, 10], 返回结果为 20
在面试过程中，可以通过提问或者预测两种方式来与面试官确定数据的范围以及题目的细节，
提问：“数组的数字范围是多少？”
预测：“我们可以假设数组的数字范围在 1 ~ 2^31-1 吗？”
经过重新阐述之后，你可以从过去做过的题目中寻找灵感，这题的灵感在于：“任意一个正整数 A 加上另一个正整数 B 的和都大于 A”，显而易见，数组 nums 的和就是要求的未知量。当然，不是所有问题的灵感都那么直观，你需要通过不停做题和总结来积累经验。特别要注意的是，一道精心设计过的题目，你需要用到它所有的条件，如果你忽略了其中某些条件，那么很可能会让你偏离正确的方向，上面的题目如果没有限制数字是正整数的话：
“给定一个包含正负整数的数组 nums ，找到一个具有最大和的连续子数组并返回其最大和。”
题目难度就完全不同了，注意观察题目的每一个已知数据和条件。
2. 拟订方案
“我们当然知道，如果我们只有关于该主题的很少知识，要产生一个好的思路是困难的；而如果我们没有任何知识，那就完全不可能产生。好的思路来源于过去的经验和以前获得的知识。仅仅是记忆并不足以产生一个好的思路；仅有材料不足以盖一幢房屋，但不收集必需的材料就盖不了一幢房屋。求解某个数学题目所需要的材料是我们以前所获得的数学知识中某些与之有关的内容，比如以前求解过的某些题目或以前怎么过的某些定理。”
SSH 解题方法
对于一道算法题，可以尝试使用 SSH 方法来进行解题：
Similar：找到解决过的相似题目：
慢慢你会发现题目之间会有相似的地方，你可以通过将原题的一些条件普遍化，特殊化来转变为以前解决过的题目，当你要解答二叉树的后序遍历的时候，可以先回顾自己解决过的相似题目，例如二叉树的前序遍历，二叉树的中序遍历，然后尝试使用相似的解法来解答题目。有时候这种相似并不是那么明显，需要通过观察已知条件或者将多个已知条件进行运算来找到相似点。
Smaller：解决一道更简单的题目：
先解决原题的简单版，之后再通过简单版的变形来解决原题。对于这题我们可以先考虑数组没有旋转过的情况。也就是找到有序数组中元素的索引二分查找可以直接解决这个问题。接下来，我们观察原题和简单版的区别，发现原题是有两个有序数组组成的，可以理解为简单版的组合形式，有了这个观察之后，我们可以尝试将二分查找进行简单变形来解答此题。有时候，找到合适的简单版问题并没有那么容易，需要做一些转换。例如：“给定一个集合 S，需要求出符合某个特定条件的子集 A 的和”，如果直接求 A 的和比较困难，简单版可以先求相反的内容，求出 S 的和与 S - A 的和，再通过 S - (S - A) 来计算 A。
High level：假定子问题已经被解决：
原题可能包含多个子问题，或者涉及一些你不熟悉的数据结构或者算法。先不用花大量时间在子问题的细节中，可以假定子问题已经被解决，先从整体架构上解决问题，再尝试实现子问题。在排序数组中查找元素的第一个和最后一个位置中，通过观察，子问题是找到有序数组中第一个插入该元素的索引。解题过程中，你可以假定已经有这个 API，findFirst(nums, target)，你可以先实现主函数，再实现 API 的具体内容。这题可以轻松地解答：（为了简化代码，我们假定 target 一定存在在数组里）：
function solution(nums, target):
// 先假定子问题被解决
return [findFirst(nums, target), findFirst(nums, target+1) - 1]
function findFirst(nums, target):
// 之后再实现二分查找细节
......
完成整体架构再实现 API 的细节，这样做的好处是 1）即使你最后没有时间实现 API 或者细节出错的话，面试官也能看得出你对整体问题的理解和思路。2）如果你一开始的解题思路不正确，这题无法用二分查找来解答的话，那么一开始耗费时间在子问题的解决上就会白费功夫。
3. 执行方案
“解题方案给出了一个总体的框架，我们必须使自己确信细节都符合这个框架，所以我们不得不耐心地逐个检查所有细节，知道每一点都非常清晰，不再有任何可能会隐藏着错误的含糊之处。”
当你拟订好方案之后，执行方案就比较简单了，要注意几个关键点：
- 如果你的思路不清晰，那么你的代码一定不正确，要克制写代码的冲动，先用例子来理清思路。
- 注意代码风格，命名以及架构，例如函数和函数之间的调用关系
4. 回顾与检查
每做完一个类型的题目，你都需要对其进行 4 个维度的总结：
解题步骤：这类型题目应该按照怎样的步骤来解答？例如链表可以先口头提出使用额外空间的暴力解，拿到基本分，再根据面试官的要求实现常数空间的解法。
常用方法：这类型的题目有哪些常用的方法吗？二叉树的题目可以优先考虑递归，链表的题目考虑快慢指针或者通过链表长度来获取新的数据。
使用场景：这个算法或者数据结构有什么应用场景？知道二叉搜索树可以在对数时间内增删元素是不够的，我们需要结合实际题目，总结二叉搜索树能够解决什么问题？例如：
- 找到顺序统计量（中位数，极大值，极小值）
- 第 K 大的值
- 区间和，区间极值（通过在节点记录统计信息）
当我们把算法或者数据结构和使用场景关联起来后，遇到一道题目，经过分析后，就可以从自己的工具包中选择合适的工具来解题。
关键点：包括使用此算法或者数据结构的基本要求，实现过程中的易错点。
我们提供了一些例子，请你对做过的题目类型进行总结：
| 类型 | 解题步骤 | 常用方法 | 使用场景 | 关键点 |
|---|---|---|---|---|
| 链表 |
|
|
|
|
| 二叉树 |
|
|
|
|
| 二分查找 |
|
|
|
|