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

6.7 做题

70. Climbing Stairs. base case is the first and second steps, the induction rule is the current number of ways is the sum of last two numbers of ways.

62. Unique Paths. the base case is that there is only one way from initial point to initial point(m = 1, n = 1); the induction rule is that the number of ways in current position is the sum of the number of ways in top and left position(dp[j] = dp[i - 1][j] + dp[j - 1])

63. Unique Paths II. 和上一题一样，只不过在induction rule的时候，判断一下当前dp[j]涉及到的obstacleGrid[j]是不是1，如果是1的话，当前dp[j]就得为0，如果是0，那就和上一题一样

120. Triangle. dp[j] represents the minimum path from the bottom to dp[j] position. Induction rule is that dp[j] = the value of current position + the minimum between the dp[i+1][j] and dp[i+1][j+1]. because we can get to the (i, j) position only from either (i + 1, j) or (i + 1, j + 1).

279. Perfect Squares. the induction rule is dp[n] = Min{ dp[n - i*i] + 1 }, n - i*i >=0 && i >= 1就是对每一个n，都一个一个来回凑一遍，看看能不能尽量用多的squares给组合起来，也就是用的1尽量少一些，解释在这里https://leetcode.com/problems/pe ... DP-solution-in-Java

6.7 继续做题

139. Word Break. 这个题的induction rule就是，当前长度的substring，是否可以根据比它长度小的substring的正确与否的结果，和剩下那段长度是否存在与Dict里面的组合来判断；比如当前的检查长度是8，substring是applepen，那么已知检查长度为5的substring为true（apple），而剩下的一段pen又在Dict里面，那么就可以得出，长度为8的这段是true；那么到了长度为13的applepenapple的时候，已知刚刚的出的长度为8的applepen为true，而剩下的apple这段又在Dict里面，所以长度为13的applepenapple也是true

375. Guess Number Higher or Lower II. 这道题不是很明白，induction rule应该就是，在取错了的情况下，当前的i和j范围之内，如果取k为猜测值，那么这个k肯定是要花出去了，然后从i~k-1和k+1~j这两个已经得出的结果里面，找一个更多的拿出来，用k加上，就是当前i和j范围之内并且取k的情况下，要花的钱；那么把k从i+1到j-1都给遍历一遍，找出最少的花钱数，就是dp[i][j]了；就这样对所有的i和j都给循环下去，最后得出的dp[1][n]就是最终结果

322. Coin Change. 这个题目的induction rule就是当前钱总数的票数，等于当前钱总数减去给定币值以后的钱数的票数，再加上1代表这张给定币值的票数；但是不太明白，corner case是怎么判断的

6.9 做题

终于做了一百个题目了，现在要开始学习一些其他内容了，光做题也不行

312. Burst Balloon. 这题和前面的guess number higher and lower II很像，不太清楚的就是int coins = nums[i] * side(nums, start - 1) * side(nums, end + 1);为什么要这么写？而不是i和i-1、i+1

