LeetCode总结 -- 二叉查找树篇

这篇总结主要介绍一个比较常见的数据结构--二叉查找树。二叉查找树既是一颗树，又带有特别的有序性质，所以考察的方式比较多而且灵活，属于面试题目中的常客。LeetCode中关于二叉查找树的题目有以下几道：
Validate Binary Search Tree
Recover Binary Search Tree
Unique Binary Search Trees
Unique Binary Search Trees II
Convert Sorted Array to Binary Search Tree
Convert Sorted List to Binary Search Tree

先来看看最基本的Validate Binary Search Tree，就是判断一个树是不是二叉查找树。比较简单而且明了的方法就是利用二叉查找树的中序遍历有序的性质，只要对树进行一次中序遍历，而其中的结点都满足有序即可，实现上就是维护一个前驱结点，每次判断前驱结点比当前结点要小。另一种方法是根据二叉查找树的定义来实现，保证结点满足它的左子树的每个结点比当前结点值小，右子树的每个结点比当前结点值大，实现上就是对于每个结点保存左右界，然后进行递归判断左右界不会违背即可。

Recover Binary Search Tree这道题目还是利用二叉查找树的主要性质，就是中序遍历是有序。那么如果其中有元素被调换了，意味着中序遍历中必然出现违背有序的情况。主要考虑到就是出现违背的次数问题。这里有两种情况：
（1）如果是中序遍历相邻的两个元素被调换了，很容易想到就只需会出现一次违反情况，只需要把这个两个节点记录下来最后调换值就可以；
（2）如果是不相邻的两个元素被调换了，会发生两次逆序的情况，那么这时候需要调换的元素应该是第一次逆序前面的元素，和第二次逆序后面的元素。

Unique Binary Search Trees这道题要求可行的二叉查找树的数量，其实二叉查找树可以任意取根，只要满足中序遍历有序的要求就可以。从处理子问题的角度来看，选取一个结点为根，就把结点切成左右子树，以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积，所以总的数量是将以所有结点为根的可行结果累加起来。这其实是一个卡特兰数的模型，所以按照公式进行实现就可以。而Unique Binary Search Trees II则不能用卡特兰数，因为要求出所有结果，所以还是得走递归遍历的过程，然后把生成树来的树接上。

Convert Sorted Array to Binary Search Tree和Convert Sorted List to Binary Search Tree则是属于二叉查找树的构造问题，针对两种不同数据结构数组和链表进行构造。其实方法都是一样，就是递归对窗口进行圈限，然后用中间的结点作为当前根，再递归生成左右子树。链表的构造要稍微绕一些，因为要通过中序遍历走到第一个结点，然后递进链表。

这篇总结主要介绍LeetCode中关于二叉查找树的题目，二叉查找树因为是基本数据结构加上有可利用的有序性质，还是在面试中相当常见的，对于性质理解要深刻，实现要熟练哈。

Maximum Product Subarray -- LeetCode

原题链接: https://oj.leetcode.com/problems/maximum-product-subarray/
这道题跟Maximum Subarray模型上和思路上都比较类似，还是用一维动态规划中的“局部最优和全局最优法”。这里的区别是维护一个局部最优不足以求得后面的全局最优，这是由于乘法的性质不像加法那样，累加结果只要是正的一定是递增，乘法中有可能现在看起来小的一个负数，后面跟另一个负数相乘就会得到最大的乘积。不过事实上也没有麻烦很多，我们只需要在维护一个局部最大的同时，在维护一个局部最小，这样如果下一个元素遇到负数时，就有可能与这个最小相乘得到当前最大的乘积和，这也是利用乘法的性质得到的。代码如下：

public int maxProduct(int[] A) {
    if(A==null || A.length==0)
        return 0;
    if(A.length == 1)
        return A[0];
    int max_local = A[0];
    int min_local = A[0];
    int global = A[0];
    for(int i=1;i<A.length;i++)
    {
        int max_copy = max_local;
        max_local = Math.max(Math.max(A[i]*max_local, A[i]), A[i]*min_local);
        min_local = Math.min(Math.min(A[i]*max_copy, A[i]), A[i]*min_local);
        global = Math.max(global, max_local);
    }
    return global;
}

