LeetCode总结 -- 树的求和篇

树的求和属于树的题目中比较常见的，因为可以有几种变体，灵活度比较高，也可以考察到对于树的数据结构和递归的理解。一般来说这些题目就不用考虑非递归的解法了（虽然其实道理是跟LeetCode总结 -- 树的遍历篇一样的，只要掌握了应该没问题哈）。 LeetCode中关于树的求和有以下题目：
Path Sum
Path Sum II
Sum Root to Leaf Numbers
Binary Tree Maximum Path Sum

我们先来看看最常见的题目Path Sum。这道题是判断是否存在从根到叶子的路径和跟给定sum相同。树的题目基本都是用递归来解决，主要考虑两个问题：

1）如何把问题分治成子问题给左子树和右子树。这里就是看看左子树和右子树有没有存在和是sum减去当前结点值得路径，只要有一个存在，那么当前结点就存在路径。

2）考虑结束条件是什么。这里的结束条件一个是如果当前节点是空的，则返回false。另一个如果是叶子，那么如果剩余的sum等于当前叶子的值，则找到满足条件的路径，返回true。

想清楚上面两个问题，那么实现起来就是一次树的遍历，按照刚才的分析用参数或者返回值传递需要维护的值，然后按照递归条件和结束条件进行返回即可。算法的时间复杂度是一次遍历O(n)，空间复杂度是栈的大小O(logn)。

对于Path Sum II，其实思路和Path Sum是完全一样的，只是需要输出所有路径，所以需要数据结构来维护路径，添加两个参数，一个用来维护走到当前结点的路径，一个用来保存满足条件的所有路径，思路上递归条件和结束条件是完全一致的，空间上这里会依赖于结果的数量了。

Sum Root to Leaf Numbers这道题多了两个变化，一个是每一个结点相当于位上的值，而不是本身有权重，不过其实没有太大变化，每一层乘以10加上自己的值就可以了。另一个变化就是要把所有路径累加起来，这个其实就是递归条件要进行调整，Path Sum中是判断左右子树有一个找到满足要求的路径即可，而这里则是把左右子树的结果相加返回作为当前节点的累加结果即可。

变化比较大而且有点难度的是Binary Tree Maximum Path Sum，这道题目的路径要求不再是从根到叶子的路径，这个题目是把树完全看成一个无向图，然后寻找其中的路径。想起来就觉得比上面那种麻烦许多，不过仔细考虑会发现还是有章可循的，找到一个根节点最大路径，无非就是找到左子树最大路径，加上自己的值，再加上右子树的最大路径（这里左右子树的路径有可能不取，如果小于0的话）。我们要做的事情就是对于每个结点都做一次上面说的这个累加。而左子树最大路径和右子树最大路径跟Path Sum II思路是比较类似的，虽然不一定要到叶子节点，不过标准也很简单，有大于0的就取，如果走下去路径和小于0那么就不取。从分治的角度来看，左右子树的最大路径就是取自己的值加上Max(0，左子树最大路径，右子树最大路径)。这么一想也就不用考虑那么多细节了。而通过当前节点的最长路径则是自己的值+Max(0，左子树最大路径)+Max(0，右子树最大路径)。所以整个算法就是维护这两个量，一个是自己加上左或者右子树最大路径作为它的父节点考虑的中间量，另一个就是自己加上左再加上右作为自己最大路径。具体的实现可以参见Binary Tree Maximum Path Sum。

这篇总结主要讲了LeetCode中关于树的求和的题目。总体来说，求和路径有以下三种：（1）根到叶子结点的路径；（2）父结点沿着子结点往下的路径；（3）任意结点到任意结点（也就是看成无向图）。这几种路径方式在面试中经常灵活变化，不同的路径方式处理题目的方法也会略有不同，不过最复杂也就是Binary Tree Maximum Path Sum这种路径方式，只要考虑清楚仍然是一次递归遍历的问题哈。

LeetCode总结 -- 一维数据合并篇

合并是一维数据结构中很常见的操作， 通常是排序， 分布式算法中的子操作。 这篇总结主要介绍LeetCode中关于合并的几个题目：
Merge Two Sorted Lists
Merge Sorted Array
Sort List
Merge k Sorted Lists

我们先来看看两个有序一维数据的合并， 这里主要是要介绍链表的合并操作， 不过因为一维数组的合并也比较简单， 而且与链表有比较性， 就顺便在这里列举一下。 Merge Two Sorted Lists就是要求合并两个有序链表， 一般来说合并的思路就是以一个为主参考， 然后逐项比较， 如果较小元素在参考链表中， 则继续前进， 否则把结点插入参考链表中， 前进另一个链表， 最后如果另一个链表还没到头就直接接过来就可以了， 思路和实现都比较简单， 最好力求一遍过哈。 Merge Sorted Array也是一样的思路， 只是数据结构换成了一维数组， 所以插入操作比链表要麻烦一些， 这里相当于从尾部开始， 然后数字一个个按照位置填入， 插入操作在这里就不明显了。 可以看出虽然思路近似， 但是数据结构不同， 因为操作不同， 实现细节还是比较不一样的， 都得熟练掌握哈。
有了上面合并两个链表（或者数组）我们就可以进行归并排序了， 也就是Sort List这道题目。 对于链表， 用Merge Two Sorted Lists作为合并的子操作， 然后用归并排序的递归进行分割合并就可以了， 这里就不说排序的具体细节了， 会有专门的排序总结篇哈。

最后我们来说说最重要的也是最实用的一个题目Merge k Sorted Lists。 为什么说他实用是因为现在分布式系统很多， 而且也很强调MapReduce或者Hadoop的技术， 这个题目就是分布式计算的一个常见操作。 比如说来自不同client的有序数据要在central server上面进行合并。 这个问题有两种做法：
第一种就是利用上面的Merge Two Sorted Lists对k个链表先进行两两合并， 然后再上一层继续两两合并， 直到合成一个链表。 根据Merge k Sorted Lists中的分析， 时间复杂度是O（nklogk）, 空间复杂度是O（logk）。
上面这种做法是利用分治然后进行合并的方法， 接下来这个方法用到了堆的数据结构。 思路是维护一个大小为k的堆， 每次取堆顶的最小元素放到结果中，然后读取该元素对应的链表的下一个元素放入堆中。 因为每个链表是有序的， 每次又是去当前k个元素中最小的， 所以当所有链表都读完时结束，这个时候所有元素按从小到大放在结果链表中。 这个算法每个元素要读取一次，即k*n次，然后每次读取元素要把新元素插入堆中要O（logk）的复杂度，所以复杂度是O(nklogk)， 跟第一种方法是一样的。
两种方法不同的数据结构和类型， 都非常具有代表性， 个人觉得都很有意思哈。

合并算是链表中比较典型的操作， 也能够连续地问出比较连贯的一些题目， 扩展性非常好， 既可以考察基本数据结构的操作， 又可以看看对于算法和更多数据结构的理解， 是一个不错的面试话题。

LeetCode总结 -- 数值计算篇

数值计算在工业界是非常实用而且常见的具体问题, 所以在面试中出现频率非常高, 几乎可以说是必考题目。 LeetCode中关于数值运算的有以下题目：
Palindrome Number
Reverse Integer
Sqrt(x)
Pow(x, n)
Divide Two Integers
Max Points on a Line
在LeetCode中， 关于数值运算的题目分为三种类型， 下面将进行一一讲解。

第一种类型是最简单的， 就是对整数进行直接操作， 一般来说就是逐位操作， 比如反转， 比较等。 LeetCode中这类题目有Palindrome Number和Reverse Integer。 这类题目通常思路很清晰， 要注意的点就是对于边界情况的考虑， 对于数值而言， 主要问题是对于越界情况的考虑。 实际上越界问题是贯穿于所有数值计算题目的常见问题， 下面大多问题都会强调这点。
在Palindrome Number中因为只是进行判断， 并不需要修改数字， 所以没有越界问题。 思路比较简单， 就是每次取出最高位和最低位进行比较， 直到相遇或者出现违背条件（也就是不相等）即可返回。 对于Reverse Integer因为需要对数字进行反转， 所以需要注意反转后的数字可能会越界。 对于越界一般都是两种处理方法， 一种是返回最大（或者最小）数字， 一种则是抛出异常， 这个可以跟面试官讨论， 一般来说， 面试只要简单的返回最大最小或者dummy数字就可以了， 但是处理和检查这种corner case（也就是越界）的想法一定要有和跟面试官讨论。

