每日5道题

从现在开始到开学前，一定要吧leetcode热门100道题刷完，每天5道，加油！

然后今天只做了三道题，做起来还挺吃力，不过题目还是很有意思的，尤其是第二个水槽的题目。今天还学会了用playground针对testcase调bug，原来一直以为要用eclipse来debug。
Leetcode 10:正则匹配
                  正则匹配我一直有点晕，还好题目中只让考虑了两种符号，'.'和‘*’,因为我觉得出现'**‘这样很难处理，不太明白什么意思。但是看最后提交的结果是没有这种情况的，'*'一定是跟在字母后面，表示前面的字母可以出现任意多次。这道题我也看了网上的解答，采用了dynamic programming的思想。今天这道题和昨天那道题让我大概明白了dynamic programming的大体思路：这一步的结果依赖于上一步。所以，最后的结果得出一定是建立在子问题的结果之上。这道题也是，因为正则表达式匹配的时候可以这么考虑。在完全没有符号的情况下，正则表达式当前步的匹配取决于上一步，假如当前步i和j相同，那么分别从text和pattern把i和j位置的字符去掉，如果前面的能匹配上，i和j就也能匹配上。当有字符的时候，需要考虑‘*’，匹配到‘*’可能出现两种情况，第一种是‘*’前面的字符不出现，那么这时候就要看[i][j-2]是否为匹配的，还有一种情况是'*'前面的字符出现，这时候就有递归的思想，逐步考虑去掉当前的i，text[i]==pattern[j-1]并且如果[i-1,j]能匹配的话，就说明能匹配(最后会逐步递减到没有*前面的字符的状态里）。

Leetcode 11:水容器
                   这道题目很有意思。第一个想到的肯定是n^2的遍历，但是有更好的办法。这时候要想清楚这是一个短板效应，最后的容积取决于最短的板。所以可以i=0,j=length-1开始考虑，这时候边是最长的，最有可能得到最大容积。第二步，假如height[i]<height[j]，就i++，因为无论height[j-1]或height[j-2]取什么值，都会小于height[j]*height[i]，again取决于短板，而且长度也没有最开始长。这样降低到linear time。

Leetcode 15:3Sum
                  这道题有点基础我感觉。其实3sum无法避开遍历的，只不过有更聪明的遍历方法。首先需要对数组重新排序，让数组有序。然后从第一个开始，用两个指针在后面逐步尝试。尝试的时候和上面那道题一样，也可以首尾开始，这样能linear time，最后就是quardratic time。

         明天早点开始，不要拖到这么晚，脑子都不清楚。

上一道关于最大矩形面积的题目最终还是放弃了没有继续做下去，我觉得没有什么算法的问题在里面，至于用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数列。也是一个很有用的数列。今天有点晚，打算明天把这个题事先。

今天做了三道题，本来很有希望打破三道的大关，哎呀科协卡在了求不同路径的问题，我本来以为很简单用一个递归就解决了，结果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。。。

结果今天开局不利，只刷了两道。还是开始的太晚了，明天要早点开始刷。

Leetcode 4， 寻找两个已经排好序的数组的中位数。我觉得这一题可以直接把两个数组重新放在一起排序，采用heap sort的方法可以让时间复杂度为log(m+n)，但是有更好的方法可以直接在短的数组上寻找，把时间复杂度降为log(m)，m是短数组的长度。关键是要理解中位数的定义，中位数是要把一个数组分成长度相等的两个部分。所以如果对数组一和数组二分别进行两个划分，那么当在在数组一上在位置i处把数组一一分为二之后，数组二的划分就是确定的了，因为长度是确定的，为总长度加一的一半（加一是因为数组长度和可能为奇数，这时候左边要多一个数）。这样在短数组上用二分法寻找位置，就能大大降低时间复杂度。

Leetcode 5， 寻找最长回文字符。这一题看了网上的解法，采用Dynamic Programming的方法，核心思想在于把一个长回文数组的判定拆分为短回文数组的判定。一个字符串是回文，首先第一个字符和最后一个字符相等，第二中间的字符串是回文字符串。这样就把问题拆成了小问题。实际实施的时候，维护了一个二维的布尔数组，boolean[i][j]为true表示i到j是回文字符串。这样用i和j遍历字符串，找到最长的left和right的位置，最后返回s.substring(left,right+1)