256. Paint House. dp[i][c] represents that the minimum costs from 0 to i if the house i is painted by color c. What we want is to find the minimum cost among the dp[final][c1], dp[final][c2], and dp[final][c3]. The induction rule is dp[current][c] = min{dp[previous][another1 c], dp[previous][another2 c} + costs[current][c]. Because we need to make sure that the current color must be different from the previous color.

265. Paint House II. 基本思路和前一题大概一致，前一题是三个颜色，这一题是k个颜色，所以在k这里就应该多加一次循环；那么技巧就在于，在比较哪个颜色在当前去最小的时候，不需要和上一题一样，一个一个去比，而只需要在k个颜色的遍历时，考虑最小的和第二小的就可以了，这样实现O(nk)

64. Minimum Path Sum. dp[i][j]代表从(0,0)到(i,j)的minimum path sum；induction rule是dp[i][j]从dp[i - 1][j]和dp[i][j - 1]里面选一个稍微小一些的，然后加上当前的grid的值

72. Edit Distance. 要注意三种操作究竟是如何反应到两个word之间的长度上的

97. Interleaving String. 和edit distance在形式上很相似，注意induction rule，只从(i - 1, j)和(i, j - 1)这里推导过来

174. Dungeon Game. induction rule更麻烦了一些，还要注意那个“1”究竟是什么意思，如果有demon那么就要在前面补足血，如果是magic orbs的话就只需要留1滴血就够了

6.13 更新一下

最近没怎么刷题，都在看web相关的网课，有点不好，主次没有分清，要重新继续刷题才是

6.14 做题

169. Majority Element. 这个题就是要求一个数组里面频率最大的元素。首先想到的就是用HashMap来做：先遍历一边数组，统计出每单个元素的频率然后放到HashMap中；然后对HashMap进行一次遍历，找出频率（也就是value）最大的那个key-value pair，这样获得的key就是频率最大的元素。当然这里有另外一种解法Boyer-Moore Voting Algorithm。这个解法就是说，一次遍历，然后暂时统计当前的element的次数，如果次数为0时，那么element换成当前次数。比较难想。

229. Majority Element II. 这个题目和上一题一样用hashmap，只不过对hashmap遍历的时候，把凡是value > n/3的key拿出来放到结果里就可以了

274. H-Index. 这个题目需要有一个bucket，bucket长度比给定array长度多一位；bucket里面的每一个元素的index，都对应着给定array的每一个元素的value，唯一特殊情况就是，如果给定array的某些元素的value特别大的话，就存到bucket的额外的那个位置上；那么对给定array进行遍历，每一个value都去bucket里面寻找自己对应的位置，然后bucket中每一个元素的value，就是对该元素的index在array中的频数统计，额外的那个位置就是array中较大那些数值的频数统计；构建好bucket之后，从后往前进行遍历，并且进行value的累加，直到value累加和能够大于当前的index，就说明找到了h-index了；从后往前累加，就是先加那些引用数多的，并且逐渐降低index

275. H-Index II. 整体思路明白，就是找一个index，使得citation[index]能够比它左边的元素个数len - index要相等或者多；这个index可能有很多，但是要找最左边最小的那个；不太清楚的就是循环条件为什么不是<而是<=，并且最后返回的len-left为什么？

243. Shortest Word Distance.这个题目就是遍历一下当前的数组，然后再遍历的过程中，分别找到两个target所对应的index就可以了；又因为可能出现多个target，因此不能简单返回两者之差；而是要返回两者之差的最小，因此就maintain一个gloabl的res，如果遇到新的target的index，那么就实时更新全局最小即可

非常详细的计划了，楼主加油

6.20 做题

这几天刚刚从国内回来，然后因为网课的平台要关了所以时间都花在看网课上了，然后又要各种坐火车坐飞机，落下了好几天……总之各种理由

244. Shortest Word Distance II.这个题目在构造函数里要建立起每个list里的word和它们在list里面对应出现的位置的list；在函数里面所要做的就是，找出两个target word的位置list，因为这些list都是sorted，所以两个可以一起遍历，然后最终找到最小，所以仍然是O(N)复杂度

245. Shortest Word Distance III.这道题目考虑到两个target可能相同的缘故，因此i2要多考虑一下；如果相同，那么当前的i1和i2都会指向同一个i，所以需要有一个指向上一轮保留的i才对；因此用i1保存上一轮的i2，i2保存这一轮的i即可

217. Contains Duplicate.用Set即可

219. Contains Duplicate II. Use HashMap to store the value as key and index as value. Scan the array and every time we find the existed key, we compare the existed value with the current index. If its gap is not more than k, we can return true.

55. Jump Game. If the current index is i, then the current max length we can have is nums[i] + i. If the current index is larger than the max length we can have, then we will never reach the end.

6.25 做题

这几天从波士顿到旧金山，折腾好几天终于算是安顿下来了，重新开始做题

293. Flip Game. 一个一个检查就可以了，因为是个String，所以先转化成char array，就可以避免一些string的api带来的额外复杂度；如果满足条件，直接进行flip，然后把当前flip完的结果加到result里面，然后变回原样即可

294. Flip Game II. canWin是用来判断当前starting person是否能赢的；那么starting person可能会flip任意一组“++”，flip以后就把当前的string留给opponent继续flip；所以对每一组“++”，翻完以后做dfs，即如果starting person翻了这个，那么留给opponent的剩下的string，opponent作为当前的starting person是否能赢；如果当前oppoent不能赢，那么就是当前starting person赢，返回true，否则返回false。这个就是一个dfs。另外有一个简化的方法，就是canWin(s)是对当前string进行判断，判断当前starting person是否能赢的，那么如果把两个person的person作为key，当前string作为value，就可以表示，当前的person作为starting person来操作当前的string；如果这组key-value被canWin判定能赢，那么就放在一个HashMap当中；通过这种方式记录能赢的key value，那么当dfs一直进行下去，如果遇到了相同的key-value在hashMap当中，这就说明能赢，说明不用继续进行额外的dfs了。通过这种方式来简化复杂度。

290. Word Pattern. 这个题目就把word和pattern给map起来，用线先map好的去检查后面的，如果后面的key不对应value，或者value不对应key，那么就返回false；就这样一直检查下去即可

242. Valid Anagram. Anagram的意思就是，两个String所包含的字母都一样，只是顺序不一样；那么一个方法就是把两个String的顺序按某种方式排列一下，然后进行比较，这个方法就是排序；另一个方法就是，用HashMap，key是26个字母，value是它们在String里面出现的次数，如果每个字母在两个String中出现的次数相同，那么就是valid了；那么当然可以用两个HashMap，可不可以用一个HashMap呢？用一个HashMap去存储阿玲个String中的字母出现次数；所以value就是代表，每个字母能否在两个String的次数相互抵消，一个String为正，一个为负，如果最终是0，那就说明能够相互抵消。

49. Group Anagrams. 归类的题目要考虑HashMap，同一类的要放在同一个key下面。对这个题而言，同一类的就是anagrams的这群，key就是它们排序排好的那个string，因为anagrams排序后的string都是一样的