第二种题型是算术运算的题目， 比如乘除法， 阶乘， 开方等， LeetCode中这类题目有Sqrt(x)， Pow(x, n)和Divide Two Integers。 这种题目有时候看似复杂， 其实还是有几个比较通用的解法的， 下面主要介绍三种方法：
（1）二分法。 二分法是数值计算中很常用和易懂的方法。 基本思路是对于所求运算进行对半切割， 有时是排除一半， 有时则是得到可重复使用的历史数据。 Sqrt(x)就是属于每次排除一半的类型， 对于要求的开方数字进行猜测， 如果大于目标， 则切去大的一半， 否则切去大的一半， 原理跟二分查找是一样的。 Pow(x, n)则是属于重复利用数据的类型， 因为x的n次方实际上是两个x的n/2次方相乘， 所以我们只需要递归一次求出当前x的当前指数的1/2次方， 然后两个相乘就可以最后结果。 二分法很明显都是每次解决一半， 所以时间复杂度通常是O（logn）量级的。
（2）牛顿法。 这种方法可以说主要是数学方法， 不了解原理的朋友可以先看看牛顿法-维基百科。 Sqrt(x)就非常适合用牛顿法来解决， 因为它的递推式中的项都比较简单。 Pow(x, n)当然原理上也可以用牛顿法解答， 但是因为他的递推式中有项是进行x的开n次方的， 这个计算代价也是相当大的， 如果为了求x的n次方而去每一步求开n次方就没有太大实际意义了， 所以对于这种题我们一般不用牛顿法。
（3）位移法。 这种方法主要基于任何一个整数可以表示成以2的幂为底的一组基的线性组合， 对一个整数进行位数次迭代求解， 因为复杂度是位数的数量， 所以也跟二分法一样是O（logn）量级的。 Pow(x, n)和Divide Two Integers就是比较典型可以用这种方法解决的题目。 对于Pow(x, n)可以把n分解成位， 每次左移恰好是当前数的平方， 所以进行位数次迭代后即可以得到结果， 代码中很大的篇幅都是在处理越界问题， 而关于逐位迭代代码却很简短。 Divide Two Integers同样把结果分解成位， 每次对除数进行位移并且减去对应的除数来确定每一位上的结果。 这种方法可能理解起来没有二分法那么直观， 还是要消化一下哈。

第三种题目是解析几何的题目， 一般来说解析几何题目的模型都比较复杂， 而且实现细节比较多， 在面试中并不常见， LeetCode中也只有Max Points on a Line是属于这种题型。 这种题目没有什么通法， 主要就是要理清数学和几何模型， 比如Max Points on a Line中主要是理解判断点在直线的判断公式， 然后进行迭代实现。 实现细节还是比较多的， 需要对一些边界情况仔细考虑。

这篇总结主要列举了LeetCode中关于数值计算的题目， 介绍了这类问题的主要考点（比如越界判断）和常用的几种实用方法， 总体感觉这类问题是在面试中比较难很快写对的题目， 因为有一些边界情况和数值实现的细节。 因为出现频率很高， 还是需要对这类题目重点练习哈。

LeetCode总结 -- kSum篇

这篇总结主要介绍LeetCode中几道关于求kSum的题目， 主要要求是在数组中寻找k个数的和能否达到目标值。 LeetCode关于kSum的主要题目有：
Two Sum
3Sum
3Sum Closest
4Sum
首先从Two Sum开始， 这道题目提供了后面k>2的题目的基本思路， 也是最常考到的题目（亚马逊的面试对这道题算是情有独钟了）。 主要有两种思路， 一种是利用哈希表对元素的出现进行记录，然后进来新元素时看看能不能与已有元素配成target， 如果哈希表的访问是常量操作，这种算法复杂度是O(n)。 另一种思路则是先对数组进行排序， 然后利用夹逼的方法找出满足条件的pair， 算法的复杂度是O(nlogn)。 两种方法都比brute force的O(n^2)要优， 具体可以参见题目Two Sum的具体分析。 因为这道题模型简单， 但是可以考核到哈希表等基本数据结构和排序等基本算法， 所以是面试中的常客。
接下来是3Sum和3Sum Closest， 3Sum是使用Two Sum的第二种方法作为子操作， 然后循环每个元素， 寻找剩下的元素满足条件的pair即可。 3Sum Closest和3Sum很类似， 只是要多维护一个最小的diff， 保存和target最近的值。 算法的复杂度是O(n^2)， 这道题使用Two Sum的第一种方法并不合适， 因为当出现元素重复时用哈希表就不是很方便了。
最后是4Sum， 这道题的比较优的解法是用求解一般kSum的解法进行层层二分， 然后用Two Sum结合起来， 基本思路是这样， 实现细节还是比较复杂的， 即使是4Sum都比较复杂了， 所以面试中难度和实现细节也就到这了， kSum这种一般性的问题只需要知道思路就可以满足面试要求了哈。

LeetCode总结 -- 树的遍历篇

遍历树的数据结构中最常见的操作， 可以说大部分关于树的题目都是围绕遍历进行变体来解决的。 一般来说面试中遇到树的题目是用递归来解决的， 不过如果直接考察遍历， 那么一般递归的解法就过于简单了， 面试官一般还会问更多问题， 比如非递归实现， 或者空间复杂度分析以及能否优化等等。 树的遍历题目在LeetCode中有以下几个：
Binary Tree Inorder Traversal
Binary Tree Preorder Traversal
Binary Tree Postorder Traversal
Binary Tree Level Order Traversal
Binary Tree Level Order Traversal II
Binary Tree Zigzag Level Order Traversal

树的遍历基本上分成两种类型， 下面分别介绍：

第一种是以图的深度优先搜索为原型的遍历， 可以是中序， 先序和后序三种方式， 不过结点遍历的方式是相同的， 只是访问的时间点不同而已， 对应于Binary Tree Inorder Traversal， Binary Tree Preorder Traversal和Binary Tree Postorder Traversal这三道题目。
在这种类型中， 递归的实现方式是非常简单的， 只需要递归左右结点， 直到结点为空作为结束条件就可以， 哪种序就取决于你访问结点的时间。
不过一般这不能满足面试官的要求， 可能会接着问能不能用非递归实现一下， 这个说起来比较简单， 其实就是用一个栈手动模拟递归的过程， Binary Tree Inorder Traversal和Binary Tree Preorder Traversal比较简单， 用一个栈来保存前驱的分支结点（相当于图的深度搜索的栈）， 然后用一个结点来记录当前结点就可以了。 而Binary Tree Postorder Traversal则比较复杂一些， 保存栈和结点之后还得根据情况来判断当前应该走的方向（往左， 往右或者回溯）。 这里就不列举代码细节， 有兴趣的朋友可以看看具体题目的分析， 会更详细一些。
有时候非递归还是不能满足面试官， 还会问一问， 上面的做法时间和空间复杂度是多少。 我们知道， 正常遍历时间复杂度是O(n), 而空间复杂度是则是递归栈（或者自己维护的栈）的大小， 也就是O(logn)。 好了， 他会问能不能够在常量空间内解决树的遍历问题呢？ 确实还真可以， 这里就要介绍Morris Traversal的方法。 Morris遍历方法用了线索二叉树，这个方法不需要为每个节点额外分配指针指向其前驱和后继结点，而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。 这样就节省了需要用栈来记录前驱或者后继结点的额外空间， 所以可以达到O（1）的空间复杂度。 不过这种方法有一个问题就是会暂时性的改动树的结构， 这在程序设计中并不是很好的习惯， 这些在面试中都可以和面试官讨论， 一般来说问到这里不会需要进行Morris遍历方法的代码实现了， 只需要知道这种方法和他的主要优劣势就可以了， 有兴趣知道实现的朋友可以看看具体题目的实现哈。