这道题是一道很不错的面试题目，因为Maximum Subarray这道题过于常见了，所以可能大部分人都做过，这道题模型类似，但是又有一些新的考点，而且总体还是比较简单，无论是思路上还是实现上，又能考察动态规划，个人还是比较喜欢的哈。

LeetCode总结 -- 图篇

图的算法跟树一样是准备面试中必不可少的一块，不过图的方法很容易概括，面试中考核的无非就是两种搜索算法：深度优先搜索和广度优先搜索。LeetCode中关于图的问题有以下几个：
Clone Graph
Word Ladder
Word Ladder II
Longest Consecutive Sequence
Word Search
Surrounded Regions

先来看看最基础的Clone Graph，很简单就是要复制一个图，常见的两种搜索算法（深度和广度）都可以用，具体细节就不在这里解释了，不熟悉的朋友可以看看相关资料。建议大家还是两种都要练一练，因为在解决具体问题中这两种方法还是很常用的。

接下来的这些题都是基于图算法的应用，Word Ladder和Word Ladder II是比较典型的，看起来好像是字符串操作的题目，实际上这里得转换成图的角度来考虑，因为字符集比较小的缘故（26个小写字母），也就是说对于一个单词来说，改变其中一个字符可以有25条边（除去他自己），所以总共有（25*单词的长度L）条边。找到是否有满足一个单词转成另一个单词就是在这个图中找到一条路径。所以我们可以把问题转换成图用广度优先搜索来解决，找到即可停止。

Word Ladder是广度优先搜索的应用，而Longest Consecutive Sequence则是深度优先搜索的应用。题目要求是找出最长的连续整数串，如果把数字看成结点，与它相邻的整数连有边，那么找到最长的连续串就是在这个图中找最长路径。因为是最长路径，这里用深度优先搜索是比较适合的。

Word Search也是一道深度优先搜索的题目，是把上下左右相邻的结点看成有边联结，然后进行深度搜索就可以了，小细节是这里从每个点出发字符就可以重用，所以要重置一下访问结点。

Surrounded Regions要用一个图形学中很常用的填充算法：Flood fill 算法，其实本质还是一个深度优先搜索，跟Word Search一样是把相邻的上下左右看成连边，然后进行搜索填充。

图的问题其实本质都是两种搜索算法，难点主要在于对于具体问题如何想到转换成图的问题，然后用这两种搜索来解决，这也是算法中的一个分支，面试中也是常客哈。

LeetCode总结 -- 矩阵篇

矩阵（一般是二维数组）操作的题目在面试中考察基础coding的时候比较常见，一般来说不带有太多算法思想，纯粹就是二维数组下标的操作。虽然比较简单，不过还是比较能体现基本的实现能力。LeetCode中关于矩阵操作的题目有以下几个：
Spiral Matrix
Spiral Matrix II
Rotate Image
Valid Sudoku

Set Matrix Zeroes

前面三个题Spiral Matrix，Spiral Matrix II，Rotate Image思路比较类似，都是按照一定的规则在二维数组里面走下标。

Spiral Matrix就是按照螺旋的方式，按照右下左上的顺序，走到头就换方向。小技巧就是把这些螺旋分成层，然后知道区间照着走就可以。Spiral Matrix II也是一样的，不过是换成1到n^2的整数。

而Rotate Image也是比较类似的，主要是想清楚每一个点经过旋转之后的下表位置，然后还是分成层，一层层进行旋转即可。

Valid Sudoku是让我们判断一个Sudoku的盘是否合法，对于行和列的判断应该比较简单，就是1到9不重复出现即可，有点技巧的是对于每个九宫格的合法性判断，这里需要稍微斟酌一下才可以把代码写得比较通用简洁一些，大家可以看看Valid Sudoku中的实现哈。

