每日5道题

今天做了三道题，本来很有希望打破三道的大关，哎呀科协卡在了求不同路径的问题，我本来以为很简单用一个递归就解决了，结果submit告诉我递归报错，明天再试试吧。
Leetcode 48 旋转图像。我觉得这个题真的蛮好的，很开阔思路。这个题我前天晚上就开始想了，一直没有思路。然后今天看了讲解之后恍然大悟。这个题问题的关键就在于怎么swap。我们平常用sway函数，都是两两swap，我就是被卡在了这里，两两换肯定是换不过来的，根本找不到规律。其实这个题的关键就是，一个值被存在了temp里了，没有必要很快就把它赋给别人，可以把它这个坑先留着。Rotate 90度。就意味着要留四个，等最后一个坑空出来，再把temp的值赋给它。这个就相当于更大的swap。然后再逐层完成swap就行了。

Leetcode 55 蹦蹦跳。这个题我还是比较骄傲的，因为算法是我自己想的，而且效率很高。我的想法是检测数组中的0，就是遇到0就检测前面是否能跳过它，要不就不管。这种适用于0少的。另一种网上的解法是维持一个reachable量，如果当前的i大于reachable，就return false。这种方法也比较直观，而且运行时间就是O(n)。

Leetcode 56 合并区间。 这个题我看了半天，还是语言障碍啊。interval特指区间，所以相当于合并区间的意思。这里面先要把区间的起始点都取出来，排个序，然后把区间的终止点取出来也排个序，然后再合并。不过这个题有意思的事情是return type，return的是一个int[][]。这就很尴尬了，因为不可能事先知道合并之后有多少个区间，所以使用的肯定是ArrayList或者Linked List。参考了别人的解法，可以先声明一个ArrayList<int[]>，然后再用List.toArray(int[result.size()][])，这样能成功我也是很奇怪，但是确实最后能work。这里面不能用integer直接转，因为integer和int不一样，所以不能把一个ArrayList<ArrayList<Integer>>转成int[][]。唉这时候就想起了python的好了，一开始坚定不移的使用java，到这里突然想用python。。。

今天依然三道题，我发现最近刷题的时间都集中在晚上了，难道只有晚上能静下心来做一下题hhh
Leetcode 62 Unique Paths。今天我终于想到怎么用排列解这道题了。其实这道题就是一个排列问题，因为向右走和向下走的步数都是固定的，不过是怎么排列的问题。这是一个部分顺序的排列问题，所以要用C x x。总共有m+n步，先选其中m步往右走，就行了，所以解答就是C(m+n) m。如果用dynamic Programming做，就先声明一个数组，然后找到每一步的状态方程，每一步的path取决于上方和左方的path。
Leetcode 64 最短路程。这也是一个DP问题，DP问题就是先建立好subproblem的解，然后再最后逐步解决最后的问题。最短路径也一样，先初始化好dp[0][j],dp[i][0]。这样之后也一样，dp[i][j]取决于左方和上方的值。
Leetcode 70 爬梯子。同样的DP问题，i步的方法取决于i-1和i-2的方法，这样最后加起来就行了。

总的来说，DP比recursive更高效，这些问题无一例外我都先想到了recursive，但是recursive耗时太多，而且stack space占的也多，DP的好处在于不重复解sub problem，这样比recursive高效，耗时也短一些。

昨天休息了一天，今天做了两道题。
Leetcode 72，修改距离。计算将一个字符串转化到另一个字符串的最小距离。没想到这个也是DP的问题哈哈，和之前一样把问题分解成小问题。从后往前或者从前往后均可，如果字符相同，就可以比较之前的字符。

Leetcode 75， 排序颜色。这个我自己想了一个one pass的方法，在leetcode里有详细介绍，大概就是维持index0 和 index2 两个指针，这样最后把0全放到左边，2全放到右边。