另一种是以图的广度优先搜索为原型的， 在树中称为层序遍历， LeetCode中有三种自顶向下层序， 自底向上层序和锯齿层序遍历， 对应于Binary Tree Level Order Traversal， Binary Tree Level Order Traversal II和Binary Tree Zigzag Level Order Traversal。
Binary Tree Level Order Traversal其实比较简单， 代码基本就是图的广度优先搜索， 思路就是维护一个队列存储上一层的结点， 逐层访问。 而Binary Tree Level Order Traversal II则要从最后一层倒序访问上来， 这个我没有想到太好的方法， 现在的实现就是把Binary Tree Level Order Traversal得到的层放入数据结构然后reverse过来， 确实没有太大的考核意义。 至于Binary Tree Zigzag Level Order Traversal因为每一层访问顺序有所改变， 而且是每次都反转顺序， 这让我们想到栈的数据结构， 所以这里不用队列对于上层结点进行， 而改用栈来保存， 就可以满足每层反转访问顺序的要求了。

树的遍历是一个老生常谈的题目， 不过仔细研究还是有一些考点的， 对于考查对数据结构和算法的理解还是不错的， 所以简单的东西也得重视哈。

LeetCode总结 -- 一维动态规划篇

这篇文章的主题是动态规划， 主要介绍LeetCode中一维动态规划的题目， 列表如下：
Climbing Stairs
Decode Ways
Unique Binary Search Trees
Maximum Subarray
Maximum Product Subarray
Best Time to Buy and Sell Stock

在介绍上述具体题目之前, 我们先说说动态规划的通常思路。 动态规划是一种算法思路（注意这里不要和递归混淆， 事实上递归和迭代只是两种不同的实现方法， 并不是算法）， 用一句话来总结就是， 动态规划是利用存储历史信息使得未来需要历史信息时不需要重新计 算， 从而达到降低时间复杂度， 用空间复杂度换取时间复杂度目的的方法。 我个人喜欢把动态规划分为以下几步：
1） 确定递推量。 这一步需要确定递推过程中要保留的历史信息数量和具体含义， 同时也会定下动态规划的维度；
2） 推导递推式。 根据确定的递推量， 得到如何利用存储的历史信息在有效时间（通常是常量或者线性时间）内得到当前的信息结果；
3） 计算初始条件。 有了递推式之后， 我们只需要计算初始条件， 就可以根据递推式得到我们想要的结果了。 通常初始条件都是比较简单的情况， 一般来说直接赋值即可；
4） （可选）考虑存储历史信息的空间维度。 这一步是基于对算法优化的考虑， 一般来说几维动态规划我们就用几维的存储空间是肯定可以实现的。 但是有时我们对于历史信息的要求不高， 比如这一步只需要用到上一步的历史信息， 而不需要更早的了， 那么我们可以只存储每一步的历史信息， 每步覆盖上一步的信息， 这样便可以少一维的存储空间， 从而优化算法的空间复杂度。
动态规划的时间复杂度是O(（维度）×（每步获取当前值所用的时间复杂度））。 基本上按照上面的思路， 动态规划的题目都可以解决， 不过最难的一般是在确定递推量， 一个好的递推量可以使得动态规划的时间复杂度尽量低。

接下来我们来看看具体题目， 一维动态规划的题目主要分成两类：

（1） 第一种是比较简单的， 直接地按照上面步骤就可以解出来的， 确定递归量， 然后按递归式迭代就可以得到。 这种类型的题目是： Climbing Stairs， Decode Ways和Unique Binary Search Trees。
Climbing Stairs中递推量很清晰， 就是爬到i级楼梯有多少种可行爬法。 而对于递推式我们可以看出， 要到达i级楼梯， 必须通过i－1级或者i－2级（以为只能爬一级或者两级）， 如此可以得到到达i级楼梯的方式有f（i）=f(i-1)+f(i-2)种， 这样递推式也就出来了。 而初始条件则是一级楼梯是一种解法， 两级楼梯是两种解法（2或者11）。 有了这些接下来递推到n级楼梯返回即可， 空间复杂度是O（n)(一维动态规划乘以每一步的常量操作）。 空间上我们发现每一步，只需要前两步的历史信息， 所以我们不需要存储所有历史信息， 只需要保存前两步， 然后迭代替换就可以了， 所以空间复杂度是O（2）=O（1）， 这里对应于上面的第四步。
Decode Ways中递推量也是类似的到达第i个字符可解析方式的数量， 递推式比Climbing Stairs稍微复杂一些， 要分情况讨论， 主要对于自己和前面一位组成数字的不同要分别处理一下， 这里就不列出来的，大家可以看看Decode Ways -- LeetCode。 虽然是分情况，不过每种情况也是可以常量时间更新信息的， 初始条件依然是非常简单的case， 空间上也是只需要保存前两步的信息， 所以时间和空间复杂度跟Climbing Stairs都是一样的。
Unique Binary Search Trees思路还是类似的， 递推式是稍有不同， 按左右子树划分然后进行累加， 最后归结为卡特兰数的模型。 这个问题仍然是一维动态规划， 但是求解单步信息时是一个线性操作， 所以时间复杂度是O（n^2)。 而空间上因为每一步都需要前面每一步的所有信息， 所以也无法优化， 是O(n)。

（2） 接下来我们介绍第二种类型， 虽然也是一维动态规划， 但是区别在于这类题目需要维护两个递推量， 所以思路上有一点技巧。 不过还是比较有通法的， 我通常把这种方法称为”局部最优和全局最优解法“。 这种方法中我们通常维护两个量， 一个是到目前为止最好的结果信息（全局最优）， 另一个必须包含新加进来的元素的最好的结果信息（局部最优）， 然后还是推导递推式， 计算初始条件， 跟动态规划的通常思路一样了。 Maximum Subarray和Best Time to Buy and Sell Stock就是这种类型的题目。
Maximum Subarray中对于递推量我们维护两个，一个是到目前为止最好的子数组， 而另一个量则是加入当前元素之后， 包含当前元素的最好的子数组， 最终我们是看全局最优的变量的最优值， 而局部最优却是我们在递推过程中维护全局最优所需要的。 递推式还是有点技巧， 第i+1步表达式如下：
  local[i+1]=Math.max(A[i], local[i]+A[i])，就是局部最优是一定要包含当前元素，所以不然就是上 一步的局部最优local[i]+当前元素A[i]（因为local[i]一定包含第i个元素，所以不违反条件），但是如果local[i]是负的，那么加上他就不如不需要的，所以不然就是直接用A[i]；
  global[i+1]=Math(local[i+1],global[i])，有了当前一步的局部最优，那么全局最优就是当前的局部最优或者还是原来的全局最优（所有情况都会被涵盖进来，因为最优的解如果不包含当前元素，那么前面会被维护在全局最优里面，如果包含当前元素，那么就是这个局部最优）。
初始条件都是0或者第一个元素既可以了， 一遍扫过来， 每次迭代更新两个量（都是常量时间）， 所以时间是O(n)。 空间上可以看出只需要上一步的信息， 所以只需要保存上一步的全局最优和局部最优即可， 复杂度是O（2）=O(1)。
Maximum Product Subarray的题目模型跟Maximum Subarray比较类似，只是把加法改成了乘法，思路还是用这个方法，只是注意这里两个负数相乘可能得到更优的乘法结果，所以我们在维护局部最优时把局部的最小值也存下来，这样遇到负数时就可以得到也许更大的乘积。其他就跟Maximum Subarray是一致的了。
Best Time to Buy and Sell Stock跟Maximum Subarray是完全一样的， 也是维护两个量， 一个是到目前为止最好的交易（全局最优）， 另一个是在当前一天卖出的最佳交易（局部最优）， 其他步骤也是一样的， 这里就不列出来了。