最后我们来说说比较有技巧的Set Matrix Zeroes这道题。它是一个非常常见的题目了，也是cc150中的题目。看似一个非常简单的题目，就是如果矩阵如果有元素为0，就把对应的行和列上面的元素都置为0，但是却有层层的优化方法。时间复杂度基本都是O(m*n)，而空间复杂度却有很多可以优化的空间。最简单的思路是备份一个矩阵，然后照着原矩阵进行判断，有0则置对应列和行为0，这样空间是O(m*n)。而如果我们维护一个行和列的布尔数组，然后扫描一遍矩阵记录那一行或者列是不是应该置0，最后在进行一次赋值，这样时间复杂度不变，而空间复杂度只需要O(m+n)。再进一步优化，如果我们连布尔数组都不要，而用第一行和第一列来代替布尔数组，然后用两个变量来维护第一行和第一列的置0情况，这样就只需要O(1)的额外空间了。模型非常简单的一个题目，却有非常不同的答案，还是比较值得一考的题目哈。

这篇总结主要介绍了LeetCode中几个关于矩阵操作的题目，这种题目主要考点就是二维数组的下标操作，写代码的时候要思路清晰，才能保证bug free地实现。而有时候也会有像Set Matrix Zeroes这样模型比较简单，但是还是有一些考点的题目，大家还是要尽量考虑到最优解法。

LeetCode总结 -- 位运算篇

位运算一直编程和面试中的一个必须准备的主题。 不过现在面试中关于位运算的出现得不多，主要原因还是位运算太考察技巧了，很多时候很难在短时间内想出来，所以作为面试的题目显得有点太花时间了。LeetCode中关于位运算的题目有以下几道：
Single Number
Single Number II
Divide Two Integers
Pow(x, n)

先来说说Single Number， 这应该LeetCode中唯一一道纯粹用位运算解决的题目。题目本身要求是找出唯一一个在数组中出现一次的整数，而其他都会出现两次。这里利用到了位运算中异或的性质，就是两个相同的数进行异或会得到0，并且任何一个数与0的异或还是原数。利用上面的性质，只要把数组中的元素一一异或起来，因为出现两次的会互相抵消，最后会只剩下那个出现一次的整数，所以就搞定了。

对于Single Number II，上面的方法就没办法了，因为出现三次就不能利用异或的性质了，所以这个题目得使用另外的方法了。 算法是对每个位出现1的次数进行统计，因为其他元素都会出现三次，所以最终这些位上的1的个数会是3的倍数。如果我们把统计结果的每一位进行取余3，剩下的结果就会剩下那个出现一次的元素。这个方法对于出现k次都是通用的，包括上面的Single Number也可以用这种方法，不过没有纯位运算的方法高大上哈。

接下来看看位运算在Divide Two Integers和Pow(x, n)这道题中的应用，主要是利用任何一个整数可以表示成以2的幂为底的一组基的线性组合的性质，即num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n。对于Divide Two Integers基于上面的性质以及左移一位相当于乘以2，我们先让除数左移直到大于被除数之前得到一个最大的基。然后接下来我们每次尝试减去这个基，如果可以则结果增加加2^k，然后基继续右移迭代，直到基为0为止。因为这个方法的迭代次数是按2的幂直到超过结果，所以时间复杂度可以达到O(logn)，也就是位的数量。而Pow(x, n)也是使用同样的方法，把幂数n分解成2的幂数的基，然后进行依次平方然后求和。这个方法算是数值运算中的一个比较实用的方法，还是要熟练掌握。

这篇总结介绍了LeetCode中几个关于位运算的题目，虽然数量很少，不过思想上还是都挺有意义的，如果面试中遇到能提出位运算的解法还是能加分不少，所以位运算在有些题目中还是一把关键的武器。

LeetCode总结 -- 高精度篇

我们常见的一些基本的数据结构比如整型int或者浮点型float由于位数过多无法用内置类型存储，这时候我们就需要自己实现高精度的数据类型来进行存储和运算。这种问题在实际产品中还是比较实用的，所以相对来说也是面试中的常客。LeetCode中关于高精度的题目有以下几道：
Add Binary
Add Two Numbers
Plus One
Multiply Strings

Add Binary和Add Two Numbers是同一类型的题目，都是高精度中的加法运算，只是一个是二进制的，一个是十进制的，其实进制是无所谓的，代码基本可以统一起来用一种思路来实现。思路也很简单，就是从低位开始相加，一直维护进位就可以了。属于考察非常基本的数组操作，没有什么算法难度，主要看看coding实现能力。

