为了找工作，题还是要刷起来~
Problem 4
总结： 我们很容易想到需要使用二分来完成这道题，但它的输入却是两个数组，这使普通的二分对此题无效。解这道题的关键在于意识到如果数组 1 的 break point i 确定了，那么数组 2 的 break point j 也就确定了，因为我们需要维持中位数两端数字个数一致，因此我们只需要对 i 进行二分即可。这道题即使想到这里可能也需要一些时间才能写出，实现时我们需要对奇偶等一些细节进行判断。
Problem 5
总结： 看到这道题的直观想法是生成一个倒序字符串，然后使用动规找出最长公共子串，但是这样做需要考虑一种情况：acxyzca，它的“ac”和“ca”会被匹配到一起；另一种做法是直接动规，但是这道题最快的解法其实是最简单的解法，那就是遍历字符串的每一个字符，同时往两端查找，虽然这种做法和动规同样是 O(n^2) 的最坏复杂度，但是考虑到多数情况下字符串都不对称，因此它的实际复杂度应该接近于 O(n)。我相信这道题应该还有更快的解法，但是刚刚提到的解法已经可以满足这道题的速度要求了。
Problem 11
总结： 我们显然不能使用暴力 O(n^2) 来解这道题，凭直觉来看也不大可能是任何带 log 的复杂度，因此我们只能硬着头皮使用 O(n) 复杂度的算法：贪心。想出贪心算法非常简单，贪心的难点永远在于对它正确性的证明。
这道题我们使用的贪心算法是：起初将左边界和右边界分别安放在最两端，然后我们将较矮的那个边界向中心收，以此循环，直到左右边界相碰，最优解一定存在于这个过程的某个状态中。我们需要通过反证法来证明这个算法的正确性：假设某一时刻左边界为 i，右边界为 j，我们假设左边界较矮，因此我们需要进行 i++。算法的反面是，存在一个最优解，它的左边界就是 i，右边界是小于 j 的某一个值，而我们 i++ 时把它错过了。我们很容易证明这个反面的错误性，因为任何以 i 为左边界，右边界小于 j 的容器体积都不可能有容器 (i, j) 大，这与我们的假设矛盾，也从而我们证明了贪心算法的正确性。
Problem 16
总结： 这道题的解法其实很直观，暴力的话我们需要三重循环，但是其实这里有一个非常简单有效的优化，我们可以把首尾合到一个循环里，这样我们就可以使用 O(n^2) 的复杂度来解出这道题了。
Problem 31
总结： 先举一个例子：126543，它的下一个排列数是 132456。通过这个例子我们便已经可以得出算法了：倒序搜索这个数，找到第一个下降的点 2，颠倒它之后的所有数字 123456，再交换它与它之后的那个数字即可。
Problem 32
总结： 直接给出一维动规的解法，这个答案有点巧妙：假设我们已经找到了当字符串长度小于 n - 1 时最长合理括号的所有答案，那么如果第 n 位是“(”，答案保持不变；如果第 n 位是“)”，那么答案分两种情况：1. 如果第 n - 1 位是“(”，那么答案为上一步的答案加 2；2. 如果第 n - 1 位是“)”，上一步的答案为 a，那么答案为上一步的答案加 2 加上追踪到 a + 1 步前的答案。
一个简单的例子是：()((()))，前 7 步的答案是 ans = [0, 2, 2, 2, 2, 2, 4]，那么第 8 步的答案为 ans[7] + 2 + ans[7 - ans[7] - 1] = 4 + 2 + ans[2] = 8。
Problem 37
总结： 不用多想，DFS 是效率最高的解。
Problem 41
总结： 这道题很有意思，我们需要意识到一个问题，如果数组长度是 n 的话，那么我们需要找的那个丢掉的数一定是小于 n 的。根据这个思路我们就可以得出解决了，我们只需要遍历一下这个数组，如果扫描到数字 x，那么我们就把它放在第 x 位，如果 x 超出了 n，那么我们直接不管它即可；接着我们再扫描一次数组，找出数字不等于位置的第一个数，那个位置就是我们需要找的第一个丢失的整数。
Problem 42
总结： 首先说这题的暴力思路：遍历每一个位置，往左往右找到边界，该位置的水的体积就是左右边界中的小值，这样的复杂度时 O(n^2)。优化它的思路也很简单，我们只需要实现正序倒序各遍历一次数组，求出每个位置的左右边界，计算水体积的时候直接查表，就可以成功地将复杂度压缩到 O(n)。
Problem 45
总结： 我觉得这个问题是有难度的。我们很容易可以想出 O(n^2) 复杂度的解，但是我们需要用线性的时间来完成这道题。解决它的思路是使用 BFS 去搜索，但是我们不会将图给建起来，因为建图的代价本身就是 O(n^2)。这里用了一个小技巧来标记 BFS 的 level，那就是当前能达到的最远的点：一旦越过了这个点，那么我们就需要另一跳来达到它之后的点。
还是举一个简单的例子：[2, 3, 1, 1, 4]，第一 level 是 2，因为 0 跳只能到起始点；第二 level 是 3， 1，因为根据 0 + 2 我们最远只能到 1 的位置；第三 level 是 1，4，因为 1 + 3 已经可以达到终点 4 了。
算法做的事情很简单，线性地扫描一次数组，如果当前位置超过了当前最大值，那么跳数加一；如果没有则看当前位置加当前距离能否更新当前最大值。当走到终点时的跳数就是我们需要的答案。