假期四个月计划 - 刷题|补基础|看网课|做项目

6.25 继续做题

249. Group Shifted Strings. 回忆一下上一个题，也是group，group的话就是把同一组的放到HashMap相同的key下面，重要就是根据什么key来进行group。这里的key比前面的稍微麻烦一些。例子里面说，"abc" --> "bcd"可以进行转换，"xyz"也是，所以这三个可以分到一起。那么其实就是，如果a到b是移1位，那么b到c，c到d都是移1位；如果a到x是移23位，那么b到y，c到z也是移23位，所以这几个可以被移到一起。但是如果这么比较的话，就相当于要把"abc"和其他所有的String都进行比较，这就已经O(n^2)了，时间复杂度太高，而且这样去比较的话，比较的只是不同位置上字符，移动距离一样；那么这里就想到，如果移动距离一样，就说明String进行了整体平移，字母之间的相对距离位置其实是不会改变的。所以字母间具有同样相对距离的String，就可以被归为同一组里面。那么这里的key就是相邻字符间的距离，比如abc的key就是11，代表b到a和c到b的距离；而xyz同样也是11，bcd也是11，所以这三个是同一组。这样就可以建立HashMap了，后面就简单了

87. Scramble String. 这个题目用recursive去做，实际上是个tree的题目。base case就是当前的两个String是否长度为0，是否相同，是否包含不同字母；recursive rule就是去对左边的左和右边的右、左边的右和右边的左，以及左边的左和右边的左、左边的右和右边的左进行比较。

179. Largest Number. 这个题目就是把String array里面的String看看用什么方法拼接起来，才能得到最大值；那么一般想要进行String Array的string组合，就希望可以先去排序以下，排好序就可以按次序进行组合了，但是这里的问题就是，如果一个String是9，另一个String是10，显然10比9大，但是10如果排在9前面的话，就变成了109，显然没有901大；所以仍然是需要进行排序，但是应该换一个排序策略。那么对于自定义的排序策略，就要使用Comparator，就要去Override那个compare方法。而这个compare方法是基于两个obj进行比较的，那么就针对于10和9，如何比较这两个之间的优先级呢？既然在这里希望得到的优先级，就是910要优于109，而901就是string1 + string2，109就是string2 + string1，那么就去单纯比较这两个就可以了，即(string2 + string1).compareTo(string1 + string2).这样就完成了最核心的compare方法。然后根据这个方法去Arrays.sort，然后顺次拼接起来即可。

161. One Edit Distance. 这个题目首先就是进行同步遍历，遇到第一个字符不同的时，就可以进行该字符后面的子串比较了：一个字符的不同是被允许的，因为可以利用三种操作进行edit；那么三种操作实际上是根据三种情况衍生而来的，如果长度相同而字符不同，就应该进行replace，如果长度较大而字符不同，就应该进行delete，如果长度较小而字符不同，就应该进行insert；不管怎样，操作完以后，如果replace就应该都比较i + 1之后的，如果delete就应该比较i之后和i+1之后，如果insert就应该比较i+1之后和i之后的。这里其实和edit distance的那个DP题差不多的

6. ZigZag Conversion. 这个题只要找到规律就可以了，然后用笨办法做即可。

6.27 做题

367. Valid Perfect Square. 这个题其实是查找的题目，从1开始一直找到num，直到找到一个数res，使得res*res == num；既然是查找，并且从1到num是sorted的，所以就要使用binary search；确定了利用binary search以后，首先要规避一些overflow的情况，比如如果给定的num接近Integer.MAX_VALUE，在res*res的过程中，肯定会溢出，这时就要进行一些判断，如果res > Integer.MAX_VALUE / res的话该怎么办；另外根据平方的特性，可以缩短left和right的距离，不一定从一开始一直找到num

365. Water and Jug Problem. 需要借用数论的知识Bézout's identity：如果一个数z是另外两个数x和y的最大公约数的倍数，那么这个数就可以被表示为z = a*x + b*y，也就可以经过一系列操作后被x和y所组成。那么这个题目首先要求两个数的最大公约数GCD，然后验证GCD是否能够整除目标数z

