407. Trapping Rain Water II 题目链接：[链接] 参考discussion里的解法：[链接] 参考博客里的解释：[链接] {代码...}

dp来解，subproblem是：diff[i]: number of paints when current i is different from i - 1, same[i]: number of paints when current i is same as i-1所以dp方程为：diff[i] = diff[i-1] * (k-1) + same[i-1] * (k-1),same[i] = diff[i-1]，滚动数组优化

又是一道dp的题，关键是找subproblem。dp[i][j]表示最少的money you need to guarantee a win，当范围是(i+1, j+1)的时候。所以要求dp[i][j]就应该遍历切分点找出最小的值，这个切分点可能把问题分成左边或者右边，要取最大值才能保证所有的值都能赢。所以dp[i][j] = min(k+1 + max(dp[i][k-1], dp[k+1][j]))注意base ca...

求矩阵里面第k小的数，首先比较容易想到的是用heap来做，maxheap或者minheap都可以，用maxheap的话把全部元素放进heap里面，同时如果heap的size大于k就弹出，保持heap的size为k，最后root的元素就是第k小的。复杂度是k + (m*n - k)logk，其中m = matrix.length, n = matrix[0].length。

451. Sort Characters By Frequency 题目链接：[链接] hashmap求frequency加排序，排序可以用bucket sort or heap sort。 bucket sort： {代码...} heap sort参考discussion：[链接]

448. Find All Numbers Disappeared in an Array 题目链接：[链接] 一般这种类型的题要in place，要么给num[i]赋值成不在范围内的数，要么swap到对应位置。 {代码...} swap的方法见discussion:[链接] {代码...}

遍历每个point，然后找和它等距离的其他point，按距离来保存，比如有一个点a，和它距离都是1的点有b，c，d，那么一共的组合就有6种，包括：[a, b, c], [a, c, b], [a, b, d], [a, d, b], [a, c, d], [a, d, c]。这么算是不考重复的情况下。还有可能b, c坐标完全相同，那么b和c会被当成两个点算两次。

又是一道不像easy的题。。首先是穷举，把小时从0到11，和分钟从0到59所有的可能穷举一遍，1的数量等于num时就加入结果。 参考discussion里的：[链接]

现在easy题都这个风格了额，感觉有medium的难度。。首先sort两个数组。之后如果找到最小的radius，开始想到的是用2 points。一个i指house的位置，另一个j指向heater，循环的invariant是：house[0, i]已被heater[0, j]覆盖，现在来看house[i]，如果

这道题关键是找sub = abcabc这种可压缩的情况，其中sub = s[i,j]。方法比较巧妙，用sub+sub = abcabcabcabc，找第二个s在s+s里出现的位置，如果不是len(sub)，则说明sub有重复，那么就要压缩这个sub，重复次数是len(sub) / indexOf(sub, 1)，重复的string用的是之前压缩过的dpi，index = indexOf(sub, 1)。

这题给的例子太神了根本看不懂。实际上这题的要求是所有点的关于一个y轴对称，x坐标左右全部对称，就是说[[-1,1], [1, 1], [3, 1], [-3, 1]]就是对的，但是[[1, 1], [3, 1], [-3, 1]]就不对，因为[1, 1]没有和它对称的点。[[1, 1], [3, 1]]也是对的，这时候x坐标关于x = 2对称。[[-1, 1], [1, 1], [-2, -1], [2, -1]]也...

greedy，用一个point：number来指向现在到的数，每次碰到"D"，就count"D"的数量，最后碰到I把number + count到number放入结果，更新count = 0。

这题recursion和iteration都可以做，一种思路就是从中间开始往两边延伸，每次c[i-k], c[i+k]有5种可能性: (6, 9), (9, 6), (1, 1), (8, 8)和(0, 0)，其中开头处不能是0。可以加memo或者用dp table优化。

309. Best Time to Buy and Sell Stock with Cooldown 题目链接：[链接] dp来解，要用两个dp array分别表示现在的操作是buy还是sell，优化空间用滚动数组，或者几个int {代码...}

根据题目的描述，移掉k个数字然后得到最小值，肯定是greedy。那么greedy的feature是什么呢？看例子，首先是1432219，k = 3，不去掉1的原因是后面接的是4，当前这一步，看到下一个数比自己大的时候移掉是不划算的，因为移掉这个数之后最高位变成4，是不如保留1小的。所以可以看出规律实际上是从msb开始只要发现比之前有比...