今天被一道题难住了，Leetcode 76 最小字符串。这道题难点倒不是在方法上，方法基本理解了，就是保持两个指针。但是最后这个函数怎么这么难写，怎么样才能实现高效检测一个字符串是不是包含另一个字符串呢？。。。

今天终于把minmum window 做出来了，真是够费劲儿的，目前遇到的最麻烦的题目。今天三道题：
Leetcode 76 minimum window。给定一个字符串和目标字符串，找到包含目标字符串的最小window。这是一个双指针问题，如果找到了包含的字符串，移动左指针，如果没找到，移动右指针。这个思路还好，问题是实现起来实在太麻烦。需要维护两个hashmap，一个是required string的，一个是window的，必须要让在 window中特定字符出现的次数大于required string的。所以不停要对map进行改变。不过只要思路正确，写起来还行，就是有一些小细节麻烦一点，一些逻辑需要弄清楚，比如怎么最后判断字符全都对上了。竟然是最后维护了一个totaloccureen....，看totaloccurrennce有没有对上，我觉得这个解法真的很上世纪，感觉不是那么靠谱，不过anywoy能work。所以这里要注意检查一个字符串是否包含另一个字符串，不是简单的检查字符是否都出现，而是要检查是否出现的次数也一致。

Leetcode 78 subsets。给定一个集合，给出所有子集合，包括他自身。这个我觉得和全排列很像啊，反正就是用recursive一个个找，最后记得把空集加上。我倒是想了一下会不会用recursive太慢，想了一下能不能用dp做，但是想了一下好像不行，因为每个都是特殊的，所以不存在用记忆换效率的问题。

Leetcode 79 word search。 给定一个2维矩阵，在矩阵中找到特定的词，这不就是cross puzzle那个东西嘛，想办法在二维数组里找到能组成词的组合。这也是用递归，不过这个递归要注意，如果一个path对，那返回对，如果错，不能返回错，因为不能保证其他path也错。然后这个题不同之处在于不能重复用同样的字，所以需要维护一个同样大小的二维数组来记录是不是已经访问过了某个位置。

今天一道题。。。实在有点惭愧了
Leetcode 84 直方图中的最大矩形。这个题的关键是在任何一个位置，都要找到左边和右边比它低的位置，只要找到了，就找到了两个边界，最后只要用边界去乘直方图的高度即可。
Leetcode 85 最大矩形。 这个题目确实是名副其实的hard，在一个二维矩阵里找到一个最大的由一组成的矩形，看完了网上的讲解，知道了要用之前84题的函数，觉得实在是巧妙，明早把它写出来。

上一道关于最大矩形面积的题目最终还是放弃了没有继续做下去，我觉得没有什么算法的问题在里面，至于用stack解决最大直方图的问题，我感觉也是一个思路的问题，没有对算法本质的困惑在里面，所以决定先放一下等一会再回头来看。
今天两题。
Leetcode 94 In-oredr 遍历二叉树。终于开始进入树了。其实我对pre-order,in-oreder,和post-order一直分不清楚，今天看到这个题查了一下，我大概明白了。弄清楚这个需要把一个树分为三部分，左子树，根，和右子树，所以这里的pre,in,post都是指的root的位置，如果root在前面，就叫pre；如果root在中间，就叫in；如果root在后面，就是post。所以in-order就是说要先遍历左子树，再遍历根，最后遍历右子树。用recursive解这道题很直观，直接recursive(node.left),node,recursive(node.right)就行。但是如果用循环的话，怎么解决呢，我稍微想了一下，发现循环的问题不好写。看了下网上的思路，才想到应该用栈，栈先入后出非常适合这种先遍历左子树的遍历。所以一开始先从root开始，一路把left child推进去，然后当left child没有的时候，pop出最后一个推进去的left child。这个node是没有左子树的，所以首先add它，然后node = node.right，这样再把右子树的左子树全都弄到stack里，再pop，这样循环的保持条件就是stack不等于空或者还有node不是null。这个方法很巧面，用到了栈。