204. Count Primes. 最一般的办法就是，从小到大检查num范围内的数，如果是Prime就计数增加；检查prime的方法就是从小到大检查是否有能被当前数整除的数，如果没有就说明没有因子，那就是Prime；更好的办法是，用额外的空间记录下已经被确定为不是Prime的数；那当然不能先验证再存储，存储的目的是存储以后的数从而避免验证；方法就是，如果当前数是Prime，比如从2开始，那么2的所有倍数都可以确定为不是Prime，存储标记这些倍数，那么以后如果遍历到被标记的数就不需要检查了，直接确定就好了。

1. Two Sum. 这个题目就用一个HashMap去存储值和对应的index，因为HashMap可以用O(1)的时间找到key，那么当遍历到数组的一个数的时候，就可以用O(1)的时间在HashMap中检查，当前数的complement是否已经出现过了；如果已经出现过，就说明当前数和之前数组中的某个数，可以组成two sum，那么直接在hashmap中找到对应的index返回即可；如果没出现，那么把当前数作为key，当前index作为value，put进HashMap当中，作为后面的数的可能的complement

167. Two Sum II - Input array is sorted. 既然事先sorted过了，就没必要用HashMap存储了，直接用双指针，用类似binary search的方法，不一定减少时间复杂度，但是可以确定下一次的方向总是正确的。

6.27 继续做题

15. 3Sum.这个题目因为是3sum，所以必须是O(n^2)，所以可以先sorted一下，这样也是在复杂度范围之内，然后的方法就和Two Sum II一样了，最外层套一个遍历即可；然后为了避免重复，可以用一个Set，或者在遍历的时候，把value相同的相邻index都跳过，就可以避免了。

16. 3Sum Closest. 这个跟3Sum大差不差，仍然是先sort，然后外面一个遍历，里面双指针，每次指针更新后，都检查一下，如果更close的话就更新一下最终结果

259. 3Sum Smaller. 为什么是count += right - left而不是count++？没懂

18. 4Sum. 这个题和3Sum一样，就是外边多套了一层循环

231. Power of Two. 用Bit做，因为如果n是Power of Two的话，那n = 000...00100..00，只有一个1，而n-1 = 000..00011..11，原来那个1变成0，从这以后都变成1；所以用n和n-1取&运算，因为&运算必须全为1才是1否则为0，那么肯n&n-1肯定是0；这一篇给了非常好的解释https://leetcode.com/problems/po ... -Bit-operation-Math

7.2 做题
这两天主要在看Spring，之前简历上的SpringBoot项目被包装的蛮好看，但是并没有上线，而且对Spring本身掌握的就不太扎实，所以一直在看Spring和SpringBoot，准备接下来的一个月能看完Spring的基础并且开始做一个SpringBoot的项目，然后用微服务架构改造一下，这样就很好了。但是又浪费了很多刷题的时间，效率还是需要再提高一些。

129. Sum Root to Leaf Numbers. Tree的题目，计算Tree的从root到leaf的每一个path的和，可以考虑是recursive，DFS方法。对Tree来说有三种recursive方法：pre-order，in-order，post-order。它们的区别无非就是，do some business的位置，和对left和right子树进行recursion的先后次序关系。那么这个题目，由于需要先取到当前root的值，并计算到以目前的root为leaf的整个path的sum，然后把这个sum传下去，以便可能的left和right子树的继续计算，那么显然是pre-order，先计算当前root的相关，然后call recursive function on both left or right。另外要注意的问题就是，这个题目要求的是所有的path的sum，而沿着每个recursive tree的每条path传下去的，只能是sum of current path，而因为call stack的原因，这个值是会根据recursive tree的深浅而改变的，所以最终肯定不能返回这个值。那么就应该maintain一个global的total，来计算每个path的总和；而随着recursive tree往下传的那个参数变量，应该记录以当前node为leaf的到目前为止的单一path的和

298. Binary Tree Longest Consecutive Sequence. 这个题目的模式和129题很类似，都是pre-order traversal，都是要 maintain一个global的value不会随着recursive tree的深浅而改变，同时dfs helper function的signature的设计上，都要有一个cur_value来记录计算当前所要求的值。这个题目的意思就是，要找到最长的连续sequence，其实就是要找1-2-3-4-5-6-7的这种连续递增整数。那么在pre-order的do some business部分，1）就应该去验证，当前root的value，是否能够和它上面的path组成consecutive sequence，也就是验证，当前root的value是否等于它parent的value + 1，如果通过验证，那么当前sequence的长度就要加1，否则重置当前长度；2）接下来去把包括当前root在内的consecutive sequence的长度，和全局的最大长度进行比较更新，实际上相当于记录。pre-order结束后，就可以call recursive function on both sub trees了