这道题就是找规律，可以看出来下一个permutation的规律是：从右往左扫，找到第一个满足：nums[i-1] < nums[i]条件的，再找到从右到左第一个比nums[i-1]大的数，把它们swap，再把所有i-1之后的数字swap即可。边界条件：1. i = nums.length - 1，这时候i-1之后只有一个值, 2. 数组一直递减，这时候i变成0，没有nums[i-1...

无向图里找路径的问题，用邻接链或者邻接矩阵来建图，用邻接链的话注意两个方向，a/b的时候，既要把b加到a的邻接list里，也要把a加到b的邻接list里面。建好图之后就是查找了，图里面查找用bfs或者dfs都可以，dfs写起来简单点。复杂度没什么差别都是O(V+E)，这道题里面E = equations.length, V最多是2E，所以每次查找的复...

486. Predict the Winner 题目链接：[链接] 看了discussion里面参考的mit算法视频：[链接] recursion + memo 或者 iteration用dp table {代码...}

和Design Hit Counter基本一样，都可以用hashmap，但是timestamp大了之后会有很多无效的时间保存在hashmap里面，要remove的话，可能需要遍历hashmap或者用list辅助，时间复杂度超过O(1)，所以用一个rotate array来做，每次根据新的timestamp改变array。

bit也可以做，保留character为0，改为数字的为1，然后结果就是[0, 2^n]这么多，每个数学遍历一遍求对应的abbreviation即可。

这道题要求vertical的order来保存结果，一开始想到的是用遍历的时候更新index，比如现在的index = 0，有左孩子的话就在最前面插入结果，且shift++。不过这样的话每个subproblem的时间是O(N)了。那么可以先用hashmap来cache，遍历的时候就要根据node所在的column的index来存，根节点的index从0开始，左边的孩子index-1，...

这道题找是否有player赢的方法和N-Queens相似，稍微简化了。统计行列和两个对角线player的情况，两个player分别用+1和-1来记。然后判断是否有一个人赢只需要O(1)的复杂度。当然这么做的前提是假设所有的move都是valid的，棋盘一个地方已经被占用了，就不能走那个地方了。

又是图的遍历问题，就是简单的遍历，所以dfs和bfs都可以做，复杂度也是一样的。这道题要求球不能停下来，即使碰到destination，必须是碰到wall才能停下来。

这道题和numbers of islands II 是一个思路，一个count初始化为n，union find每次有新的edge就union两个节点，如果两个节点(u, v)原来不在一个连通图里面就减少count并且连起来，如果原来就在一个图里面就不管。用一个索引array来做，union find优化就是加权了，每次把大的树的root当做parent，小的树的root作为child。

思路是分别找到pacific和atlantic能够流到的地方，然后求两个地方的交集。找pacific和atlantic能流到的地方，就是这个matrix的遍历过程，可以用dfs或者bfs。复杂度没什么差，dfs写起来简单点。

和安卓解锁那道题很想，那道题步数是m到n，[链接]这道题是1到n，表示数字的位数。backtracking，每次要记录走到的位数作为depth，从msb开始。dp[i]: # of numbers with (i+1) unique digits, dp[0] = 9, dp[i] = (n - i) * dp[i-1]，最后结果是sum(dp[i])，i = [0, n-1], 也可以dfs来做, bottom up。注意最后0的情况，只...

greedy: 先把一组x里面和另外一组y最小元素的组合放进heap，然后每次poll出和最小的，同时放进去有可能成为第二小的组合，即当前y元素的下一个和x元素的组合。

这道题暴力法是可以的，每次把所有在start到end之间的值都更新一遍，不过题目要求要O(k+n)，所以其实每次更新只能用constant的时间。有点像prefix sum的意思，每次只更新第一个值，最后把值加起来，最后怎么确定结束的地方呢？没法知道在哪结束，但是可能让结束之后的地方恢复原来的值，所以要在[end+1]的方法更新成负值...

Flip Game II 题目链接：[链接] dp的题，可以直接暴力dfs，优化可以加memory，只有当所有可能的subproblem都是false的时候，当前结果才是false： {代码...}

这道题给了条件：nums[i] != nums[i+1]，然后两端是负无穷。所以能用binary search做。因为只要知道当前点是递增的，只要往右边找肯定能找到peak，大不了到最后，因为nums[n-1]是永远小于当前点的。左边同理。