Hint

10.44.89
25.reverse nodes in group (write)
34.Search for a Range(write)
116.write
188. Best Time to Buy and Sell Stock IV(write)


4.median of two sorted arrays
 	  Median can divide array into to arrays with same length. We can choose the shorter array and use binary search.Searching i in [0, m], to find an object `in` that:B[j-1] <= A[i] and A[i-1] <= B[j], ( where j = (m + n + 1)/2 - i )
	a.If(B[j-1] <= A[i] and A[i-1] <= B[j]) we find the median.
	b.If(B[j-1]>A[i])  lo=mid+1;
	c.Else hi=mid-1;

5. Longest Palindromic Substring
   1.check every single character if they can be the median of the palindromic substring

11. Container With Most Water
	Two pointer,i and j,pointing to start and end.Count the capacity and move the shorter one.

15. 3Sum
	Skipping the duplicate number can remove the duplicate answer.Because the first duplicated number contains all the possible solution

22. Generate Parentheses
	if(left<n) can appedn("("),then backtrack, and if(left>right) can append(")")

31. Next Permutation
	a.start from the last element,find a[i]<a[i+1]
	b.swap a[i] and the smallest element than larger than a[i] in a[i+1]~a[n-1]
	c.reverse a[i+1]~a[n-1]

40. Combination Sum II
	for (int i = cur; i < cand.length; i++){
       if (i > cur && cand[i] == cand[i-1]) continue;    
       //每层只能用重复序列的第一个元素
       backtracking
    } //can avoid duplciate

45. Jump Game II
	count the farthest position every step can reach
	when use bfs and input number[] like 5 4 3 2 1 1,it will cost n!

47. Permutations II
	to remove duplicate 
	for(int i=0;i<nums.length;i++){
		if(used[i]) continue;
		if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
		// 对于 1 1 1 2 3 !used[i-1] 说明前一个1开头所组成的所有permutation已经
		//全部写完了，所以要跳过，但是对下一层的使用没有影响（其实跟40题的效果一样）
		backtracking;
	}

48. Rotate Image
	clockwise rotate
	first reverse up to down, then swap the symmetry 
	 1 2 3     7 8 9     7 4 1
	 4 5 6  => 4 5 6  => 8 5 2
	 7 8 9     1 2 3     9 6 3
	anticlockwise rotate
	first reverse left to right,then swap the symmetry
	1 2 3     3 2 1     3 6 9
	4 5 6  => 6 5 4  => 2 5 8
	7 8 9     9 8 7     1 4 7

53. Maximum Subarray
	use dp,dp[i] means the maximum subarray end at i.Thus dp[i+1]=(dp[i]>0? dp[i]:0)+nums[i+1];the max dp[i] is the answer

56. Merge Intervals
	sort intervals according their start points. the start point of next interval would <= or > end point of previous interval

57. Insert Interval
	a.add all the intervals ending before newInterval starts.
	b.merge all overlapping intervals to one considering newInterval.
		start=smallest start among overlapping intervals
		end=largest end among overlapping intervals
	c.add all the rest intervals to result

72. Edit Distance
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) 
                    dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));
            }
        }
        because we only use [i-1][j-1],[i-1][j] and [i][j-1], the code could be 
        optimized to O(n) space. temp=dp[i-1][j] ,pre=[i-1][j-1]


91. Decode Ways
    int dp[]=new int[n+1];
    dp[0]=1;
    dp[i]=dp[i-1]+((i=nums.length-1||nums(i+1)!=0)&&Integer.parserInt(s.substring(i-1,i+1))在10到26之间)？ dp[i-2]:0;

98. Validate Binary Search Tree
              10                 1
             /  \               /
            5    15            1 
                /  \
               6    20 
    trees above is not a valid BST


114. Flatten Binary Tree to Linked List

	private TreeNode prev = null;
	public void flatten(TreeNode root) {
	    if (root == null)
	        return;
	    flatten(root.right);
	    flatten(root.left);
	    root.right = prev;
	    root.left = null;
	    prev = root;
	}
	将右边展开之后的root赋值给prev，brilliant solution

Best Time to Buy and Sell Stock
    T[i][k][1/0] i=day,k=transaction, 1/0 stock at hand 
	1.transaction k=1
		it means Ti00=0，
		    for (int price : prices) {
		        T_i10 = Math.max(T_i10, T_i11 + price);
		        T_i11 = Math.max(T_i11, -price);
		   	    }
	2.k=Infinity
	    T_ik1=Math.max(T_i(k-1)0-price,T_i(k-1)1);
	        for (int price : prices) {
		        int T_ik0_old = T_ik0;
		        T_ik0 = Math.max(T_ik0, T_ik1 + price);
		        T_ik1 = Math.max(T_ik1, T_ik0_old - price);
	   		}
	3.k=2
		for (int price : prices) {
	        T_i20 = Math.max(T_i20, T_i21 + price);
	        T_i21 = Math.max(T_i21, T_i10 - price);
	        T_i10 = Math.max(T_i10, T_i11 + price);
	        T_i11 = Math.max(T_i11, -price);
  		}
  	4.with cooldown
  		for (int price : prices) {
	        int T_ik0_old = T_ik0;
	        T_ik0 = Math.max(T_ik0, T_ik1 + price);
	        T_ik1 = Math.max(T_ik1, T_ik0_pre - price);
	        T_ik0_pre = T_ik0_old;
    	}

124. Binary Tree Maximum Path Sum
	最大值也可能只包括单个节点，或者是节点加上左树或者右树

128. Longest Consecutive Sequence
	1.用map储存数字number[i]的连续长度。找到他number[i-1] 和 number[i+1]的长度，加起来就是number[i]的长度，并且跟新本连续序列两个端点的长度值
	2.或者把所有的数字存入set中然后在一个个的拿出来，如果左右有相邻的，就跟着拿，并且统计长度。

132. Palindrome Partitioning II
	找到以每个char为中点的最长palindrome

134. Gas Station
	只要sumcost<=sumtotal,就一定能循环

137. Single Number II
	    int ones = 0, twos = 0;
		    for(int i = 0; i < A.length; i++){
		        ones = (ones ^ A[i]) & ~twos;
		        twos = (twos ^ A[i]) & ~ones;
		    }
	    return ones;
	ones中的int的32位，为1就表示这一位出现了一次，如果大于1次或者是等于零次，就为0.
	twos中的int的32位，为1就表示这一位出现了两次，如果大于2次或者小于两次，就为0.

139. Word Break
	a. dp
	b. dfs with memo(在回答能不能或者最小最大步数这种，bfs和dp比dfs优秀，dfs时间效率n！，加上memo才能达到n^2/2)

145. Binary Tree Three-order Traversal
	就按照递归的思路写就行，只是注意preorder和postorder都需要set去记录是否已经访问该节点

146. LRU Cache
	hashmap中的val是一个数组，里面有val和重复的次数，

148. Sort List
	对于linkedlist merge sort只需要constant space，因为它不需要复制数组

151. Reverse Words in a String
	String s, s.trim()=remove the leading and trailing space;
	s.split("\\s+") 按照多个空格和回车来分离s

152. Maximum Product Subarray
	数值零是分界线
	其实就是看是偶数个负数，还是基数个负数，所以分别采用左边扫描和右边扫描

155. Min Stack
	用另外一个stack维持一个递减序列

166. Fraction to Recurring Decimal
	注意正负号和除数太大，被除数*10之后超限

172. Factorial Trailing Zeroes
	return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);

179. Largest Number
	比较String a+String b 和String b+String a的大小即可