111. Minimum Depth of Binary Tree. 这里我用的pre-order traversal的方法，模式和129和298的方法差不多一样，仍然是maintain了一个global的min，然后dfs的signature的参数里有一个cur_val；每次do some business的时候，首先要增加当前path的长度，然后判断是否为根结点，如果是的话，那么当前path的长度就是当前path的depth，就可以和全局最小进行比较；如果不是根结点，那么call recursive function on both subtrees

104. Maximum Depth of Binary Tree. 这个题是获取Binary Tree的最深分枝，和上一题最浅分枝不同。这一题只需要简单对左右子树进行recursive function，获取左右子树的最深深度，然后进行两者的比较，然后加上当前层的即可，这是post-order的类型。而最浅分枝的那个题，则是要先计算当前的深度和全局最小的比较，为什么两个不一样呢？这个不太明白暂时

110. Balanced Binary Tree. 按照分类来说，这个题目好像应该是一个post order的题，但是我做成了pre-order的题目。我的做法是，首先获取左右子树的高度，然后检查当前左右子树是否balanced，即检查高度差是否大于1，如果大于1直接返回false；检查完以后，在对左右子树分别进行recursion，必须两者同时为true，才能说明是balanced。那么获取高度的这个方法，同样要用recursive的方法来进行。

7.3 做题
从明天开始做题又要断了，因为要出去玩好几天

124. Binary Tree Maximum Path Sum. 这一题的重点就是，recursion function向上返回的，是一个分支，但每一次recursion进行post-order时的do some business，都是去比较一个整个Path和当前全局最大的操作。那么进行call recursion function on both subtrees的时候，向下索取的是左右两个分支的值，加上当前的root.val就组成了current root的Path Sum，用它去和全局最大进行比较和更新。做完之后，当前层要向上返回的，则是以包括current root在内的一个分支的数值，当然可以是current+left也可以是current+right，选一个最大的就可以了

250. Count Univalue Subtrees. 这个题目和前面的题目很像，一开始maintain一个全局变量作为计数器，然后写一个helper function。function是dfs，首先进行base case判断，然后进行call recursion function on both subtrees，然后进行post-order。这里进行的recursion function是对左右子树的，向下获取的，是左右子树是否为Univalue的判断；在当前层或者current root所进行的post-order的do some business则应该是判断以当前节点为root的subtree是否为Univalue。判断逻辑比较麻烦但是很简单：只有当前节点的左右子树都是true，当前subtree才有可能是true，否则都是false；而如果左右子树都是true，则又分四种情况：左非空右非空，这样就要比较当前节点的value和左右子节点的value；左非空右为空，这样就要比较当前节点的value和左子节点的value；左为空右非空，这样就要比较当前节点的value和右子节点的value；左为空右为空，那么当前subtree肯定是true。最后往上返回的当然就是当前subtree是否Univalue，并且返回之前，要对全局计数器进行更新，如果为空那么就要加1.

366. Find Leaves of Binary Tree. 这个题目不太明白。逻辑是这样的，首先有一个helper function来判断，当前节点是不是leaf，如果是的话，返回true并且当前节点置于null；如果不是，向上返回false之前，要判断左右子节点是否为leaf，如果是的话，当前节点置于null。不太明白

337. House Robber III. 这个题目最简单的方法就是，rob是要返回当前节点为root的最大值，那么根据不能取相邻parent-children的准则，这个最大值的两种情况就是取或者不取当前节点，取当前节点的话那么当前节点的两个子节点就不能取，不去当前节点的话，那么最大值就应该是两个子节点的最大值的和。这篇给了非常好的解释和优化https://leetcode.com/problems/ho ... ling-of-the-problem

107. Binary Tree Level Order Traversal II. 这就是最一般的BFS题目，每次记录当前层结果，只要插入到最终返回的list的首个位置，就可以实现bottom-up了，对BFS本身不产生任何影响。

7.5 做题
今天做题时间比较短，只来得及做三题

