解题模式——如何分析未知问题
给定整数数组A[0...n]，将其重新排列，使得A[0]>A[1]<A[2]>A[3]<…
hint:假设我们已经有如此排列的数组A[0...n], 则当A[n+1]出现时，我们该如何调整以便使得整个数组满足约束？分若干种情况进行讨论。
2. longest palindrome O(n^2) ：给出一个数组，求其中最长的回文子数组。
hint: 如果我们已经有一张表，记录所有前N个元素之间的组合是否是palindrome，那么，我们只要O(N)时间，就可以判断出第N+1个元素和1…N元素的组合是否是palindrome。这个观察1可以用在接下来的题目里2可以优化成中心扩展的O(N^2)算法
另外，用suffix tree或者某神算法可以得到O(N)的解，但是无论是哪种方法，都表明了palindrome的中心点非常重要
3. longest valid parentheses (O(N)): 给出一个由左括号和右括号组成的数组，求最长的合法括号子数组。
hint:若我们已知了以1…N每一个元素为结尾的最长括号子数组的长度，那么我们可以O(1)时间知道以N+1这个元素作为结尾的最长括号子数组长度——这里要注意合并两个括号序列。如：(())()。
4. 已知有一个数组，其中正数若干，负数若干，我们要将其重新排列成偶数位上都是正数，奇数位上都是负数的形式，保证原正数和负数的相对位置不变，inplace，问有比O(n^2)好的办法木有？(请参考上一篇博文)
5. Jump Game。已知一个数组，里面的元素是非负整数，代表从这个格子可以向前跳的步数。问从0出发，是否能够跳过最后一个元素。
hint:去掉第一个元素的同时，如何保证不丢失信息？类似的想法可以直接作用于Jump Game II。
6. Container With Most Water。已知一个数组，代表各点上容器一边的高度。现在求一个能容纳最多水的容器(maximize min(A[j], A[i]) * (j – i), j > i)
hint: 我们虽然很难去掉一个元素，但是我们一定可以去掉首尾元素中的一个，因为它们中的一个作为边的最大容积我们可以直接得知，在之后的计算中，再也不需要考虑这个边。
FPI通讯一·为什么我们倾向分析而不是倾向规约
FPI通讯四：知识就是力量——论KMP与AC算法
长久以来，在面对未知问题时，我们常常会显得手足无措。我在一次面试时，曾经试图将名人问题转化成已知问题，却连连受挫，无法给出面试官所希望的O(n)算法。尽管我在面试官提示下了解了那个巧妙的O(n)算法，但是却有另一件事情令我大惑不解。之前的这种规约方法，在我高中时代的题海战术中明明是有效得很，为什么现在却只能在很小的一个范围内生效了呢？这个规约方法，在波利亚的如何解题中曾经被提及，具体为：
我是否解决过类似问题？相似的思路是否能用于现在看到的这个新问题？
后来我草草阅读了Knuth先生的具体数学。书中一再强调的一种解题模式是：
从小case开始做试验，以找出规律，建立直觉
grey code可以作为一个这类问题的例子。在忽略公式解法的情况下，将n=3的grey code列出来，任何一个人都很容易看出其规律，这个例子留给读者自行尝试。
然而当我将这种方法应用在其他算法问题上时，我立刻就意识到，这不是一个通用的方法。对于小case过多，小case到大case状态变化复杂，小case即非常复杂的问题，这个方法基本无能为力。之后我在阿呆牛的推荐下读了算法引论——一种创造性方法其中一再推荐的一种解题模式是：
试着将问题的规模减少1或者一半或者一定规模，即divide and conquer或decrease and conquer
天。这是一条如此明显的规则，我一直在有意无意地使用它，但是在将其明确化为一条模式之后，我开始发现，在很多问题面前我可以用一种有逻辑的手段去分析，而不仅仅是依赖我的直觉。
就像EPI中一再强调的：能不能将问题划分为更小问题？如果答案是能，那么只要加上memorization，一个动态规划解法即告产生——即使这个方法未必是最优——在多数问题上，动态规划解法已经可以给出令人满意的复杂度。
EPI中虽然也用了整整一章来解释解题模式，但是在后面的大量训练中，却是墨守成规，回到了其他面试训练书籍的老路上，又是数组序列、树和图、链表、排序搜索那一套，毫无新意。可以理解，这本书由四个作者写成，前后的语言风格都有细微差别，更不用想有一个在全书中能够一贯而通的线索了——其实还是有一个，就是题难。
之后我又阅读了Algorithmic Puzzles，里面也在开头讲解了解题模式，对于我的视野也是一个很好的补充。
另外，枚举也是减小问题规模的方法之一——它常常用来固定一个变量，但是代价就是要枚举这个变量的所有状态。对于部分题目，枚举和二分是相通的，但是二分开始的时候并不是那么明显。因为我们要对一个度量（如长度）做二分。我们可以从枚举开始入手。
在说明我们的结构之前，我先列举剩下的解题模式：
穷举并剪枝
这条是很明显的，当我们无法用其他任何方法得到一个简单的解法时，我们唯有退回最原始暴力的办法。然而，我们常做的dfs暴力穷举，其实是在解空间树中进行搜索。它的leaf有两种，一种是有解(solution leaf)，一种是无解(dead leaf)。如果我们在进入一个分支时可以尽早发现这个分支通向死路，那么我们就应该尽早返回。
利用单调变量(monovariant)约束算法
最通俗的例子是：一个矩阵中元素有正有负，你可以进行的两种操作是，同时改变一行的符号或者同时改变一列的符号，问如何通过若干次操作使得各行、各列的和均为正。
提示是，整个矩阵的和是一个单调变化的变量。
利用不变量来找出矛盾
例如，马踏棋盘问题。这条请读者自行google并解答。
以上两条可以归并为同一个解题模式：
找出每一次操作后变化的关键变量，利用此变量变化的规律来解题
最后，我要强调一点：
贪心算法和动态规划不是解题模式，它们只是decrease/divide and conquer的具体形式
我将在之后的一系列专题中，以解题模式为线索来讲解问题——一个有关树的问题，其模式却可能更近似于数组问题。这里的解题模式可能不是最全面的，但是我相信已经没有大的遗漏。需要强调的是：
工具和知识仍然是重要的
如果不理解后缀树，不理解AC自动机，那么无论如何分析，多模式匹配的算法复杂度也不会降低到相应的水平。这些需要长时间的积累，不是能够一蹴而就的。我的目的只是启发如何“破冰”。
模式一：decrease/divide and conquer释义
将问题划分为更小规模的问题，然后利用小规模问题的解推导出大规模问题的解
分类
- 将问题增加一个新元素
- 将问题分成两半，然后合并两者结果
辩护
看到下面的习题时，你可能会说这不就是动态规划大合集吗？
是，也不是。很多decrease by one的题目，我们可以很容易地推出其解法为动态规划；但是我们说一道题是动态规划，却隐藏了它的很多实质内容——此其一。有些动态规划的题目，规划得莫名其妙，比如longest palindrome的中心向两侧扩展，看起来容易记忆，也顺理成章，但是自己发明创造一个这玩意，却不是那么直观的，此其二。
应用方法
在面对一个问题时，问自己如下的问题，如果可以解答，则一个动态规划算法即告产生：
『假如我已经知道了0…N范围内的所有解，我能不能利用它们获得N+1的解？』
而divide and conquer的nlogn解法往往源于：
『假如我已经知道了两个规模为N/2的问题的解，我能不能在O(N)时间内将它们组合成一个规模为N的解？』
很多时候我们卡在一个问题上不知所措，上面的这两个小小的自我质问可能会帮助破冰——有着明确目标的、可以分析的问题总是比等待灵感到来靠谱很多。
例题(hint均以白色字体给出)
给定整数数组A[0...n]，将其重新排列，使得A[0]>A[1]<A[2]>A[3]<…
hint:假设我们已经有如此排列的数组A[0...n], 则当A[n+1]出现时，我们该如何调整以便使得整个数组满足约束？分若干种情况进行讨论。
2. longest palindrome O(n^2) ：给出一个数组，求其中最长的回文子数组。
hint: 如果我们已经有一张表，记录所有前N个元素之间的组合是否是palindrome，那么，我们只要O(N)时间，就可以判断出第N+1个元素和1…N元素的组合是否是palindrome。这个观察1可以用在接下来的题目里2可以优化成中心扩展的O(N^2)算法
另外，用suffix tree或者某神算法可以得到O(N)的解，但是无论是哪种方法，都表明了palindrome的中心点非常重要
3. longest valid parentheses (O(N)): 给出一个由左括号和右括号组成的数组，求最长的合法括号子数组。
hint:若我们已知了以1…N每一个元素为结尾的最长括号子数组的长度，那么我们可以O(1)时间知道以N+1这个元素作为结尾的最长括号子数组长度——这里要注意合并两个括号序列。如：(())()。
4. 已知有一个数组，其中正数若干，负数若干，我们要将其重新排列成偶数位上都是正数，奇数位上都是负数的形式，保证原正数和负数的相对位置不变，inplace，问有比O(n^2)好的办法木有？(请参考上一篇博文)
5. Jump Game。已知一个数组，里面的元素是非负整数，代表从这个格子可以向前跳的步数。问从0出发，是否能够跳过最后一个元素。
hint:去掉第一个元素的同时，如何保证不丢失信息？类似的想法可以直接作用于Jump Game II。
6. Container With Most Water。已知一个数组，代表各点上容器一边的高度。现在求一个能容纳最多水的容器(maximize min(A[j], A[i]) * (j – i), j > i)
hint: 我们虽然很难去掉一个元素，但是我们一定可以去掉首尾元素中的一个，因为它们中的一个作为边的最大容积我们可以直接得知，在之后的计算中，再也不需要考虑这个边。
FPI通讯一·为什么我们倾向分析而不是倾向规约
在FPI系列中，我将『转化』称为『规约』，原因主要是为了凸显逼格。
我们先看一个小例子。昨天在群里有人说到：
『如何inplace将数组A向左循环移k位』即rotate({2, 1, 3, 4, 5, 5}, 2) –> {3, 4, 5, 5, 2, 1}
对于见过这道题目的人，或者是能迅速联想到反转句子问题的人，这道题的解很简单：先将整个数组reverse，再reverse前n – k个数，再reverse后k个数。
那么如果这道题是陌生的，我们该如何入手去解决呢？
1. 我首先想到整个数组向左循环移动k位，可以分解成每个元素向左循环移动k位
2. 在最naive的情形中(k整除n)，如果我们将一个位置和它移位前的位置列在一起，它们将形成一个循环。也就是说， 0, k, 2k, … (d-1)k, 0. (n/k=d);
3. 进而我联想到，即使k不整除n，每个数仍然在一个圆圈上; (回想一下归位法) 例如n=10, k=4, 则我们从0开始可以得到, 0, 4, 8, 2, 6, 0
4. 对于某一个圈圈，我们可以取出其首位的数字，然后迭代地去找应该在当前位置上的元素，直到我们请求首位数字为止，如：
5.对于一个圈看起来不错，我们可以把这个圈上所有的元素都放到需要的位置上去。那么对于多个圈怎么办？我们如何有效检测一个圈是否已经处理过？在这里我卡了一下，然后我仔细检视了n=10和k=4的这个例子，以及n=5和k=3的例子。看起来似乎如果n和k互质，那么我们就只会得到一个圈。而10和4的例子里我们有两个圈。
6. 互质一个圈，10和4两个圈。这种莫名其妙的关联，如果和公因子无关就没有天理了。
7. 所以看起来圈的个数等于n和k的公因子。这不难证明。因为实际上k mod N, 2k mod N, 3k mod N, 4k mod N, … 将会遍历所有m*gcd(N, k)。这样说太抽象的话，我们将整个数组重复无数次，然后从0开始，将index每次加k，在这个无限长的数组里面进行访问。记d=gcd(N,k)。在最终回到同一元素之前，我们需要访问 (k * N / d) / k = N / d个元素，这N/d个元素中的任意两个不应该指向原数组中的同一个位置，否则这两个元素之间的距离就是一个小于 k * N / d的k和N的公倍数，违反最小公倍数的定义。如果两个圈从0…d-1中的不同位置开始，那么我们会得到两个不同的循环——如果你将数列列出来，则很容易理解，我做一个简图如下(N=10, k=4)：
8. 于是我们可以知道，我们只要顺序地走过这些圈圈就可以了。于是可以得到神代码如下
现在回过来检查一下我们的主旨：为什么我们倾向于分析。
一、从上面解答可以看出，分析的过程是基本可以说出来的，是逻辑的。
二、由此，分析的能力是可以训练的，规约的能力只能通过极大量的题海来增强。
三、分析能力更为泛用，它的作用不仅仅是在面试中做几道题，而且还可以在你面对更复杂问题的时候提供帮助。
本来还想总结点别的，不过打脸来得是挺快的，看我下一篇有关divide and conquer的博文就知道。reverse三(四…N)次的方法应该作为一种基本方法来记忆，就是：
在线性时间内我们可以in place交换数组的任意两个子数组。
之前我们说到分析的方法比规约要好，因为规约基于灵光一闪，分析是脚踏实地可以练习。那这次为什么我又要回来吹规约了呢？
因为规约有的时候可以给你提供一个新的视角看问题。
举个栗子——我们都十分熟悉的最大子段和问题，和leetcode上的buy and sell stock I，其实是相互可以规约的。不信？你肯定信了⋯⋯
对于一个给定数组，求其最大连续子段和，有一种很玄妙的O(N)方法，第一次看到的人都要花一小段时间去理解——为什么加着加着加成负数就要归零重来？
假设我们有数组A
1 2 -2 4 -3 -3 6 1 -2
我们将问题转化一下：我们先用O(N)时间和O(N)空间（其实是不必要的，我们稍后可以简化这一过程），计算出prefix sum数组：
1 3 1 5 2 -1 5 6 3
很明显，prefix sum的两个点之差，就是原数组中的子段和。那么如何通过这个数组求出最大子段和？那就是求max(A[j] – A[i]) (j >=i)。这个问题，你们解过buy and sell stock的都知道了，很好解，只要从左边开始遍历，纪录当前最小值，然后每遇到一个新元素，减去这个最小值，update最大受益并update最小值即可。于是我们将最大子段和问题规约到了一个更可靠的问题上——b&s stock是一个可分析的问题。
接下来我们会发现我们之前这段算法中，有一项非必须的工作：
计算prefix sum的时候，我们其实不需要维护一个数组，只要维护当前的prefix最小值和当前最小值即可。
看到这里，我们应该开始感到怀疑：我们是不是就要回归到最大子段和的原始做法了呢？
在prefix sum算法中，如果我们注意到在最小prefix sum之前的公有部分都可以省略，我们就可以去掉这部分的加和，从而回归最大子段和的“原始做法”（到这里我已经开始怀疑最大子段和的原始推导是什么样子了）
是的。在原始做法中之所以我们每次遇到负子段和，我们就／才跳到当前index的下一个位置重新开始，正是因为我们看到了一个更小的prefix sum。否则，我们就应该继续，因为我们始终要用当前prefix和减去当前最小子段和。
这两个做法很简单地互相转化。
那么，我们从这个规约中能学习到什么？
一、规约成其他问题有可能会对我们理解问题有相当大的帮助；
二、prefix sum和moving window有着千丝万缕的联系，在遇到类似问题的时候不妨试着转化一下。
最后出一道题，在这里已经答案很明显的题目：
给定一个数组，求其中最接近0的连续子段和。
再来一个：
给定一个数组，求最长的和不大于k的连续子段和。
FPI通讯五：简化之恶——largest rectangle under histogram
这个问题我两个月前是这么讲的：『找个例子就好了，先找到最后一个上升沿中的较小元素，然后把它后面比它大的最小元素换到它的位置上，最后reverse后面的递减序列』。
好的好的，这个描述还算精准，但是如何解释我们要将一串相等的序列定义为递减的？上面的描述是How，而不是Why。How当然有意义，而且相当有意义，它是我们将算法idea转化为代码的重要一步，但是如果我们死记硬背How，三个月后我保证你不再记得这个算法怎么做。比如说，你还记得KMP怎么写吗？
那么什么是这个例子的Why？
这里有两个直觉上的方向。
一是要找一个元素，让它和后面的某个比它大的元素交换，使得数组变得更大（不严谨，但是我们后面会补全）
二是这个元素要尽量靠后，应该是最后一个可以完成这个操作的元素。
由二，我们可以接着想，尽量靠后这是怎么个情况。也就是说后面的所有元素都不可能完成一个和再其后元素交换的操作，使得数组字典序变大，更宽泛且精确地讲，我们需要找到一个元素，其后的序列内部无论如何变换，都不可能使得字典序变大，而加上这个元素之后却可以实现。<—-记住这个
依照这个准则，我们不难看出，333333这种序列，是一个坏序列，它无论如何折腾，都不可能使得字典序变大，于是这种有相等的元素的边界输入，也就迎刃而解了。
然后我们也应该可以看出，8632这种递减的序列，也怎么折腾都大不了。它们的共同特点是，字典序已经最大了。
也就是说，一开始的叙述可以refine为：找到数组尾部的一个最长的字典序最大的序列，然后让它和前面一个元素k发生点什么。
发生点什么呢？
我们要让数组变大，所以肯定要换一个稍微大点的元素到k这里。然后我们要让结果尽量小，所以我们要把后面的序列重新恢复为字典序最小，也就是reverse一下就能完成。
这里的叙述并不严谨，但是我的意图不在于此。精确的证明可以留给大家思考。（比如为什么一定不会需要更前面的元素有所改变）