Plus One也是一道常见的题目，他其实就是实现C++中++的运算符，因为只需要+1，所以其实比上面的题目更加简单。这道题的小陷阱就是它是用数组从高位到低位进行存储的，所以如果出现进位，那么需要重新分配空间，并给最高位赋1，其他位赋0即可。这里恰好引入一个点，就是高精度存储应该低位到高位存储还是反过来好，这也是面试中可能问到的问题。

Multiply Strings这道题是高精度的乘法运算，属于比较复杂的，需要对每一位的结果分别计算累加，其中的细节有点多，这里就不细说了，个人认为实现有点复杂，并不是很适合在面试中出现。

虽然说题目不多，但是这类题目的出现率却是非常高的，主要原因倒不是这种题目本身有很多的考点，而是它们特别好扩展，基本上来说问到这种题目，首先是考察一下coding能力，一般来说都是这种加减乘除的运算，接下来一定会是关于数据结构（或者说面向对象）的设计。这些题目的本身都是为高精度BigInteger服务的，面试官会问一些关于这个数据结构设计的问题，比如说如果让你来设计这个类，用什么数据结构来存（比如数组还是链表，各有什么利弊），需要哪些接口（构造函数，加减乘除运算等等），还有比如要设计构造函数，需要什么接口的构造函数（这里赋值构造函数，赋值运算符这些肯定是需要的，但是要注意必须提供对于常规类型比如int，long这些的接口，一个好的高精度类肯定是要对比它更弱的数据结构进行兼容的）。

上面我列举了一些可能在面试中会被继续考查的问题，也是一部分联想，像这种设计问题可以问得还是比较多的，也是非常常见的，大家可以自己多进行这种问题的准备和联想哈。

LeetCode总结 -- 树的性质篇

树的性质判断是树的数据结构比较基本的操作，一般考到都属于非常简单的题目，也就是第一道入门题，面试中最好不能有问题，力求一遍写对，不要给面试官任何挑刺机会。LeetCode中关于树的性质有以下题目：
Maximum Depth of Binary Tree
Minimum Depth of Binary Tree
Balanced Binary Tree
Same Tree
Symmetric Tree

首先说说关于求树的深度的题目，最简单的是求最大深度Maximum Depth of Binary Tree，一般都是用递归实现。思路很简单，只需要对走到空结点返回0，然后其他依次按层递增，取左右子树中大的深度即可。Minimum Depth of Binary Tree稍微复杂一点，主要是要注意因为是取左右子树小的深度，但是有一种情况是不计入深度的，就是比如左子树彻底为空时，这种情况我们不会认为深度就是0，因为左边并没有叶子，按照定义我们是要找叶子结点的最小深度。所以需要对于左右是否为空做一个额外的判断。

求树的深度属于简单的题目，所以如果递归实现比较快的话，面试官可能会问非递归怎么实现，如果有时间的话还是得练习一下哈，原理跟LeetCode总结 -- 树的遍历篇是一致的。

Balanced Binary Tree是求深度的一道扩展题目，基本原理还是求深度。不过需要增加的环节是判断他是不是平衡树，因为深度是我们必须维护的量，如果选用额外的布尔变量来维护是否为平衡树也可以。不过这里可以利用深度大于0的性质，可以将平衡的树返回正常的深度值，而不平衡的则返回-1来进行区分，这样相当于用一个变量维护了想要的两种性质，代码实现也比较简单。

Same Tree也是比较基础的题目，和树的遍历时一样的，只是对两棵树同时做相同的遍历，然后进行一一比较，如果出现不同则返回false即可。

Symmetric Tree会稍微绕一点，不过想清楚跟Same Tree还是差不多，第一个不同点是要根据左右子树比较，其实就是把左右子树当成Same Tree中的两个树即可。第二个不同点是在递归过程中对于结点的左右子树进行互换比较，也就是左跟右比，右跟左比。

这篇总结主要提到了LeetCode中求树的一些基本性质的题目，这类题目比较简单，属于最低门槛题目，所以要力求bug free地一遍完成哈。