Leetcode 96 这个题很有意思，给定n，求利用1,2,3,...n-1能够构建多少个独特的二叉搜索树，这个我一开始有点蒙。但我发现了一个很好的方法，就是如果不知道怎么写，就先在纸上把简单的几个先写一下。比如n=1,n=2,n=3，写的时候我发现，这个题其实很有规律的，比如n=3的时候，有三种情况，root=1，root=2，root=3,root=1的时候，2和3都在右边，这个时候有几种可能呢？有两种，为什么呢？因为两个数构造搜索树只有两种情况，这是从简单的情况(n=2）的时候推出来的。然后是root=2,root=3，总之这个问题其实可以看得出来是由sub problem组成的，比如由两个数或者1个树构造二叉搜索树。所以这个应该是一个DP的问题，但是当时我想的有点头晕，其实后来我看了解答，这个时候应该想办法更清楚的用公式也好，或者用图表也好，再分析一下就出来了。后来我知道这个数列叫katelan数列。也是一个很有用的数列。今天有点晚，打算明天把这个题事先。

今天终于算是在美国安顿好了，继续开始刷题。
Leetcode 98 有效的搜索二叉树。搜索二叉树的要求是所有在左边树的结点的值都要比root小，所有右边的都要比root大。这个问题我一开始想的很简单，不就是一个简单的递归就可以了嘛》》结果发现并不是，我的递归只检查了左子结点是不是小于root，右子结点是不是大于root，但是搜索二叉树的要求是，左边子树上所有的结点都小于root。 这样的话，只检查最邻近的点就不行，要把左子树上所有的点都检查一遍。所以如果这样想的话，其实对于root，总共要比较n次（n是结点的数量），而对于左边子树和右边子树的点，总的来说又要比较n次，所以最后最好的情况下总共要比较n*k次，最好情况是指搜索树是balance的。这是一种方法，但是这种方法写起来我觉得太过复杂，首先没有办法写递归，我觉得如果要这个思路的话应该是要写循环的。所以在网上看到了另一种解法是每次递归的时候传入两个两个int，一个上限，一个下限，这样就可以直接比较下去，解法也比较直观。
Leetcode 101 对称树，这一题我也想简单了，我一开始觉得只要比较左边和右边相不相等就可以了，后来发现其实还要比较左结点的左结点和右结点的右结点是否相等，以及左结点的右结点和右结点的左结点是否相等。

继续两道树的题目，我发现树其实挺难的。。。
Leetcode 102, 二叉树层遍历。这个我真的想了好久，我一直没有想到合适的方法。最后看了解答才想到用队列。首先把root推到队列里，然后把root的左子结点和右子结点推进去，之后以此类推，利用了队列先进先出的原则，但是要注意每次把元素取出来的时候都要记住这一层有多少个元素。如果都取完了，就开始pop队列的其他元素，也就是下一层。这个方法利用了queue先进先出的原则，今天上了一节算法基础课，我才知道远离queue是抽象的，具体也是用array或者linked list实现的。
Leedtcode 104, 树的最大深度。这个用递归可以很容易实现，每次传入目前的根结点，和目前为止树的深度，之后每次递归都把深度加一，知道最后递归到叶结点停止，返回最后的深度。所以这道题主要利用的是递归

leetcode 114 把二叉树展开成链表， 这个题很有意思，其实是典型的递归问题，首先这个题目的难点在于不能另外申请新的memory， 要不然直接可以重新弄个树，把这边pre-order一遍，但是这样的话，不能直接把值copy过来。这时候，首先需要把左子树和右子树先分别flattern，然后把flattern好的右边子树添加到左边子树后面，最后再把左边整个子树移到右边，这样就ok了。这个问题我想了很久，主要就是递归的这个问题没想好，如果把这个问题想好的话，还是比较简单的。主要就是要把右子树先全部移到左子树上，然后最后再移动过去，这点很关键。