可以看出， 上面五道一维动态规划的题目都是按照我前面列出的四个步骤进行求解的， 事实上所有动态规划题目都是按照这个基本思路来的。 掌握了套路之后就是看对具体问题要维护的递推量的选择了，这个个人感觉还是比较靠经验的， 熟能生巧。

LeetCode总结 -- 二分查找篇

二分查找算法虽然简单，但面试中也比较常见，经常用来在有序的数列查找某个特定的位置。在LeetCode用到此算法的主要题目有：
Search Insert Position
Search for a Range
Sqrt(x)
Search a 2D Matrix
Search in Rotated Sorted Array
Search in Rotated Sorted Array II

这类题目基本可以分为如下四种题型：
1. Search Insert Position和Search for a Range是考察二分查找的基本用法。基本思路是每次取中间，如果等于目标即返回，否则根据大小关系切去一半，因此时间复杂度是O(logn)，空间复杂度O(1)。以Search Insert Position为例，其关键代码写法如下：

    int l = 0;
    int r = A.length-1;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(A[mid]==target)
            return mid;
        if(A[mid]<target)
            l = mid+1;
        else
            r = mid-1;
    }
    return l;

这样当循环停下来时，如果不是正好找到target，l指向的元素恰好大于target，r指向的元素恰好小于target，这里l和r可能越界，不过如果越界就说明大于（小于）target并且是最大（最小）。Search for a Range这道题能更好的解释这一点。其思路是先用二分查找找到其中一个target，然后再往左右找到target的边缘。我们主要看找边缘（往后找）的代码：

    int newL = m;
    int newR = A.length-1;
    while(newL<=newR)
    {
        int newM=(newL+newR)/2;
        if(A[newM]==target)
        {
            newL = newM+1;
        }
        else
        {
            newR = newM-1;
        }            
    }
    res[1]=newR;

我们的目标是在后面找到target的右边界，因为左边界已经等于target，所以判断条件是相等则向右看，大于则向左看，根据上面说的，循环停下来时，l指向的元素应该恰好大于target，r指向的元素应该等于target，所以此时的r正是我们想要的。向前找边缘也同理。

2. Sqrt(x)是数值处理的题目，但同时也可以用二分查找的思想来解决。因为我们知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，直到左界和右界相遇。算法的时间复杂度是O(logx)，空间复杂度是O(1)。这里同样是考察二分查找的基本用法。代码如下：

public int sqrt(int x) {
    if(x<0) return -1;
    if(x==0) return 0;
    int l=1;
    int r=x/2+1;
    while(l<=r)
    {
        int m = (l+r)/2;
        if(m<=x/m && x/(m+1)<m+1)
            return m;
        if(x/m<m)
        {
            r = m-1;
        }
        else
        {
            l = m+1;
        }
    }
    return 0;
}

这里要注意，这里判断相等的条件不是简单的 m == x/m, 而是 m<=x/m && x/(m+1)<m+1, 这是因为输出是整型，sqrt(14)=3 但 3 != 14/3. 所以我们需要一个范围框住结果。另外根据二分查找算法的特性，如果不能正好m==x/m停下，那么r指向的数字将正好是结果取整的值。所以我们也可以这样写：

public int sqrt(int x) {
    if(x<0) return -1;
    if(x==0) return 0;
    int l=1;
    int r=x/2+1;
    while(l<=r)
    {
        int m = (l+r)/2;
        if(m==x/m )
            return m;
        if(x/m<m)
        {
            r = m-1;
        }
        else
        {
            l = m+1;
        }
    }
    return r;
}

3. Search a 2D Matrix是二分查找算法的多维应用，通过观察不难发现，输入的矩阵行内有序并且行间有序，所以查找只需要先按行查找，定位出在哪一行之后再进行列查找即可，两次二分查找，时间复杂度是O(logm+logn)，空间上只需两个辅助变量，因而是O(1)，这里不再赘述。

4. Search in Rotated Sorted Array和Search in Rotated Sorted Array II算是二分查找算法的一个变体。在Search in Rotated Sorted Array中，乍一看感觉数组已经不是有序的了，也就无法用二分查找算法，但仔细分析一下会发现，因为只rotate了一次，如果二分一下，总有一半是有序的，而且和另一半无区间重叠，我们只需要检查有序的一半的前后两个元素就可以确定target可能在哪一半。具体来说，假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回；
（2）如果A[m]<A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。
（3）如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。
根据以上方法，每次我们都可以切掉一半的数据，所以算法的时间复杂度是O(logn)，空间复杂度是O(1)。

Search in Rotated Sorted Array II中array有重复元素，按照刚刚的思路，二分之后虽然一半是有序的，但我们会遇到中间和边缘相等的情况，我们就丢失了哪边有序的信息，因为哪边都有可能是有序的结果。假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，这样的我们判断左边缘和中心的时候都是3，如果我们要寻找1或者2，我们并不知道应该跳向哪一半。解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而他就在最后一个）就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)。

总体来说，二分查找算法理解起来并不算难，但在实际面试的过程中可能会出现各种变体，如何灵活的运用才是制胜的关键。我们要抓住“有序”的特点，一旦发现输入有“有序”的特点，我们就可以考虑是否可以运用二分查找算法来解决该问题。

4Sum -- LeetCode

原题链接: http://oj.leetcode.com/problems/4sum/
这道题要求跟3Sum差不多，只是需求扩展到四个的数字的和了。我们还是可以按照3Sum中的解法，只是在外面套一层循环，相当于求n次3Sum。我们知道3Sum的时间复杂度是O(n^2)，所以如果这样解的总时间复杂度是O(n^3)。代码如下：

public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(num==null||num.length==0)
        return res;
    Arrays.sort(num);
    for(int i=num.length-1;i>2;i--)
    {
        if(i==num.length-1 || num[i]!=num[i+1])
        {
            ArrayList<ArrayList<Integer>> curRes = threeSum(num,i-1,target-num[i]);
            for(int j=0;j<curRes.size();j++)
            {
                curRes.get(j).add(num[i]);
            }
            res.addAll(curRes);
        }
    }
    return res;        
}
private ArrayList<ArrayList<Integer>> threeSum(int[] num, int end, int target)
{
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    for(int i=end;i>1;i--)
    {
        if(i==end || num[i]!=num[i+1])
        {
            ArrayList<ArrayList<Integer>> curRes = twoSum(num,i-1,target-num[i]);
            for(int j=0;j<curRes.size();j++)
            {
                curRes.get(j).add(num[i]);
            }
            res.addAll(curRes);
        }
    }
    return res;
}
private ArrayList<ArrayList<Integer>> twoSum(int[] num, int end, int target)
{
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    int l=0;
    int r=end;
    while(l<r)
    {
        if(num[l]+num[r]==target)
        {
            ArrayList<Integer> item = new ArrayList<Integer>();
            item.add(num[l]);
            item.add(num[r]);
            res.add(item);
            l++;
            r--;
            while(l<r&&num[l]==num[l-1])
                l++;
            while(l<r&&num[r]==num[r+1])
                r--;
        }
        else if(num[l]+num[r]>target)
        {
            r--;
        }
        else
        {
            l++;
        }
    }
    return res;
}

上述这种方法比较直接，根据3Sum的结果很容易进行推广。那么时间复杂度能不能更好呢？其实我们可以考虑用二分法的思路，如果把所有的两两pair都求出来，然后再进行一次Two Sum的匹配，我们知道Two Sum是一个排序加上一个线性的操作，并且把所有pair的数量是O((n-1)+(n-2)+...+1)=O(n(n-1)/2)=O(n^2)。所以对O(n^2)的排序如果不用特殊线性排序算法是O(n^2*log(n^2))=O(n^2*2logn)=O(n^2*logn)，算法复杂度比上一个方法的O(n^3)是有提高的。
思路虽然明确，不过细节上会多很多情况要处理。首先，我们要对每一个pair建一个数据结构来存储元素的值和对应的index，这样做是为了后面当找到合适的两对pair相加能得到target值时看看他们是否有重叠的index，如果有说明它们不是合法的一个结果，因为不是四个不同的元素。接下来我们还得对这些pair进行排序，所以要给pair定义comparable的函数。最后，当进行Two Sum的匹配时因为pair不再是一个值，所以不能像Two Sum中那样直接跳过相同的，每一组都得进行查看，这样就会出现重复的情况，所以我们还得给每一个四个元素组成的tuple定义hashcode和相等函数，以便可以把当前求得的结果放在一个HashSet里面，这样得到新结果如果是重复的就不加入结果集了。
代码如下：