明天继续把今天落下的三道题补上！

额今天又是三道。Leetcode 17 手机按键字母的所有组合。这个题蛮有意思，和实际很接近。下午用手机敲了半天，看了网上的解法。我一开始想采用hashmap，把每个数字和对应的字符串对应起来，但是很快发现有一个问题，就是不知道要写几个循环，循环的数量取决于输入的数字有多少。其实我发现这种不知道循环次数的非常适合于递归。所以一开始先要建立一个数字到string的mapping，其实不用hashmap，只要索引数字对应到一个字符串数组就好。然后递归调用函数，每次递归的状态改变在于前进一个index，最后递归终止的条件是index刚好等于输入数字长度减一。每个递归里的循环是把所有的可能数字循环一遍。做题的时候发现，java字符串是“”，字符是‘’。

Leetcode 20 判断括号对不对的上。这个是很标准的一道题目，CS61B老师提到过。关键是要利用栈先进后出的原则，最后进去的左括号要最先和右括号匹配。这里还要注意False的情况还有字符串没检测完栈就空了，和最后检测完栈还没空的情况，分别对应右括号多和左括号多。

Leetcode 22 生成括号。这个题目很有意思，因为看这个题目的解析看到了Youtube上一个博主，我觉得他讲的很不错，Back2Back SWE。这道题我觉得是递归的标准题目。其实递归关键在于三点，每个递归其实都对应了一棵树，三点分别是，What's our choice? ——树有几个分岔；What‘s our constraints?——约束决定了此刻树能往哪走;What's our goal?——最后的终止条件。所以在这里面每一步的递归函数要传递进去目前的状态，目前的状态决定了下一步能走什么。同时还要想清楚能有几个分岔，我们的选择分别是什么。在这道题目里，状态就是左括号剩余个数和右括号剩余个数，选择就是下一步输出左括号还是右括号。划重点——1、递归对应了一棵树。2、递归要明确现在的状态和现在能做的选择。3、递归适用于不知道要写多少个循环的情况。

我觉得22题还是很不错的，如果对递归很清楚会对它迎刃而解的。

昨天拔牙做了两道题，没有写，今天补上。
Leetcode 23 合并k个排好序的数组。这个题我一开始想的是先合并两个，再逐次合并，最后合并完k个，合并两个就相当于是merge list了。但是这种方法效率不高。相反其实直接把所有数组合到一起直接排序效率会更高，因为时间复杂度是nlogn。最好的方法是使用堆（优先队列），维护一个长度为3的优先队列，这样每次买入一个元素需要logk，最后时间复杂度是knlogk，比knlogkn要好一些。

Leetcode 31 下一个全排。这个题我觉得是个找规律的题目，题目读了半天，终于明白其实是给定一个排列，然后找下一个比它大一点的排列。因为越靠前的位权重越大，所以如果是降序排下来的数组一定是最大的。如果要找下一个排列，需要找到第一个违反了从后往前升序（正着看就是降序）的数，然后把它和之后的数中比它大又最小的那个数交换，之后再把后面的reverse过来就可以，我觉得问题的关键就是要知道越靠前的数字权重越高。

这几天坚持刷了21道题，不知道是拔牙的原因还是觉得累了的原因，感觉动力不如刚开始那么足了。刚开始对题目总是有很多好奇心，去想知道问题是怎么解决的，但是像Leetcode 31 全排这种我觉得意义就不大，感觉就像是在找规律一样，没有考到数据结构也没有算法在里面，希望自己能坚持下去吧。

今天身体不太舒服，写了一道题。
Leetcode 32 最长有效括号子序列。目前括号的题目这是第三道，第一道是判断括号是否对其，用stack，第二道是生成括号，用递归生成，注意状态转换。第三道就是这一道最长有效的括号子序列。这一题也是用stack，但用的时候，push今去的是括号的index，不是括号本身，这样才能算出子序列的长度。如果遇到一个右括号并且检测到栈为空，就要更新left，让left等于这个右括号，后面才好计算。其实这一题不算难，还是利用了栈的特性，只不过要转一个小弯，不用括号本身，而用索引。

