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是完全一样的， 也是维护两个量， 一个是到目前为止最好的交易（全局最优）， 另一个是在当前一天卖出的最佳交易（局部最优）， 其他步骤也是一样的， 这里就不列出来了。

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