public class Node
{
    int index;
    int value;
    public Node(int index, int value)
    {
        this.index = index;
        this.value = value;
    }
}
public class Pair
{
    Node[] nodes;
    public Pair(Node n1, Node n2)
    {
        nodes = new Node[2];
        nodes[0] = n1;
        nodes[1] = n2;
    }
    public int getSum()
    {
        return nodes[0].value+nodes[1].value;
    }
}
public class Tuple
{
    ArrayList<Integer> num;
    public Tuple(ArrayList<Integer> num)
    {
        this.num = new ArrayList<Integer>(num);
        Collections.sort(this.num);
    }
    public int hashCode() {
        int hashcode = 5;
        for(int i=0;i<this.num.size();i++)
        {
            hashcode = 31*hashcode + this.num.get(i);
        }
        return hashcode;
    }
    public boolean equals(Object obj) {
        if (obj == null)
            return false;
        if (obj == this)
            return true;
        if (!(obj instanceof Tuple))
            return false;
        Tuple rhs = (Tuple) obj;
        for(int i=0;i<this.num.size();i++)
        {
            if(!this.num.get(i).equals(rhs.num.get(i)))
            {
                return false;
            }
        }            
        return true;
    }
}
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
    ArrayList<Pair> pairs = getPairs(num);
    Comparator<Pair> pairComparator = new Comparator<Pair>(){
        @Override
        public int compare(Pair p1, Pair p2){
            return p1.getSum()-p2.getSum();
        }
    };
    Collections.sort(pairs, pairComparator);
    return twoSum(pairs, target);
}
private ArrayList<Pair> getPairs(int[] num)
{
    ArrayList<Pair> res = new ArrayList<Pair>();
    for(int i=0;i<num.length-1;i++)
    {
        Node n1 = new Node(i,num[i]);
        for(int j=i+1;j<num.length;j++)
        {
            Node n2 = new Node(j,num[j]);
            Pair pair = new Pair(n1,n2);
            res.add(pair);
        }
    }
    return res;
}
private ArrayList<ArrayList<Integer>> twoSum(ArrayList<Pair> pairs, int target){
    HashSet<Tuple> hashSet = new HashSet<Tuple>();
    int l = 0;
    int r = pairs.size()-1;
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    while(l<r){
        if(pairs.get(l).getSum()+pairs.get(r).getSum()==target)
        {
            int lEnd = l;
            int rEnd = r;
            while(lEnd<rEnd && pairs.get(lEnd).getSum()==pairs.get(lEnd+1).getSum())
            {
                lEnd++;
            }
            while(lEnd<rEnd && pairs.get(rEnd).getSum()==pairs.get(rEnd-1).getSum())
            {
                rEnd--;
            }
            for(int i=l;i<=lEnd;i++)
            {
                for(int j=r;j>=rEnd;j--)
                {
                    if(check(pairs.get(i),pairs.get(j)))
                    {
                        ArrayList<Integer> item = new ArrayList<Integer>();
                        item.add(pairs.get(i).nodes[0].value);
                        item.add(pairs.get(i).nodes[1].value);
                        item.add(pairs.get(j).nodes[0].value);
                        item.add(pairs.get(j).nodes[1].value);
                        //Collections.sort(item);
                        Tuple tuple = new Tuple(item);
                        if(!hashSet.contains(tuple))
                        {
                            hashSet.add(tuple);
                            res.add(tuple.num);
                        }
                    }                        
                }
            }
            l = lEnd+1;
            r = rEnd-1;
        }
        else if(pairs.get(l).getSum()+pairs.get(r).getSum()>target)
        {
            r--;
        }
        else{
            l++;
        }
    }
    return res;
}
private boolean check(Pair p1, Pair p2)
{
    if(p1.nodes[0].index == p2.nodes[0].index || p1.nodes[0].index == p2.nodes[1].index)
        return false;
    if(p1.nodes[1].index == p2.nodes[0].index || p1.nodes[1].index == p2.nodes[1].index)
        return false;
    return true;
}

第二种方法比第一种方法时间上还是有提高的，其实这道题可以推广到k-Sum的问题，基本思想就是和第二种方法一样进行二分，然后两两结合，不过细节就非常复杂了（这点从上面的第二种解法就能看出来），所以不是很适合在面试中出现，有兴趣的朋友可以进一步思考或者搜索网上材料哈。

Unique Binary Search Trees II -- LeetCode

原题链接: http://oj.leetcode.com/problems/unique-binary-search-trees-ii/
这道题是求解所有可行的二叉查找树，从Unique Binary Search Trees中我们已经知道，可行的二叉查找树的数量是相应的卡特兰数，不是一个多项式时间的数量级，所以我们要求解所有的树，自然是不能多项式时间内完成的了。算法上还是用求解NP问题的方法来求解，也就是N-Queens中介绍的在循环中调用递归函数求解子问题。思路是每次一次选取一个结点为根，然后递归求解左右子树的所有结果，最后根据左右子树的返回的所有子树，依次选取然后接上（每个左边的子树跟所有右边的子树匹配，而每个右边的子树也要跟所有的左边子树匹配，总共有左右子树数量的乘积种情况），构造好之后作为当前树的结果返回。代码如下：

public ArrayList<TreeNode> generateTrees(int n) {
    return helper(1,n);
}
private ArrayList<TreeNode> helper(int left, int right)
{
    ArrayList<TreeNode> res = new ArrayList<TreeNode>();
    if(left>right)
    {
        res.add(null);
        return res;
    }
    for(int i=left;i<=right;i++)
    {
        ArrayList<TreeNode> leftList = helper(left,i-1);
        ArrayList<TreeNode> rightList = helper(i+1,right);
        for(int j=0;j<leftList.size();j++)
        {
            for(int k=0;k<rightList.size();k++)
            {
                TreeNode root = new TreeNode(i);
                root.left = leftList.get(j);
                root.right = rightList.get(k);
                res.add(root);
            }
        }
    }
    return res;
}

实现中还是有一些细节的，因为构造树时两边要遍历所有左右的匹配，然后接到根上面。
当然我们也可以像在Unique Binary Search Trees中那样存储所有的子树历史信息，然后进行拼合，虽然可以省一些时间，但是最终还是逃不过每个结果要一次运算，时间复杂度还是非多项式的，并且要耗费大量的空间，感觉这样的意义就不是很大了。

Unique Binary Search Trees -- LeetCode

原题链接: http://oj.leetcode.com/problems/unique-binary-search-trees/
这道题要求可行的二叉查找树的数量，其实二叉查找树可以任意取根，只要满足中序遍历有序的要求就可以。从处理子问题的角度来看，选取一个结点为根，就把结点切成左右子树，以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积，所以总的数量是将以所有结点为根的可行结果累加起来。写成表达式如下：

熟悉卡特兰数的朋友可能已经发现了，这正是卡特兰数的一种定义方式，是一个典型的动态规划的定义方式（根据其实条件和递推式求解结果）。所以思路也很明确了，维护量res[i]表示含有i个结点的二叉查找树的数量。根据上述递推式依次求出1到n的的结果即可。
时间上每次求解i个结点的二叉查找树数量的需要一个i步的循环，总体要求n次，所以总时间复杂度是O(1+2+...+n)=O(n^2)。空间上需要一个数组来维护，并且需要前i个的所有信息，所以是O(n)。代码如下：

public int numTrees(int n) {
    if(n<=0)
        return 0;
    int[] res = new int[n+1];
    res[0] = 1;
    res[1] = 1;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            res[i] += res[j]*res[i-j-1];
        }
    }
    return res[n];
}