今天依旧一道题。
Leetcode 33 在移动过的数列里找寻一个值，要求time complexity 为 logn。 这道题和以往的二分法查找不一样在于，二分法只要关心target是大于mid还是小于mid就很好查找，但是这道题里无论target大于还是小于mid，都有可能在mid两边。比如4567012， 以7为mid，1在7的右边但是比7小。但这时候要想清楚，这里面和二分法一致的地方在于，每一步只有两种选择，要么找左边，要么找右边。这个我想了很久都没想明白，直到后来在youtube上看到别人画图解释。可以以pivot为分界点，画两个一次函数，有点像当时学的双曲线。然后如果mid在pivot左边，如何移动指针有一套方法，如果mid在pivot右边又有一套方法。而在左还是在右，是可以由midleft与right的比较判断出来的。这里就会有疑问，如果最后left和right之间已经没有pivot了呢。那其实也是一样的，所以其实可以把排好序的数列当成rotated 的数列的一种特殊情况对待，所以这里还是应该用binary search.

今天做了两道题～
Leetcode 34 找到数组中特定元素开始和结束的位置。比如1233334，就是要返回3开始的index和3结束的index。这个题目其实乍一看想了很久，我看了一下网上的解法，其实是这样，用了两次二分法，分别用来找起始点和结束点。但是在着的时候要注意，二分法一般都会用left = mid + 1或者right = mid-1这种，但是这里面要找到起始点和终止点，就不能用+1或者-1了，那这个时候要注意比如[1,1]这种情况，因为这种情况由于（left+right）/2总是等于0，所以就会出现找不到起始点的情况。所以要注意起始点和终止点不一定是left或者right，可能让其中之一。

Leetcode 39 数组合的和。这个题我很开心，因为我自己想出来用recursive的方法，他本质是一个树的问题，遍历所有可能。但是要注意，因为不能有重复，所以要把数组排序，已经遍历过的序列不要再遍历第二遍。我觉得这是一道很经典的题目，可以反复练习。要提升速度的话，还可以用backtrack的方法，每遍历一个数，把target减去当前数。还要注意在调用的程序里的List的存活周期。

感觉刷题慢慢找到了感觉。

今天又是两道题～
Leetcode 42 计算留住的水滴量。 看网上的解析说这个题是google的，我觉得这个题很有新意的，不像之前的题一看感觉很传统。这个题目虽然标的是hard，但我感觉难度还好，关键是要理解题目的意思，主要就是一个需要靠图像理解的题，明白了图像就应该会做了。明白了题意之后，就要像怎么计算，我一开始被卡在这里。后来看了讲解才反应过来应该分每个柱子计算，每个柱子上的水量取决于它左右的柱子的高度，如果左右柱子有一个比它矮，它就留不住水。明白了这点之后，做起来就比较容易了，只要维护两个数组，分别记下i位置处，左边最高的和右边最高的，就能解决问题。
Leetcode 46 全排列。这个题目我觉得非常经典，给定一个没有重复数字的数组，要求计算出全排列。还是和原来一样，为了遍历所有的可能，采用树的机构，用递归解决。但是因为题目给的是int array，这个就比较难处理递归的时候，要把已经递归到的数去掉，但是array又不好改变。这点我看了网上的解法，我觉得比较好，就是每次递归的时候，swap一下，把index和i的数交换一下，因为index是当前遍历到的不更改的地方。然后调用recursive之后，再swap回来即可。我觉得递归要注意一个问题，就是变量的存在周期，比如递归调用的一个函数中声明的一个变量，当函数结束之后还存不存在，这个问题十分地困扰我，明天我要好好看一下这个问题。对于nums和cur肯定是存在的，因为他们是在主函数里生成的，但是最后result add的list是在递归调用的函数里生成的，为什么他们最后会存在呢？总之我觉得递归得好好想想这个问题。这个题目是个经典题目。