291. Word Pattern II. 这个题目没怎么懂。希望比较的是str的子串和pattern的子母，由于没有了空格，意味着str的任意长度子串都可能被作为待检测对象。因此就需要对任意长度的子串进行检验，如果检验不过关，那么马上退回来，调整子串的起始位置或长度，进行重新监测，这就是backtracking所在。而对于pattern来说依然是一个一个检查。那么要考虑的就是，如何调整子串的起始位置或长度了？起始位置需要通过调用dfs时传入的起始index来确定，每次往下调用时，检查到哪个位置就传入哪个位置（当然这里实际上需要对每个位置开始的子串都进行检查）；而子串长度则需要在dfs function内部进行设置，从起始位置开始一直到str的末尾，可能的子串都要一一检查，因此相当于设置一个for loop去loop子串可能出现的长度。那么如何判断返回是true还是false呢？也就是说如何判断base case呢？首先是str和pat的位置，如果都检查到头了，说明没有出现错误，那么肯定是true；如果一个到头一个没到，说明本身pattern就给错了，肯定是false。然后就是，如果当前检查到的pattern之前已经匹配了一个子串了，那么就把这个子串拿出来，和str当前的起始位置开始的相同长度子串开始比较，如果有任何不一样，都是false；如果匹配通过，那么检查下一个pattern，并掠过当前str的这个长度的子串即可。

17. Letter Combinations of a Phone Number. 这个题目是dfs，其实比较典型。recursion tree的层数，由digits的数字的个数决定；recursion tree的当前层的节点数，由digits当前数字对应的字母集的个数决定。base case是recursion tree进行到底，即digits所有数字对应的字母已经选定完毕。对于每一个node所对应的节点，要进行for loop去找寻字母集的所有字母进行组合。

320. Generalized Abbreviation. dfs的层数是word的长度，dfs每层的节点数是要么保留字母、要么替换为数字。

7.10做题

这几天更新的不是很频繁，因为刚刚回到波士顿，然后这一阵子在看Spring，Spring真的内容太多了，之前想直接看视频做spring boot的项目真的很不现实，很多知识根本不会看视频再多遍也没用；但是重新看spring的基础有感觉遥遥无期。。。。。。

93. Restore IP Addresses. 这个题目用dfs，recursion tree的层数就是IP地址格式规范的4个，recursion tree每个节点的子节点数，就是IP地址格式规范的3位数字或者1位数字（0）；dfs的base case就是，只要当前的string被组成完毕，或者当前的IP地址的四个位置都被填满，那么就说明到底了，要判断是否添加结果，如果两个条件同时满足，说明组成了正确的IP地址，否则就是错误的；那么在每一个recursion function当中，就是在当前IP的某个位置上，从当前string的首个数字开始一位一位的试，直到位数越界，然后把试好的数字添加给当前组成的IP，当然这里要注意，如果当前数字越界的话（>255），就要进行剪枝

282. Expression Add Operators. 这个题目的层数就是给定表示一串数字的String的长度，当然不一定是长度，因为每次选取进行操作的数字长度不同；recursion tree每个节点的子节点数，就是要求的加、减、乘操作；base case就是，每当按照顺序把num String的所有数字组成好表达式之后，看看表达式的结果是否和target一样；具体在recursion的时候，首先就是从当前进行到的num的位置开始到num的结尾处进行遍历，把以当前position开始的所有能取得数字全都取一遍以获取当前数字（具体当然就是用substring来做），有了当前数字，就要么加要么减要么乘到已经组成的表达式当中，然后向下dfs。注意的就是，不仅要track当前组好的表达式，还要track当前组好的表达式的值；那么这里就遇到了问题，如果当前组好的表达式只有加减，但是后面紧接着要跟一个乘法怎么办？这种情况下如何进行表达式值的track？这里hint告诉了1 + 2 - 4 * 12 --> -1 - (-4) + (-4 * 12) --> 3 + (-48) --> -45 (CORRECT!)，用这种方式才可以。

369. Plus One Linked List. 这里是给一个数字加1，那么既然是加法肯定就涉及到进位的问题；进位的话，就要从后往前一个一个进位；而这里加的是1，如果后面的数字全都是9，那么这些数字变为0，并且往前进；一直往前进直到遇到第一个不是9的数字就可以了。那么这里给的是一个linkedlist，linkedlist要找到最后一位，肯定要一步一步去往后进行遍历。那么在遍历的过程中，就可以找到从后往前数第一个不是9的数字，记录下来。这样，在加1的时候，如果最后一位数不是9，那么就直接加；否则，找到这个记录下的第一个不是9的数字，加1，然后再往后遍历，后面的都变成0。

2. Add Two Numbers. 用dummy node就可以了，加起来以后要记得考虑carry的问题