这种求数量的题目一般都容易想到用动态规划的解法，这道题的模型正好是卡特兰数的定义。当然这道题还可以用卡特兰数的通项公式来求解，这样时间复杂度就可以降低到O(n)。因为比较直接，这里就不列举代码了。
如果是求解所有满足要求的二叉树（而不仅仅是数量）那么时间复杂度是就取决于结果的数量了，不再是一个多项式的解法了，有兴趣的朋友可以看看Unique Binary Search Trees II。

Restore IP Addresses -- LeetCode

原题链接: http://oj.leetcode.com/problems/restore-ip-addresses/
这道题的解法非常接近于NP问题，也是采用递归的解法。基本思路就是取出一个合法的数字，作为IP地址的一项，然后递归处理剩下的项。可以想象出一颗树，每个结点有三个可能的分支（因为范围是0-255，所以可以由一位两位或者三位组成）。并且这里树的层数不会超过四层，因为IP地址由四段组成，到了之后我们就没必要再递归下去，可以结束了。这里除了上述的结束条件外，另一个就是字符串读完了。可以看出这棵树的规模是固定的，不会像平常的NP问题那样，时间复杂度取决于输入的规模，是指数量级的，所以这道题并不是NP问题，因为他的分支是四段，有限制。代码如下：

public ArrayList<String> restoreIpAddresses(String s) {
    ArrayList<String> res = new ArrayList<String>();
    if(s==null || s.length()==0)
        return res;
    helper(s,0,1,"",res);
    return res;
}
private void helper(String s, int index, int segment, String item, ArrayList<String> res)
{
    if(index>=s.length())
        return;
    if(segment == 4)
    {
        String str = s.substring(index);
        if(isValid(str))
        {
            res.add(item+"."+str);
        }
        return;
    }
    for(int i=1;i<4&&(i+index<=s.length());i++)
    {
        String str = s.substring(index, index+i);
        if(isValid(str))
        {
            if(segment==1)
                helper(s,index+i,segment+1,str,res);
            else
                helper(s,index+i,segment+1,item+"."+str,res);
        }
    }
}
private boolean isValid(String str)
{
    if(str==null || str.length()>3)
        return false;
    int num = Integer.parseInt(str);
    if(str.charAt(0)=='0' && str.length()>1)
        return false;
    if(num>=0 && num<=255)
        return true;
    return false;
}

实现中需要一个判断数字是否为合法ip地址的一项的函数，首先要在0-255之间，其次前面字符不能是0。剩下的就是NP问题的套路了，递归中套一个for循环，不熟悉的朋友可以看看N-Queens哈。

Interleaving String -- LeetCode

原题链接: http://oj.leetcode.com/problems/interleaving-string/
这是一道关于字符串操作的题目，要求是判断一个字符串能不能由两个字符串按照他们自己的顺序，每次挑取两个串中的一个字符来构造出来。
像这种判断能否按照某种规则来完成求是否或者某个量的题目，很容易会想到用动态规划来实现。
先说说维护量，res[i][j]表示用s1的前i个字符和s2的前j个字符能不能按照规则表示出s3的前i+j个字符，如此最后结果就是res[s1.length()][s2.length()]，判断是否为真即可。接下来就是递推式了，假设知道res[i][j]之前的所有历史信息，我们怎么得到res[i][j]。可以看出，其实只有两种方式来递推，一种是选取s1的字符作为s3新加进来的字符，另一种是选s2的字符作为新进字符。而要看看能不能选取，就是判断s1(s2)的第i(j)个字符是否与s3的i+j个字符相等。如果可以选取并且对应的res[i-1][j](res[i][j-1])也为真，就说明s3的i+j个字符可以被表示。这两种情况只要有一种成立，就说明res[i][j]为真，是一个或的关系。所以递推式可以表示成

res[i][j] = res[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1) || res[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1)

时间上因为是一个二维动态规划，所以复杂度是O(m*n)，m和n分别是s1和s2的长度。最后就是空间花费，可以看出递推式中只需要用到上一行的信息，所以我们只需要一个一维数组就可以完成历史信息的维护，为了更加优化，我们把短的字符串放在内层循环，这样就可以只需要短字符串的长度即可，所以复杂度是O(min(m,n))。代码如下：

public boolean isInterleave(String s1, String s2, String s3) {
    if(s1.length()+s2.length()!=s3.length())
        return false;
    String minWord = s1.length()>s2.length()?s2:s1;
    String maxWord = s1.length()>s2.length()?s1:s2;
    boolean[] res = new boolean[minWord.length()+1];
    res[0] = true;
    for(int i=0;i<minWord.length();i++)
    {
        res[i+1] = res[i] && minWord.charAt(i)==s3.charAt(i);
    }
    for(int i=0;i<maxWord.length();i++)
    {
        res[0] = res[0] && maxWord.charAt(i)==s3.charAt(i);
        for(int j=0;j<minWord.length();j++)
        {
            res[j+1] = res[j+1]&&maxWord.charAt(i)==s3.charAt(i+j+1) || res[j]&&minWord.charAt(j)==s3.charAt(i+j+1);
        }
    }
    return res[minWord.length()];
}

动态规划其实还是有套路的，无非就是找到维护量，然后得到递推式，接下来看看历史信息对于空间的需求，尽量优化，会在后面对于动态规划做一个比较通用的总结哈。

Reverse Linked List II -- LeetCode

原题链接: http://oj.leetcode.com/problems/reverse-linked-list-ii/
这道题是比较常见的链表反转操作，不过不是反转整个链表，而是从m到n的一部分。分为两个步骤，第一步是找到m结点所在位置，第二步就是进行反转直到n结点。反转的方法就是每读到一个结点，把它插入到m结点前面位置，然后m结点接到读到结点的下一个。总共只需要一次扫描，所以时间是O(n)，只需要几个辅助指针，空间是O(1)。代码如下：

public ListNode reverseBetween(ListNode head, int m, int n) {
    if(head == null)
        return null;
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode preNode = dummy;
    int i=1;
    while(preNode.next!=null && i<m)
    {
        preNode = preNode.next;
        i++;
    }
    if(i<m)
        return head;
    ListNode mNode = preNode.next;
    ListNode cur = mNode.next;
    while(cur!=null && i<n)
    {
        ListNode next = cur.next;
        cur.next = preNode.next;
        preNode.next = cur;
        mNode.next = next;
        cur = next;
        i++;
    }
    return dummy.next;
}

上面的代码还是有些细节的，链表的题目就是这样，想起来道理很简单，实现中可能会出些小差错，还是熟能生巧哈。

Subsets II -- LeetCode

原题链接: http://oj.leetcode.com/problems/subsets-ii/
这道题跟Subsets一样是经典的NP问题--求子集。比Subsets稍微复杂一些的是这里的集合中可能出现重复元素，因此我们在求子集的时候要避免出现重复的子集。在Subsets中我们每次加进一个元素就会把原来的子集都加上这个元素，然后再加入到结果集中，但是这样重复的元素就会产生重复的子集。为了避免这样的重复，需要用个小技巧。
其实比较简单，就是每当遇到重复元素的时候我们就只把当前结果集的后半部分加上当前元素加入到结果集中，因为后半部分就是上一步中加入这个元素的所有子集，上一步这个元素已经加入过了，前半部分如果再加就会出现重复。所以算法上复杂度上没有提高，反而少了一些操作，就是遇到重复时少做一半，不过这里要对元素集合先排序，否则不好判断重复元素。同样的还是可以用递归和非递归来解，不过对于重复元素的处理是一样的。递归的代码如下：

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
    if(num == null)
        return null;
    Arrays.sort(num);
    ArrayList<Integer> lastSize = new ArrayList<Integer>();
    lastSize.add(0);
    return helper(num, num.length-1, lastSize);
}
private ArrayList<ArrayList<Integer>> helper(int[] num, int index, ArrayList<Integer> lastSize)
{
    if(index == -1)
    {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> elem = new ArrayList<Integer>();
        res.add(elem);
        return res;
    }
    ArrayList<ArrayList<Integer>> res = helper(num,index-1,lastSize);
    int size = res.size();
    int start = 0;
    if(index>0 && num[index]==num[index-1])
        start = lastSize.get(0);
    for(int i=start;i<size;i++)
    {
        ArrayList<Integer> elem = new ArrayList<Integer>(res.get(i));
        elem.add(num[index]);
        res.add(elem);
    }
    lastSize.set(0,size);
    return res;
}

