75. Sort Colors 题目链接：[链接] 这题是给数组排序，数组里面只有3个变量。一个方法是用类似bucket sort，3个桶，统计三个变量出现的个数，然后重构数组即可。 {代码...} 还有一种方法是用three way partition，参考算法这本书上的讲解和程序：[链接][链接] {代码...}

这道题要求所有重复出现的序列，那么可以想到得用hash table，因为这里限制了是10个字符长的序列，所以每次其实是去掉第一个letter，再加一个letter，这个思想和rabin karp挺像的，需要用int或者long来表示string。

这题就遍历所有可能的切分点n然后mergenums1[n]和nums2[k-n]求到最大值，nums1[n]和nums2[k-n]分别是nums1有n个数时候的最大值，和nums2有k-n个数时的最大值。merge部分比较简单，来看求最大值的部分。设产生的最大值是max，max的size是n，num的size是m。现在已经选了了i个digit，最大值是max[0:i]，num用了j个数，现在...

和Count of Smaller Numbers After Self还有count of range sum是一类题，解法都差不多。BST可以做，但是这道题如果输入是有序的，简单的bst会超时，所以得用AVL来做。然后就是binary index tree的做法，计算大于nums[j]2的时候就是拿全部的sum减去sum(nums[j] 2)

这题实际就是给定范围内的range sum，divide and conquer的方法。一路计算prefixSum[0:i]，并把结果放进tree里面，然后计算到prefixSum[0:j+1]的时候，找tree里面有没有满足条件的prefixSum[0:i]，这里的条件是lower <= sum[0:j+1] - sum[0:i] <= upper，那么可知sum[0:j+1] - upper <= sum[0:i] <= sum[0:j...

divide and conquer的题，用bst来做，这种求有多少smaller的题一般都是bst。node里多加一个信息：size表示以node为subtree的节点数。

greedy的思想，这题要让相同字母的character距离至少为k，那么首先要统计字母出现的次数，然后根据出现的次数来对字母排位置。出现次数最多的肯定要先往前面的位置排，这样才能尽可能的满足题目的要求。建一个heap，存char和剩余次数，每次从heap里面取k个不同的字母出来排，把字母放入一个大小为k的q里面等待，直到距离...

bst的值大小顺序实际上就是满足inorder的条件，所以直接中序遍历，过程中维护一个queue，放入k个当前离target最近的值，queue的size=k时，新的值和target的距离如果小于队首的那个值和target的距离那么移除队首，如果size=k，且新的距离大于等于队首的距离，直接退出，返回队列中的所有结果。

动态规划问题，最后要求全部满足条件的path。subproblem是：dp[i]: possible sum of s[0, i+1]，function是：dp[i] = dp[i-k] + (-prev + prev*cur, +cur, -cur)注意s[i-k+1]如果等于0，那么k只能等于1，如果有除的时候也不能是0，开头的数字单独处理，因为前面没有符号，dfs来解。还有个问题是取数字的时候可能 超过int...

224. Basic Calculator 题目链接：[链接] stack，就是感觉条件有点多 {代码...} 简单点的写法，把sign直接用int存在stack里面，'+'就存成1， '-'存成-1 {代码...} 227. Basic Calculator II 题目链接：[链接] 这题就是碰到'*', '/'在加减后面怎么处理的问题。用一个prev来表示之前的number，所以碰到现在是乘的时候就：r...

57. Insert Interval 题目链接：[链接] {代码...}

找到string从头开始最长的palindrome substring：s[0:i+1]那么只要把substring(i+1)的reverse加到s前面就是结果了。找palindrome substring的过程可以用kmp来做优化，由于reverse(s[0:i+1]) == s[0:i+1]，那么就照着kmp里面见prefix数组的方法来查，最后prefix[n-1]就是palindrome的长度，注意两个string并在一起的要加...

利用kmp求prefix数组的方法来做，利用string自身的重复性，prefix[i] = k, k < i表示在s[0, i+1]中，最大的k使得s[0, k] == s[i-k+1, i+1]参考视频：[链接]

150. Evaluate Reverse Polish Notation 题目链接：[链接] stack来做，保存数字，碰到符号的时候就弹出两个数字计算算完后再放入stack，最后stack里面的就是结果。 {代码...}

首先想到的是dfs查找，用left，right，up，down四个变量分别表示最左边，最右边最上面和最下面，最后面积就是(right-left+1) * (down-up+1)dfs查找的时候如果四周有没visited过的黑点就继续search，同时更新四个变量。

dp记录最大的长度，加parent指针存路径。dp方程是：dp[i] = max(dp[j]) + 1, if nums[i]%nums[j] == 0

和300. Longest Increasing Subsequence类似的题，这里变成两个量了，依然是patient sort+binary search的思路。这里先按一个方向排序，另外一个方向按降序再排，这样就可以binary search了。

363. Max Sum of Rectangle No Larger Than K 题目链接：[链接] 参考discussion里的解释：[链接] 先是如何在2d矩阵里找max sum的问题，参考视频：[链接] 然后就是一个array里面找不大于k的最大值问题了:[链接] 要找到最大的sum <= k, 用cumulative sum就是cum[j] - k <= cum[i]，upper_bound就是TreeSet来做了。行...

检查图的连通性及是否有环，可以dfs，bfs，从一个点出发看能不能遍历所有的点，同时visited来检查是否有环。还可以用union find检查是否有环，最后看edge的数量是否等于n-1来判断是不是spinning tree。

dp的subproblem是：dp[i]: i-th ugly numberdp的function是：dp[i] = min(dp[t2] * 2, dp[t3] * 3, dp[t5] * 5)其中，t2-1, t3-1, t5-1分别为上一个*2, *3, *5得到的丑数，所以当前dp[t2]*2, dp[t3]*3, dp[t5]*5分别表示当前由*2， *3， *5得到的最小丑数

枚举所有可能的largest sum，找最小的那个，二分枚举优化复杂度，因为数组不含负数，根据largest sum是否满足条件可以二分结果。largest sum的范围是(sum(nums)/m, sum(nums))，找当前largest sum是否存在，判断存在的标准是：扫一遍array，看实现每个subarray的sum都<=当前largest sum的时候subarray的数量是否小于...

330. Patching Array 题目链接：[链接] 想了半天没想出来，参考discussion里的解法：[链接] {代码...}

469. Convex Polygon 题目链接：[链接] 不会，参考这个博客的解释：[链接] 计算三个点的法向量（叉乘），任意三个点必须同正或同负。这样判断三点组成的两边角度是否小于180。注意考虑90度的情况，这时候叉乘为0。 {代码...}

481. Magical String 题目链接：[链接] 找规律的题，比较无聊。根据前面的结果来得到下一个数字是多少。两个point：i和j 分别指向字符串和ocuurrence字符串。 {代码...}

用一个stack来做，stack里面的字母按增序来排，出现top>cur的时候要把top给pop出来，注意一点是如果后面没有top的话，就不能pop出来，所以先要用个hashmap来保存每个字母出现的次数，次数到0说明后面没有这个字母了，还需要一个visited数组来保存已经在stack里面的字母

enumerate，但是不是结果，而是幂。方法特别巧妙，另外求幂的和还可以优化用快速幂来求。知道幂之后，根据逼近法，可以得到base：k = logm(n) = (long) (pow(n, 1/m)) = (long) (log(n) / log(m))，幂的最大值是min(log2(n), 64)，当然这个是m>1的时候。注意求pow(base, m)不能直接用pow因为java里面double和long的转...

这题的dp方程还是挺难想的。首先subproblem比较容易：dp[i][j]: max coins I can get if there are balloons (i, j) left，有n^2个subproblem。接下来就是方程的问题了。

和那道read n不同的是这次call multiple times，问题就是当前的call可能存在多读了几个字节，那么下一次call read的时候要先算上上次多读的部分，所以要保存上次读的。和读一次一样有两种要考虑的case：

这题和那道Find Median from Data Stream比起来多加了个sliding window。那道题巧妙的用了两个heap来找到mean，还有道题是Slide Window Maximum，同样是slide window的题。还是用两个heap来做，remove这个操作复杂度用了logk。minHeap和maxHeap，maxHeap在保存较小的一半元素，minHeap保存较大的一半元素，0 <= minHe...

360. Sort Transformed Array 题目链接：[链接] 这是个数学问题，抛物线，我们知道 a > 0: 这时候是个凹函数，两遍的值大于中间，所以从两遍开始哪边的大就把结果放到result的右边 a < 0: 这时候是个凸函数，两遍的值小于中间，所以两遍开始扫哪边的值小就把它放到result的左边 a == 0: 这时候是单调增的函数，用...