160. Intersection of Two Linked Lists. 这个题可以用比较一般的方法来解决，就是先获取两个list的长度，然后比较长的那个往后next，直到剩下的长度和短的list的长度相同，这样两个list同步往后找，直到找到相同的节点就可以了；还有另一种方法，不需要事先获得长度，而是把两个list看成一个圈，然后循环往下走，这个有点像找环的那个题目。解释在这里
https://leetcode.com/…/Java-solution-without-knowing-the-di…!

It works because pointer A walks through List A and List B (since once it hits null, it goes to List B's head).
Pointer B also walks through List B and List A.
Regardless of the length of the two lists, the sum of the lengths are the same (i.e. a+b = b+a), which means that the pointers sync up at the point of intersection.

If the lists never intersected, it's fine too, because they'll sync up at the end of each list, both of which are null.

21. Merge Two Sorted Lists. 这个用dummyNode一个一个往后面比较遍历即可。

234. Palindrome Linked List. 第一步，找中点；第二步，reverse后半部分；第三步，一个一个往后比较

7.11 做题

143. Reorder List. 这个题跟明确，首先找中点，然后后半段进行reverse，最后来两个分段进行一个一个连接起来也就是reorder；要注意的就是，找完中点后，要记得把两个半段给切断，否则在最后reorder的时候实际上两个段仍然是连在一起的，这样就会TLE

142. Linked List Cycle II. 这里是一个trick，假设从初始节点到cycle开始点距离为A，slow进入cycle后到slow和fast相遇的距离为B；这时可以确定slow走了A+B，fast走了2A+2B，而由于fast是从后追上来的，所以fast比slow多跑了一个cycle的距离，因此cycle的长度N = 2A+2B-(A+B) = A+B；那么在这种情况下，由于slow已经在cycle里走了B的路程，剩下只要走A的路程就可以到起点，而A又正是从起始点到cycle开始点的距离；这样只需要再使一个指针从起始点开始，和slow同步往前走，那么他们就可以同时到达cycle起始点。

148. Sort List. 这个题目就是基于LinkedList的merge sort。对于merge sort来说就是，先分两半，然后如果这两半都能够被sort的话，那么只要两个merge起来就可以了；而那两半都被sort的过程，就是recursion fuction出现的地方

25. Reverse Nodes in k-Group. 这一题目主要是看如何操作k-Group。对于一个k-Group，重要的节点就是，k-Group的首个节点的前一个，k-Gourp的最末节点，和当前操作的节点。每次循环就是，把当前最前的节点插入到最末节点的后面，知道首个节点的前一个的后一个是最末节点为止；然后下一次循环之前要固定好这些重要节点。一直循环下去，知道要固定的最末节点为空，就说明到头了。具体在注释里都标明了。

61. Rotate List. 先首位连起来，然后找到应该切断的点，然后切断即可。注意这个过程中要保持对头节点的控制。

作为转专业选手希望和楼主一起加油！

7.11 继续做题

今天又做了四个题目，感觉一般般，可能时间太紧张了，这些题还需要重新做和复习

350. Intersection of Two Arrays II. 这个题目和上一个找两个array交集的题目一样，上一个题目是不考虑重复，而这个是考虑重复。不考虑重复的是用HashSet，那么考虑重复的就应该用HashTable，因为HashTable的value可以用来记录重复的次数。第一步，遍历其中一个array，在HashMap记录下所有的元素和它们在该array中出现的次数；第二步，遍历另一个array，去HashMap中找是否存在对应的元素，如果存在，并且次数仍然大于0，那么就可以被看作是intersection而放到结果里，当然放完以后，HashMap中对应元素的次数也就是value要减1；第三步，直接返回结果即可。

315. Count of Smaller Numbers After Self. 这个题完全没懂，有一种方法使用merge sort做，另一种方法是建立起BST来做，discussion都有详细的解释。总之就是没看懂

300. Longest Increasing Subsequence. 用dp。先建立dp数组。遍历nums数组，如果当前数比dp的最大的数（也就是最后的那个）还要大，那么直接插入dp的最后一位；如果当前数不在dp的范围之内，利用binary search查找当前数在dp内的位置，然后放进去就可以了。其实这个题也不是特别理解。

354. Russian Doll Envelopes. 这个题目首先需要根据width升序、height降序进行排序，然后再用LIS来计算结果。解释在discussion里面有，重点还是LIS。LIS现在有些可以理解解法了