非递归的代码如下：

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    res.add(new ArrayList<Integer>());
    if(num==null || num.length==0)
        return res;
    Arrays.sort(num);
    int start = 0;
    for(int i=0;i<num.length;i++)
    {
        int size = res.size();
        for(int j=start;j<size;j++)
        {
            ArrayList<Integer> newItem = new ArrayList<Integer>(res.get(j));
            newItem.add(num[i]);
            res.add(newItem);
        }
        if(i<num.length-1 && num[i]==num[i+1])
        {
            start = size;
        }
        else
        {
            start = 0;
        }
    }
    return res;
}

这种NP问题的重复处理在LeetCode有一定出现频率，比如还有Permutations II也是这样的，其实本质就是当一个重复元素进来时忽略上一个元素已经有的结果，只考虑由重复元素所产生的新结果。

Decode Ways -- LeetCode

原题链接: http://oj.leetcode.com/problems/decode-ways/
这道题要求解一个数字串按照字符串编码方式可解析方式的数量。看到这种求数量的，我们很容易想到动态规划来存储前面信息，然后迭代得到最后结果。
我们维护的量res[i]是表示前i个数字有多少种解析的方式，接下来来想想递归式，有两种方式：第一种新加进来的数字不然就是自己比较表示一个字符，那么解析的方式有res[i-1]种，第二种就是新加进来的数字和前一个数字凑成一个字符，解析的方式有res[i-2]种（因为上一个字符和自己凑成了一个）。当然这里要判断前面说的两种情况能否凑成一个字符，也就是范围的判断，如果可以才有对应的解析方式，如果不行，那么就是0。最终结果就是把这两种情况对应的解析方式相加。这里可以把范围分成几个区间：
（1）00：res[i]=0（无法解析，没有可行解析方式）；
（2）10, 20：res[i]=res[i-2]（只有第二种情况成立）；
（3）11-19, 21-26：res[i]=res[i-1]+res[i-2]（两种情况都可行）；
（4）01-09, 27-99：res[i]=res[i-1]（只有第一种情况可行）；
递推式就是按照上面的规则来得到，接下来我们只要进行一遍扫描，然后依次得到维护量就可以了，算法的时间复杂度是O(n)。空间上可以看出我们每次只需要前两位的历史信息，所以只需要维护三个变量然后迭代赋值就可以了，所以空间复杂度是O(1)。代码如下：

public int numDecodings(String s) {
    if(s==null || s.length()==0 || s.charAt(0)=='0')
    {
        return 0;
    }
    int num1=1;
    int num2=1;
    int num3=1;
    for(int i=1;i<s.length();i++)
    {
        if(s.charAt(i)=='0')
        {
            if(s.charAt(i-1)=='1' || s.charAt(i-1)=='2')
                num3 = num1;
            else
                return 0;
        }
        else
        {
            if(s.charAt(i-1)=='0' || s.charAt(i-1)>='3')
                num3 = num2;
            else
            {
                if(s.charAt(i-1)=='2' && s.charAt(i)>='7' && s.charAt(i)<='9')
                    num3 = num2;
                else
                    num3 = num1+num2;
            }
        }
        num1 = num2;
        num2 = num3;
    }
    return num2;
}

这道题是一维动态规划的题目，递推式关系来说是比较容易得到的，主要是要对这些两位数进行划分有一些细节，容易出小错误。

Recover Binary Search Tree -- LeetCode

原题链接: http://oj.leetcode.com/problems/recover-binary-search-tree/
这道题是要求恢复一颗有两个元素调换错了的二叉查找树。一开始拿到可能会觉得比较复杂，其实观察出规律了就比较简单。主要还是利用二叉查找树的主要性质，就是中序遍历是有序的性质。那么如果其中有元素被调换了，意味着中序遍历中必然出现违背有序的情况。那么会出现几次呢？有两种情况，如果是中序遍历相邻的两个元素被调换了，很容易想到就只需会出现一次违反情况，只需要把这个两个节点记录下来最后调换值就可以；如果是不相邻的两个元素被调换了，举个例子很容易可以发现，会发生两次逆序的情况，那么这时候需要调换的元素应该是第一次逆序前面的元素，和第二次逆序后面的元素。比如1234567,1和5调换了，会得到5234167，逆序发生在52和41，我们需要把4和1调过来，那么就是52的第一个元素，41的第二个元素调换即可。
搞清楚了规律就容易实现了，中序遍历寻找逆序情况，调换的第一个元素，永远是第一个逆序的第一个元素，而调换的第二个元素如果只有一次逆序，则是那一次的后一个，如果有两次逆序则是第二次的后一个。算法只需要一次中序遍历，所以时间复杂度是O(n)，空间是栈大小O(logn)。代码如下：

public void recoverTree(TreeNode root) {
    if(root == null)
        return;
    ArrayList<TreeNode> pre = new ArrayList<TreeNode>();
    pre.add(null);
    ArrayList<TreeNode> res = new ArrayList<TreeNode>();
    helper(root,pre, res);
    if(res.size()>0)
    {
        int temp = res.get(0).val;
        res.get(0).val = res.get(1).val;
        res.get(1).val = temp;
    }
}
private void helper(TreeNode root, ArrayList<TreeNode> pre, ArrayList<TreeNode> res)
{
    if(root == null)
    {
        return;
    }
    helper(root.left, pre, res);
    if(pre.get(0)!=null && pre.get(0).val>root.val)
    {
        if(res.size()==0)
        {
            res.add(pre.get(0));
            res.add(root);
        }
        else
        {
            res.set(1,root);
        }
    }
    pre.set(0,root);
    helper(root.right,pre,res);
}

可以看到实现中pre用了一个ArrayList来存，这样做的原因是因为java都是值传递，所以我们要全局变化pre的值（而不是在当前函数里），只能传一个数组，才能改变结点的地址，这一点非常重要，也是java和C++一个比较大的区别，不了解的朋友可以研究一下哈。
这道题还是考察二叉树遍历，不过应用题目要求套了一个不同的外壳，需要我们利用二叉查找树的性质观察出规律之后才能求解。

Gray Code -- LeetCode

原题链接: http://oj.leetcode.com/problems/gray-code/
这道题要求求出n位的格雷码对应的二进制数，主要在于找到一种格雷码的递增方法（gray code并不是唯一的，可以有多种）。
我们来看看有了n-1位的格雷码如何得到n位的格雷码呢？其实方法比较简单，首先在n-1位的格雷码前面都添加0作为前2^(n-1)个格雷码，它们一定是合法的因为除了第一位（都是0）其余位都跟n-1的格雷码一致，所以两两之间只相差一位，满足要求。接下来看看如何接上剩下的2^(n-1)个，我们把n-1位的格雷码倒序排列，然后在每个前面添加1，然后接到上述的前2^(n-1)个就可以了。首先因为是倒序过来，所以中间两个元素除去第一位其他都是一样的（因为原来最后一个，现在倒序过来就是第一个），而他们第一位分别是0和1，满足格雷码的要求。而剩下的元素因为我们是n-1位的格雷码倒序排列，所以两两都是满足要求的，加上前面都一样的位1，仍然满足条件。最后看看这些数字是不是都不一样，前半部分和后半部分肯定不会一样，而因为前半部分都是0开头，后半部分都是1打头，所以互相之间也不会有重复，可以看出覆盖了所有数字，而且依次下来均满足条件。
如此我们提出了格雷码的递推方法，我们只需要做一次位数的循环，每次根据上面结果构造当前位数的结果即可。算法复杂度是O(2+2^2+...+2^n-1)=O(2^n)，所以是指数量级的，因为是结果数量无法避免。空间复杂度则是结果的大小，也是O(2^n)。代码如下：

public ArrayList<Integer> grayCode(int n) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    if(n<0)
        return res;
    if(n==0)
    {
        res.add(0);
        return res;
    }
    res.add(0);
    res.add(1);
    for(int i=2;i<=n;i++)
    {
        int size = res.size();
        for(int j=size-1;j>=0;j--)
        {
            res.add(res.get(j)+(1<<(i-1)));
        }
    }
    return res;
}

可以看出上面代码并不需要处理前半部分，因为要求的是二进制数对应的整数，所以在前面加0等于原来的数字，所以前面数字只需要保持原来就行，后面进行倒序然后对最高位赋1即可。感觉更接近于一道寻找规律的题目，实现上用到一点位运算会比较简单，不过位运算是这道题的考察点之一，面试中还是有关于位运算的题目，需要熟悉一下哈。

Binary Tree Zigzag Level Order Traversal -- LeetCode

原题链接: http://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
这道题其实还是树的层序遍历Binary Tree Level Order Traversal，如果不熟悉的朋友可以先看看哈。不过这里稍微做了一点变体，就是在遍历的时候偶数层自左向右，而奇数层自右向左。在Binary Tree Level Order Traversal中我们是维护了一个队列来完成遍历，而在这里为了使每次都倒序出来，我们很容易想到用栈的结构来完成这个操作。有一个区别是这里我们需要一层一层的来处理（原来可以按队列插入就可以，因为后进来的元素不会先处理），所以会同时维护新旧两个栈，一个来读取，一个存储下一层结点。总体来说还是一次遍历完成，所以时间复杂度是O(n)，空间复杂度最坏是两层的结点，所以数量级还是O(n)（满二叉树最后一层的结点是n/2个）。代码如下：

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(root==null)
        return res;
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    int level=1;
    ArrayList<Integer> item = new ArrayList<Integer>();
    item.add(root.val);
    res.add(item);
    stack.push(root);
    while(!stack.isEmpty())
    {
        LinkedList<TreeNode> newStack = new LinkedList<TreeNode>();
        item = new ArrayList<Integer>();
        while(!stack.isEmpty())
        {
            TreeNode node = stack.pop();
            if(level%2==0)
            {
                if(node.left!=null)
                {
                    newStack.push(node.left);
                    item.add(node.left.val);
                }
                if(node.right!=null)
                {
                    newStack.push(node.right);
                    item.add(node.right.val);
                }
            }
            else
            {
                if(node.right!=null)
                {
                    newStack.push(node.right);
                    item.add(node.right.val);
                }
                if(node.left!=null)
                {
                    newStack.push(node.left);
                    item.add(node.left.val);
                }                   
            }
        }
        level++;
        if(item.size()>0)
            res.add(item);
        stack = newStack;
    }
    return res;
}

上面的算法其实还是一次广度优先搜索，只是在读取每一层结点交替的交换顺序。毕竟面试中像Binary Tree Level Order Traversal有时候考得太多了，面试官会觉得你肯定练过，所以会稍作变体，来考察对于编程和算法的基本理解。

Scramble String -- LeetCode

原题链接: http://oj.leetcode.com/problems/scramble-string/
这道题看起来是比较复杂的，如果用brute force，每次做切割，然后递归求解，是一个非多项式的复杂度，一般来说这不是面试官想要的答案。
这其实是一道三维动态规划的题目，我们提出维护量res[i][j][n]，其中i是s1的起始字符，j是s2的起始字符，而n是当前的字符串长度，res[i][j][len]表示的是以i和j分别为s1和s2起点的长度为len的字符串是不是互为scramble。
有了维护量我们接下来看看递推式，也就是怎么根据历史信息来得到res[i][j][len]。判断这个是不是满足，其实我们首先是把当前s1[i...i+len-1]字符串劈一刀分成两部分，然后分两种情况：第一种是左边和s2[j...j+len-1]左边部分是不是scramble，以及右边和s2[j...j+len-1]右边部分是不是scramble；第二种情况是左边和s2[j...j+len-1]右边部分是不是scramble，以及右边和s2[j...j+len-1]左边部分是不是scramble。如果以上两种情况有一种成立，说明s1[i...i+len-1]和s2[j...j+len-1]是scramble的。而对于判断这些左右部分是不是scramble我们是有历史信息的，因为长度小于n的所有情况我们都在前面求解过了（也就是长度是最外层循环）。
上面说的是劈一刀的情况，对于s1[i...i+len-1]我们有len-1种劈法，在这些劈法中只要有一种成立，那么两个串就是scramble的。
总结起来递推式是res[i][j][len] = || (res[i][j][k]&&res[i+k][j+k][len-k] || res[i][j+len-k][k]&&res[i+k][j][len-k]) 对于所有1<=k<len，也就是对于所有len-1种劈法的结果求或运算。因为信息都是计算过的，对于每种劈法只需要常量操作即可完成，因此求解递推式是需要O(len)（因为len-1种劈法）。
如此总时间复杂度因为是三维动态规划，需要三层循环，加上每一步需要线行时间求解递推式，所以是O(n^4)。虽然已经比较高了，但是至少不是指数量级的，动态规划还是有很大有事的，空间复杂度是O(n^3)。代码如下：

public boolean isScramble(String s1, String s2) {
    if(s1==null || s2==null || s1.length()!=s2.length())
        return false;
    if(s1.length()==0)
        return true;
    boolean[][][] res = new boolean[s1.length()][s2.length()][s1.length()+1];
    for(int i=0;i<s1.length();i++)
    {
        for(int j=0;j<s2.length();j++)
        {
            res[i][j][1] = s1.charAt(i)==s2.charAt(j);
        }
    }
    for(int len=2;len<=s1.length();len++)
    {
        for(int i=0;i<s1.length()-len+1;i++)
        {
            for(int j=0;j<s2.length()-len+1;j++)
            {
                for(int k=1;k<len;k++)
                {
                    res[i][j][len] |= res[i][j][k]&&res[i+k][j+k][len-k] || res[i][j+len-k][k]&&res[i+k][j][len-k];
                }
            }
        }
    }
    return res[0][0][s1.length()];
}

个人觉得这是LeetCode中最难的动态规划的题目了，要进行一次三维动态规划，对于维护量的含义也比较讲究。有朋友会讨论这个维护量是怎么提出来的，我自己也没什么绝对的方法，还是熟能生巧，靠“感觉”，做的题目多了就自然来了，这个做高中数学题有点类似哈，辅助线是靠“灵感”的哈。面试中如果遇到就是top难度的了，不过即使如此，只要思路清晰，还是可以记住的。如果没做过，个人觉得比较难当场想出来，不过算法大牛就另说了，这种题很经常出现在编程比赛中，ACM高手还是不在话下的哈。

Partition List -- LeetCode

原题链接: http://oj.leetcode.com/problems/partition-list/
这是一道链表操作的题目，要求把小于x的元素按顺序放到链表前面。我们仍然是使用链表最常用的双指针大法，一个指向当前小于x的最后一个元素，一个进行往前扫描。如果元素大于x，那么继续前进，否则，要把元素移到前面，并更新第一个指针。这里有一个小细节，就是如果不需要移动（也就是已经是接在小于x的最后元素的后面了），那么只需要继续前进即可。算法时间复杂度是O(n)，空间只需要几个辅助变量，是O(1)。代码如下：

public ListNode partition(ListNode head, int x) {
    if(head == null)
        return null;
    ListNode helper = new ListNode(0);
    helper.next = head;
    ListNode walker = helper;
    ListNode runner = helper;
    while(runner.next!=null)
    {
        if(runner.next.val<x)
        {
            if(walker!=runner)
            {
                ListNode next = runner.next.next;
                runner.next.next = walker.next;
                walker.next = runner.next;
                runner.next = next;
            }
            else
                runner = runner.next;
            walker = walker.next;
        }
        else
        {
            runner = runner.next;
        }
    }
    return helper.next;
}

这道题思路比较清晰，不过还是有点细节的，第一次写可能不容易完全写对，可以练习练习。