LeetCode 做题笔记

LeetCode 做题笔记

前面的想起来再记录吧！

5. Longest Palindromic Substring
	隔了半年了。终于把马拉车算法给实现了。
	算法关键：
		1. 预处理string。 把"ABC"处理成"^#A#B#C#$"就可以了。

		2. P[i]表示从下标i开始，可以向单边延伸的长度。
		   并且，P[i]也是删除掉所有'#'符号之后的回文长度。

		3. 计算原回文的位置。 start = (i - P[i]) // 2

		4. 注意事项：
			P[i] = min(P[i_mirror], R - i)

			if i + P[i] > R:
				center, R = i, i + P[i]

	expand from center也是一个很不错的办法，而且挺好实现的。

13. Roman To Integer
	testcase不足：考虑“IXCM”

14. Longest Common Prefix
	divide and conqure方法！
	step = 2
        while(step < 2 * len(strs)):
            for i in range(0, len(strs) - int(step / 2), step):
                strs[i] = common_prefix(strs[i], strs[i + int(step / 2)])
            step = step * 2
        return strs[0]
    要记住这个写法！

15. 3 Sums
	经典题目还是要挤一挤！
	关键点是sort，这样之后可以two pointer搜索。

16. 3Sum Closest
	还是需要先sort，然后two pointer就可以了。
	加上一些沙雕优化hhh

17. Letter Combinations of a Phone Number
	直接建立一个mapping，然后backtracking也行。直接bfs生成也行。

21. Merge Two Sorted Lists
	加一个Dummy就好写多了。

23. Merge K sorted List
	每个list一个pointer，和merge 2 list类似做法？
	那么找最小的需要 K 比较。 整体就是nK。
	用min heap找最小， O(log(K)N)

	Python3: from queue import PriorityQueue
			 Avoid compare between user-defined bojects, put(  (value, idx, object) )

	另一个思路， divide and conquer， 两两合并，不断汇总

25. Reverse Nodes in k-Group
	emmm。
	用递归做挺好做的。
	不过用loop也可以做，二层反转。虽然代码不好写。

26. Remove Duplicates from Sorted Array
	做吧。

29. Divide Two Integer
	不能用乘除法和取余。
	一直做减法，记count。 这是一种做法。
	优化一下：1 2 4 8 16 做减法， 然后循环

30. Substring with Concatenation of All Words
	好题。思路需要清晰。

	有一个关键点是单词长度一样，所以可以遍历，要不然只能DFS。

	不需要每一个下标都重置count和seen_word。
	可以用类似KMP的思路，牢牢结合word长度一样这个特性，采用滑动窗口的思路做

	退出码为0，成功找到一个candidate，i只能往前走一个word的长度
	退出码为1，substring内单词个数超了，i往前走到合适位置
	退出码为2，substring内有非法字符，i可以跳过全部

31. Next Larger Permutation
	关键一：如果一个数是非升序排列，不可能有比它大的排列。
	关键二：一个非升序排列，反转后就是升序排列，也就是最小的排列。

	所以找最右边的升序pattern，从右往左找第一个比它大的，交换。
	这是右边的仍然是非升序排列，反转后生成最小排列。

32. Longest Valid Parentheses
	很关键的一点，我想了很久是错的。

	不能用二分法找最大合法长度。
	因为(())()(())，246都可以，但是8不行，但是10又可以。

	不过验证是否存在长度为N的合法括号群，确实可以用O(N)实现。
	用deque加滑动窗口实现嗷。

	没做出来。看答案了。
	都是O(n)就可以找到最长。
	dp[i] = 2 + dp[i - 2]                         # case1: ....()
	dp[i] = 2 + dp[i - 1] + dp[i - dp[i - 1] - 2] # case2: ....))

	用stack做也可以。
	ans, stack = 0, [-1]
	for i, c in enumerate(s):
		if c == '(':
			stack.append(i)
		elif stack:
			stack.pop()
			if not stack:
				stack.append(i)
			else:
		ans = max(ans, i - stack[-1])

	还可以左边扫描一遍，右边扫描一遍。


33. Search in Rotated Sorted Array
	这种题目，真的是我的软肋。

	思路还是二分法，找到mid之后判断mid在高位还是低位。

35. Search Insert Position
	就是binary search。需要复习。

37. Sudoku Solver
	这应该是我接触的backtracking第一题。
	我的做法是预先遍历一次grid，用三个collections.defaultdict(set)来做。

38. Count and Say
	emmmm。。。考点是loop吗？

39. Combination Sum
	典型的backtracking问题。
	如何避免重复？加一个起始位置记录。

40. Combination Sum II
	和 I 的区别是candidate不是set了。为了避免重复，需要sort。
	并且step into的条件需要增加。

41. First Missing Positive
	交换元素，放到该放的位置。记得用while。
	至多发生N次交换，最坏再for loop访问N-1个元素。O(2n)。

	或者不交换，用负号标记也可以。

42. Trapping Rain Water
	横着想：
	可以用stack。里面装（index，height）
	对每个元素，如果height > top's height，就pop top。
	temp = stack.pop(-1)
	if len(stack) == 0: break
	distance = i - stack[-1][0] - 1 //关键，长度是算的左边的bound
	temp_height = min(stack[-1][1], h) - temp[1]
	water += distance * temp_height

	竖着想：
	每一个slot可以放的水量是他左右max的min。 -> 直接搜索是O(N^2)
	使用DP思路，从左到右，从右到左，记录最值，最后每个slot取两个值的较小值。

	更进一步，2 pointers。左右各一个。
	如果左边的height低于右边的height，相当于这个点的水量一定取决于left_max。
	同理，如果右边的height低于左边，这个点水量一定取决于right_max。


43. Multiply Strings
	和两个list相乘没啥区别。注意一下连续进位。（有办法可以不处理）

44. Wildcard Matching
	和Facebook的正则匹配万分类似。
	DP即可。wildcard要么不要，要么白嫖一位。

	补充！DP太慢了！！！
	这个题目有一个核心关键点：那就是如果出现了多个星号，我们只用记录最后一个星号的信息，因为前面的部分都是匹配成功的。

	所以可以用 【双指针 + 回溯】 做。

	如果出现了星号，就记录双指针的位置，下次匹配不成功就回溯，记得更新source指针 (increment by 1)

45. Jump Game II
	最少步数。 bfs思路。类似sliding window。

	⭐：从左往右找第一个能到终点的点，更新终点，直到终点为0。类似反向bfs思路。

46. Permutations
	典型的backtracking题目。交换后recursion，之后交换回来。

	另一种做法：反向一步一步生成。ans和new ans交换。

47. Permutation II
	我的思路：数一下每个数有多少个，然后backtracking做。

	另一种做法：反向生成。如何避免重复是关键！
	如果在插入位置的元素和被插入元素一样，则break。

49. Group Anagrams
	就是计算哈希值嘛。可以统计char的频率

50. Pow(x, n)
	二分法思路
	2^7 = 2 * 4^3 = 2 * 4 * 8 ^ 1
	不同语言可能需要handle int_min。

51. N-Queens
	第二道backtracking吧？
	不知道queen的移动方式真的是太尴尬了。hhhhh

52. N-Queens II
	和上面一道题是一样的。
	可以用bitmap来做，因为不用保存结果。

53. Maximum Subarray
	Kadane's algorithm.

	额外考虑一下全负数的情况。
	只需要把cur = max(0, cur + n)改成cur = max(0, cur) + n就好了。

55. Jump Game
	DP例题。一开始的想法是从右往左记录每个点是否能到终点。

	速度过慢。观察发现其实只要能够到最左边的good slot，就可以了。

	最后优化为O(N)。

56. Merge Intervals
	有很多写法。核心就是排序了。
	我觉得比较简洁的写法是，修改result的末尾是一个好思路。
	intervals.sort(key=lambda x: x.start)
	result = []
	for i in intervals:
		if not result or result[-1].end < i.start:
			result.append(i)
		elif result[-1].end < i.end:
			result[-1].end = i.end
	return result
	当然了，用一个pre来做也挺好的。

57. Insert Interval
	嗯？这道题为啥是Hard？

	模拟就可以了呀，O(n)。

59. Spiral Matrix II
	必须学这个写法！！！ 太震撼了

	matrix = [[0] * n for _ in range(n)]
	i = j = 0
	di, dj = 0, 1
	for k in range(1, n * n + 1):
		matrix[i][j] = k
		# 因为是从外走到内，所以外围一定是不是0，所以可以直接取模！！！
		# 换方向也是牛逼！
		if matrix[(i + di) % n][(j + dj) % n]:
			di, dj = dj, -di
		i += di
		j += dj
	return matrix

60. Permutation Sequence
	因为只要找到特定的一个，所以不可能生成全部。

	O(N^2)就可以生成。因为remove(index)是O(N)。
	index = (k - 1) // mul
	ans += candidates.pop(index)
	k -= index * mul


61. Rotate List
	可以直接跑一遍统计长度，求出来前面要放多少个。
	把尾巴连接到头，再跑一遍找到新的尾巴，断开就可以了。

	也可以把整个链表翻转，从后外前找新尾巴，断开后再翻转回来。

64. Minimum Path Sum
	dijkstra用牛刀了。

	1D DP就可以了。 因为只能向下向右走。

65. Valid Number
	最最傻逼的题目！！！！
	没有之一。

67. Add Binary
	实现Full adder。没啥意思。

68. Text Justification
	emmmm。。就是滑动窗口做嘛。。
	比较难写就是了。

69. Sqrt(x) Integer.
	这个题目大有文章可做。需要详细学习。
	等差级数公式：
		1 + 3 + 5 + ... + (2n - 1) = n ^ 2
		所以简单的for loop就可以做。效率不行。

	二分法：
		x^2 <= n and (x+1)^2 > n, get n。

	长除法：
		https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9#.E7.89.9B.E9.A0.93.E6.B3.95
		太牛了。

	牛顿迭代法：
		理解：利用斜率，选择起始点，不断逼近。
		需要二阶可导，起始点选择有影响。
		https://www.zhihu.com/question/20690553

		选择起始点 X_n，切线方程为 y - f(X_n) = f'(X_n) * (x - X_n)
		下一个迭代点： 设y = 0，解方程 f'(X_n) * (x - X_n) + f(X_n) = 0
		⭐：X_n+1 = X_n - f(X_n) / f'(X_n)

		运用到这道题目里，相当于求解 x^2 - n = 0。
		这个函数二阶全程可导。 -> f'(X_n) = 2 * X_n

		X_n+1 = X_n - f(X_n) / f'(X_n)
		      = X_n - (X_n ^ 2 - n) / (X_n * 2)
		      = 0.5 * (X_n + n / X_n)

		设置起始点X_n = n，这样我们迭代时一直在根点的右侧。（因为n > 0）
		当 X_n ^ 2 <= n停止。（这里也很神奇）

	位运算： 还需要研究。
		32位的整数，开方后最大为16位。我们只需要确定这16个bit是0还是1。
		MSB是sign bit所以不管。

		unsigned bitwise_verification(unsigned long x){
			unsigned long temp = 0;
			unsigned v_bit = 15;
			unsigned n = 0;
			unsigned b = 0x8000;

			if (x <= 1) return x;

			do {
				temp = ((n << 1) + b) << (v_bit--);
				if (x >= temp) {
					n += b;
					x -= temp;
				}
			} while (b >>= 1);

			return n; 
		}

	快速方法，不适用于大数: 0x5f3759df    0x5F375A86
		float FastSqrt(float x) {
			float n = x;
			int i = *(int*)&x;
			i = 0x1fbd1df5 + (i >> 1); // (1 - p)L(B - y) + p * x
			x = *(float*)&i;
			x = (x + n / x) * 0.5;	// 收敛一次
			return x;
		}
		e = E - B    m = M / L
		(1 + m) * (2 ^ e)     M + E * L

71. Simplify Path
	傻逼题目。
	扫描过去就是if编程。
	edge case是 "..filename" 和 "..."。
	在结尾加一个'/'比较方便。

72. Edit Distance
	非常有学习价值的一道题目！edit distance需要详细学习！
	https://web.stanford.edu/class/cs124/lec/med.pdf

	思路是DP。
	DP[i][j]描述word1[0: i + 1]到word2[0 : j + 1]的edit distance。

	转移方程是:
	DP[i][j] = min (
					DP[i - 1][j] + cost(deletion),
					DP[i][j - 1] + cost(insertion),
					DP[i - 1][j - 1] + cost(replace) if word1[i] != word2[j]
					)

73. Set Matrix Zeroes
	有一个很聪明的解法。
	我们利用第一行和第一列表示当前行列是否需要被清空
	因为要用第一列表示当前行是否被清空，所以我们需要特殊处理

74. Search a 2D Matrix
	就是二分法，把一维的index转成二维的就好了。

75. Sort Colors
	自己的想法是维护三个指针，代表012的对应位置。
	不过这样就不是O(N)了。

	维护两个就够了。只要保证0都在左边，2都在右边。1自己就对了。

	还有一个方法也挺有意思的，维护三个指针
	zero = one = two = -1
	for i in range(len(nums)):
		if nums[i] == 0:
			zero, one, two = zero + 1, one + 1, two + 1
			nums[two] = 2
			nums[one] = 1
			nums[zero] = 0
		elif nums[i] == 1:
			one, two = one + 1, two + 1
			nums[two] = 2
			nums[one] = 1
		else:
			two += 1
			nums[two] = 2

76. Minimum Window Substring
	滑动窗口标准题目。
	missing记录剩余需要的char个数，needed记录每个需要char的个数。

77. Combinations
	backtracking哈哈哈哈哈哈！

80. Remove Duplicates from Sorted Array II
	和LC.26一样的做法。
	用left和count两个变量就可以解决。

81. Search in Rotated Sorted Array II
	LC. 33的follow up。
	数组中可能有重复值，这样带来的结果就是最坏情况是O(n)。

	不同于LC.33直接求mid，我们可以先判断lo和hi是否为一个值。
	如果是的话，就increment lo，保证我们可以拿到高低两个区间。

82. Remove Duplicates from Sorted List II
	不能修改值的话，就加一个dummy在前面。

	和下面一道题一样的while loop，不过因为只保存独有的值，所以需要修改一些。

	值得记录！

	while cur:
		if cur.next and cur.next.val == cur.val:
			while cur and cur.next and cur.val == cur.next.val:
				cur = cur.next
			pre.next = cur.next #cur此时指向重复值的最后一个
		else:
			pre = pre.next #核心！
		cur = cur.next
	return dummy.next

83. Remove Duplicates from Sorted List
	做呗。
	如果不能改变值的话！
	加一个dummy在最前面，扫描到每个重复的最后，连接。

84. Largest Rectangle in Histogram
	我的做法是左右用单调栈各扫描一遍
	思路是每个可能的长方形一定是这个高度乘上左右连续大于等于它的长度。
	不过因为用了两次for loop，挺慢的

	看solution发现stack方法可以优化到一次！
	和我思路差不多，不过因为单调栈如果发现了一个比栈顶小的
	那么其实当前栈顶元素的左右长度其实都被确定了。
	不需要算一次左边，算一次右边。

85. Maximal Rectangle
	想太复杂了。。。
	可以直接转化成上面一道题的解法。。

	还有一个解法，之后再学吧。。

86. Partition List
	正常做，建立两个临时node优化代码。最后一定要把尾巴设置为None。

87. Scramble String
	我真的没有想到。。居然就是和对称树差不多的做法！
	小优化：如果长度小于4，必定可以，试试就可以

89. Gray Code
	我的思路是模拟，O(2^n * n)，因为要使用一个set

	还有一个厉害的思路是观察出来的。
	考虑一下n = 3
	(000, 001, 011, 010), (110, 111, 101, 100)
	每一轮都是前面剩下的镜像+前置位1


90. Subsets II
	这个要考虑重复值，可以用一个count_dict来做。

	也可以一开始sort一下，然后遍历的时候判断一下起始生成位置。（依据是否和前面元素相同）

91. Decode Ways
	backtracking会超时。
	其实是典型的dp问题，脑子不好，唉。
	可以进一步优化为二变量。

92. Reverse Linked List II
	recursion的比较好写。递归到m=1的情况再处理。

	iterative的就比较难写一点，加一个dummy在前面，然后记录范围的左右。

93. Restore IP Addresses
	啊，就是一道backtracking加上memo。

	写的真的烦！

	二刷了仍然很烦！

95. Unique Binary Search Trees II
	这道题挺恶心的，不过代码部分感觉有意思。

	我的傻逼办法是升序插入顺序，然后再按照顺序插入来生成。

	不过仔细优化下，可以直接用一个生成方法递归就好了。

	这个方法返回当前树的root，然后我们合并就好了。

	非常类似merge sort。是一道锻炼代码实现的好题目。

96. Unique Binary Search Trees
	一道典型的DP或者memorization题目。
	dp[i] = sum(dp[j] * dp[i - j - 1], 0 <= j < i)

97. Interleaving String
	backtracking with memorization就可以了。

	还想省空间就DP吧，二维可以优化为一维。
	DP[i][j]代表 interleave(s1.substring(0, i), s2.substring(0, j), s3.substring(0, i + j - 1))
	转移方程的话 同行就看左边的，第一列看上面的，剩下的看左边或者上面。
	DP[i][j] = (DP[i - 1][j] and s1[i] == s3[i + j + 1]) or (DP[i][j - 1] and s2[j] == s3[i + j + 1])

99. Recover Binary Search Tree
	是一道有意思的题目。
	利用的核心知识点其实是BST的中序遍历的输出，是从小到大的。

	在这个输出里，会出现一个到两个下降，找到就好了。

	空间可以用morris优化到O(1)。

100. Same Tree
	开开心心hhh

101. Symmetric Tree
	不记得题号了，有一道题就是这个里面的helper方法变种。
	
102. Binary Tree Level Order Traversal
	queue和new_queue交换就好了。
	BFS。

103. Binary Tree Zigzag Level Order Traversal
	BFS，reverse在0和1摇摆就行了。

104. Maximum Depth of Binary Tree
	开开心心hhh

105. Construct Binary Tree from Preorder and Inorder Traversal
	复习一下。
	基础写法就没写了。

	def helper(base, start, end):
		if start > end:
			return None

		root = TreeNode(preorder[start])

		index = inorder[preorder[start]]
		root.left = helper(base, start + 1, start + (index - base))
		root.right = helper(index + 1, start + (index - base) + 1, end)

		return root

106. Construct Binary Tree from Inorder and Postorder Traversal
	和中序 + 前序一样的。

	基础做法就是每次index，O(nlog(n))。

	优化index，可以到O(n)。
	我的做法是转index_dict，然后传入一个base，和post的start和end。

107. Binary Tree Level Order Traversal II
	emmmm。 和LC 103的区别是啥。。
	不过可以记一下dfs的写法。

108. Convert Sorted Array to Binary Search Tree
	LC爸爸对我真好hhhh
	找中点recursion就行了。

109. Convert Sorted List to Binary Search Tree
	转化成上面的就可以hhh
	或者实现middle，不过每次还要断开左右，比较繁琐。

110. Balanced Binary Tree
	做到easy树，就是笑嘻嘻。

111. Minimum Depth of Binary Tree
	BFS吧，DFS也差不多。

112. Path Sum
	path的定义需要注意下。和上面的Lc 111一样，path有点坑。

	模板就可以了。

113. Path Sum II
	和上面一样的，不过返回值需要是当前节点的所有路径。
	记得最后反转回来。

	当然也可以不反转回来做。维护一个processing，用类似backtracking的方法做。

114. Flatten Binary Tree to Linked List
	这道题有点意思哦。

	可以改一改iterative preorder。
	stack里面放right，就不放自己了。

115. Distinct Subsequences
	可以用DP，当然也可以用memorization。

	加一个last_index_dict，可以prunning很多backtracking步骤。

	DP也能做呀。【这不是废话吗
	dp[i][j] += dp[i - 1][j]; 
	dp[i][j] += dp[i - 1][j - 1] if s[i - 1] == t[j - 1]
	可以优化到 一维

116. Populating Next Right Pointers in Each Node
	BFS不行，因为要space O(1)！

	要space O(1)就一定要利用complete binary tree的性质。
    每一层都是饱和的是解题的关键。【其实不是，只是简单了点】

117. Populating Next Right Pointers in Each Node II
	和上面一道题有区别的地方，就是不是饱和的。
	也就是说，得加一个找到下一层最左的部分。
	上面一道题直接就是cur.left，这次我们要自己找。
	使用pre来建立next连接会方便很多。

118. Pascal's Triangle
	哈哈哈哈哈。

119. Pascal's Triangle II
	要么直接生成，要么就迭代一下。

120. Triangle
	从下向上每次俩俩选择min。
	最后返回array[0]

121. Best Time to Buy and Sell Stock
	和那道best sightview pair挺像的。
	记录扫描到的最小值，然后和当前值进行运算，比较，更新。

122. Best Time to Buy and Sell Stock II
	每有一个上升的pair，买！卖！

123. Best Time to Buy and Sell Stock III
	神仙题目。真的。

	一步一步优化到O(N), O(1)。

	最基础的思路是DP。

124. Binary Tree Maximum Path Sum
	还是可以用LEE的模板。

	左右子树的结果如果小于0，就不要了，直接设为0。

125. Valid Palindrome
	关键点只有一个。
	python有 string.isalnum() 这个神奇的方法。

126. Word Ladder II
	和下面一道题挺像的。
	不过要求出来所有路径。
	改一改bfs就好了。用dict来存到当前word的所有最短路径。

127. Word Ladder
	【图】。
	使用bfs找最短路径。关键在于如何构建图。
	每次transform只有一个letter可以变，所以可以建立一个中间的dictionary。
	比如 hot: *ot, h*t, ho*。 （这个做法还慢些，很神奇！）

	也可以直接枚举小写字母。

	优化：使用bidirectional BFS优化空间开销。

128. Longest Consecutive Sequence
	sequence不要求连续，不要求顺序。
	最简单肯定是sort后找。

	对于这道题，用一个set来优化查找时间就好。

129. Sum Root to Leaf Numbers
	preorder或者dfs一样的。

130. Surrounded Regions
	我是真的讨厌写matrix的遍历！

131. Palindrome Partitioning
	这道backtracking。真的写得我难受！

	要想清楚如何避免重复：
		必须要从start到i是回文才backtracking。

	上面这个的复杂度，应该是O(N*2^N)。

	我们来用一下马拉车算法。
	我们用马拉车算法生成P数组，然后我们把P数组转成(start_index, max_length)构成的数组。
	之后再用转化出来的数组，生成每一个下标index，可以和哪些right_index构成回文的数组 [set() for _ in range(len(s))]。
	
	之后再用上面的backtracking就可以了。这个样子的复杂度是O(2^N)，因为我们没有在回溯过程中找palindrome。
	预处理的复杂度是O(N^2)。

	不过这道题的testcase都很小，貌似 N <= 17，所以两个也没有啥区别。

132. Palindrome Partitioning II
	直接用 LC.131 backtracking的方法也能过，可惜是900ms。

	因为只需要求min_cut，所以其实不需要backtracking来遍历所有情况。
	考虑一下DP，DP[i]代表s[:i]满足条件的min_cut，那么DP[i] = min(DP[j] + 1 for j in range(0, i))，相当于分成两个部分计算。

	这要考虑的话，时间复杂度是O(N^2)，使用从中心扩展的方法就可以了。

	当然了，我们也可以使用马拉车来进一步优化，做法和 LC.131 的笔记都是一样的。
	但是我们不需要最后的backtracking，更换为DP的做法。
	for i, rights in enumerate(arr):
		for right in rights:
			DP[right] = min(DP[right], 1 + DP[i])

	我们这个方法，最差是O(N^2)，但是如果testcase不是一个字符从头到尾的话，其实inner loop是没有N的，平均时间应该是O(N^(3/2))。

	看了discussion，还可以再优化一下。
	反正也是O(N^2)嘛，所以可以试一下能否只砍一刀就完成任务。

133. Clone Graph
	建一个mapping_dict。
	不需要使用visited，只把不在dict里面的node加进queue就好了。

134. Gas Station
	为什么。。为什么我的方法这么慢。。

	官方答案：
		核心要点：整体油量 >= 整体消耗的话，一定有solution。

		这个就不证明了，太牛了。
		我还他妈在那儿模拟呢
		不过我模拟也是O(n)啊，为什么呢。

135. Candy
	可以左右扫描一遍，然后用类似trapping water的做法做。不过是取max.

137. Single Number II
	这道题，真的，我想不出来。

	因为XOR可以统计出哪些bit出现了奇数次，所以我们要区分出现1次和3次的。
	seen_once = ~seen_twice & (seen_once ^ num)
	seen_twice = ~seen_once & (seen_twice ^ num)


139. Word Break
	直接用DP。思路和cumulative sum非常相似。
	DP[i] = True if DP[j] == True and s[j:i] in wordDict

	还可以用BFS. (和BFS相比，这个用DFS更快)

140. Word Break II
	用BFS或者DFS会超时。因为重复访问的东西太多了。

	所以加一个memorization就好了。

	有一个讨巧的优化是把所有words按照首字母分类保存。
	这样判断的时候先判断首字母是否合格，会快一些。

142. Linked List Cycle II
	龟兔做法。关键是找entry point。

	设 起点 到 环开始点 为 L1； 环开始点 到 相遇点 为 L2。
	   环 的 长度 为 C

	则 乌龟一共移动了 L1 + L2 + n1 * C
	   兔子一共移动了 L1 + L2 + n2 * C

	因为 兔子的步数是乌龟的两倍，所以：
		2 * (L1 + L2 + n1 * C) = L1 + L2 + n2 * C
		L1 + L2 = (n2 - n1) * C
		L1 = (n3 - 1) * C + (C - L2)

	C - L2就是乌龟还需要走多久可以到 环开始点。

143. Reorder List
	可以存在array里hhhhh

	O(1)的做法是：找到中点，翻转后半部分，然后连接。

144. Binary Tree Preorder Traversal
	有什么好说的呢？三种都写写。

145. Binary Tree Postorder Traversal
	后序的iterative和Morris都是难点。时常复习是必要的。

147. Insertion Sort List
	那些存在array里排序后重建的，人才。

	建一个dummy = ListNode(-float('inf'))方便很多。
	加一个last提高下速度。

148. Sort List
	linked list sort。
	merge sort实现一下 ok。

149. Max Points on a Line
	有难度的一道题目。需要仔细想想。
	尤其是如何表示一条直线，计算斜率的话，double可能精度不够导致错误。
	使用GCD是个方法。
	def GCD(a, b):
		if a == 0: return b
		return (b % a, a)

150. Evaluate Reverse Polish Notation
	就一个stack。我写了。我过了。还要我怎么样。

151. Reverse Words in a String
	用python做是一道弱智题目。
	关键还是看看inplace + space O(1)的思路。
	整体reverse后从左到右扫描，加一个valid pointer。
	扫描到一个word后再次reverse这个word。
	记得最后erase最后的部分。

153. Find Minimum in Rotated Sorted Array
	直接的是O(n)。

	巧妙一点的可以用二分法！！！

154. Find Minimum in Rotated Sorted Array II
	一开始过滤下左边和结尾重复的元素。

156. Binary Tree Upside Down
	个人感觉就是找规律。想了挺久的hhh

	iterative的写法挺有意思。
	temp = prev = curr = next = None
	curr = root
	while curr:
		next = curr.left
		curr.left = temp
		temp = curr.right
		curr.right = prev

		prev = curr
		curr = next
	return prev

157. Read N Characters Given Read4
	嗯？？

158. Read N Characters Given Read4 II - Call multiple times
	在上一道题的基础上，加一个buffer就好了。

159. Longest Substring with At Most Two Distinct Characters
	和LC 904一模一样。
	写法复习一下，挺简洁的。

	a = b = ""
	ans = cur = b_count = 0
	for c in s:
		cur = cur + 1 if c in (a, b) else b_count + 1
		b_count = b_count + 1 if c == b else 1
		if c != b:
			a, b = b, c
		ans = max(ans, cur)

161. One Edit Distance
	直接用edit distance公式会超时。

	那就分情况做呗！

162. Find Peak Element
	这道题！！！
	这就是魔法！！
	这居然可以用binary search？？？？？

	为什么可以用二分法？？
	因为：
	1.有一个假设，没有连续相同的值
	2.并且假设了两边都是-inf
	所以用二分法维护第二个性质，可以得到答案。

163. Missing Ranges
	很迷的一道题，不知道这个英文描述是谁写的。
	if解题就好了。如果处理遍历完后lower仍然小于upper？
	把upper + 1放在末尾。

164. Maximum Gap
	我只能想到sort了。

	第二种方法就是Radix 基数排序了。

	就是拿着每一位排序，从优先度低的一测还是排。
	值得一提的是，Radix排序内的排序算法需要是【稳定】的。
	这样做的话，因为数最大也就是int32，所以是O(10N)。
	不过因为除法的开销其实并不是很低，所以也没有比python的timsort快。

	另一种做法就是Bucket Sort了。
	为了得到答案，我们只需要考虑桶内的最小距离和桶间的最大距离。

	但是，桶内最小距离计算起来比较麻烦，所以有没有可能我们只需要考虑桶间距离呢？
	问题的关键其实是 需要多少个桶!

	根据鸽子洞原则，我们只需要用M个洞装N个鸽子，M>N。那么一定有空洞。
	在这道题里面，我们只要保证左右两边的桶都有东西，空桶出现在中间，那我们就只需要考虑桶间距离了。
	因为有空桶嘛，所以gap最小也得是一个桶的大小，这样我们就可以忽略桶间距离。

165. Compare Version Numbers
	split + map(int)

166. Fraction to Recurring Decimal
	这题完全就是自己大意了。
	很多edge case都没有考虑过。

	需要考虑负数的情况 --> 保证余数是正的。

	如何判断循环？余数出现过多次就有循环了。

	但是值得注意的是，需要保存余数对应的index，因为只要那部分到尾巴是循环部分。

167. Two Sum II - Input array is sorted
	没有排序的题目，用了O(N)的dictionary来完成。
	既然排序了，肯定可以优化下。
	不用dictionnary，用two pointer左右就可以了。

168. Excel Sheet Column Title
	进制问题老是想不明白。
	这个问题没有0，所以(num - 1) % 26和(num - 1) // 26 (就是每次loop先减少1)

169. Majority Element
	有挺多做法的。

	count_dict; sort后取中间。

	记一下摩尔投票。

	还可以用bit运算做。就是每一个bit出现次数超过一半。

171. Excel Sheet Column Number
	进制进制！
	ans = ans * 26 + 1
	ans += ord(c) - ord('A')

172. Factorial Trailing Zeroes
	就是找这里面一共有多少个5。
	我们不需要找2，因为2的个数一定是充足的。
	注意下，25有两个5，125有三个5。

173. Binary Search Tree Iterator
	把iterative in order tranversal 拆开就好了。
	stack里面最多存O(h)个元素，满足条件。

174. Dungeon Game
	DP做。没有特别想明白。
	DP[i][j]描述的是 开局最少需要多少血 可以到dungeon[i][j]
	dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])

179. Largest Number
	学习了python3的functools.cmp_to_key。

	自定义一下 comparator。
	a + b 和 b + a这个写法好。

186. Reverse Words in a String II
	要么直接join起来然后用一样的方法做。

	要么就自己写一个inplace reverse的方法。
	思路是全局reverse再单个单词reverse。

187. Repeated DNA Sequences
	rolling hash的绝佳使用场景！

188. Best Time to Buy and Sell Stock IV
	就是优化到一维DP。
	要考虑特殊情况！ K >= len(prices) // 2的话，相当于就是 LC.122

190. Reverse Bits
	没啥好说的。CSAPP难度。跪了。
	n = (n >> 16) | (n << 16)
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)

191. Number of 1 Bits
	有好多的办法呢！
	str(n).count('1')是最简单的办法了。

	如果用bit operation呢？
	有一个trick是 num & (-num) 可以拿到 rightmost_bit。
	当然了，如果只是要移除 rightmost_bit，可以直接用 num = num & (num - 1)

	那如果连loop也不能用呢？
	hamming weight就可以用了。

	假设只是一个32-bit的数字。那么可以这么做：
	num = (num & 0x55555555) + ((num & 0xaaaaaaaa) >> 1)
	num = (num & 0x33333333) + ((num & 0xcccccccc) >> 2)
	num = (num & 0x0f0f0f0f) + ((num & 0xf0f0f0f0) >> 4)
	num = (num & 0x00ff00ff) + ((num & 0xff00ff00) >> 8)
	num = (num & 0x0000ffff) + ((num & 0xffff0000) >> 16)

198. House Robber
	标准的简单DP题目吧。
	抢或者不抢。

199. Binary Tree Right Side View
	BFS或者DFS都可。
	DFS检查一下level高度再添加。

201. Bitwise AND of Numbers Range
	牛逼题目啊。bit操作真厉害。

	我的思路是验证每一个bit是不是在允许范围内。

	然而。。
	while n > m:
		n &= n - 1 #移除最右边的bit
	return n #或者 m & n

202. Happy Number
	可以用set嘛，也可以用fast slow。

204. Count Primes
	dp思路？一个array，把每个数在范围内所有倍数都排除。

205. Isomorphic Strings
	简单题目嘛，空间不值钱！

207. Course Schedule
	可以用alien dictionary的思路。当一节课没有前置要求了，就把它上了。
	然后更新它所有的后置课程的前置要求。

	dfs的写法可以学习一下。
	# 造图
	graph = [[] for _ in range(numCourses)]
	visit = [0 for _ in range(numCourses)]
	for course, pre in prerequisites:
		graph[course].append(pre)

	def dfs(i):
		if visit[i] == -1:
			return False
		if visit[i] == 1:
			return True
		#这门课标记为想学但还没学成
		visit[i] = -1
		for j in graph[i]:
			if not dfs(j):
				return False
		#他的前置课程都学了，可以学习了
		visit[i] = 1
		return True
	#学习每一节课
	for i in range(numCourses):
		if not dfs(i):
			return False
	return True

208. Implement Trie (Prefix Tree)
	没啥好说的。

209. Minimum Size Subarray Sum
	滑动窗口题目。
	谢谢向老师。

	也可以对长度做 二分法。 O(Nlog(N))

211. Add and Search Word - Data structure design
	我就直接用trie做了吧。

	看其他人很多都是用length_dict来做的。也不是不行，就是。
	还是testcase没有太大的。

	记一下这个做法也不错。

213. House Robber II
	LC 198的follow up。
	我一开始的思路是加一些判断。

	不过最后看答案，发现只要排除第一个跑一次，排除最后一次跑一次就好了。

214. Shortest Palindrome
	palindrome。
	我的死穴。

	最简单的写法都写不出来。
	r = s[::-1]
	for i in range(len(s)):
		if s[:len(s) - i] == r[i:]:
			return r[:i] + s
	return ""

	到这里我们就发现，其实在找两个string的最长公共前缀后缀。
	这就是KMP的next数组含义。
	所以我们可以把两个string 拼接起来，跑kmp。

216. Combination Sum III
	backtracking就好了。

217. Contains Duplicate
	哈哈哈哈哈

218. The Skyline Problem
	最简单的思路就是维护一个array嘛，记录每个位置最高值。
	不过array过长会爆内存。

	思路二：使用divide and couquer，
	写一个类似merge two linked list的merge方法。

	思路三：使用priority queue！
	这也太牛逼了！！
	pq按照高度从大到小排，tie的话right从大到小。
	核心思路一：pop pq的时候，只要right < top right就可以删除。
	           因为 这部分全部被overshadow了。
	           pop完剩下的top height就是top right应该写的高度。
	核心思路二：right处理完，left呢。left直接添加进入answer。
	           height选取pq的top height。
	核心思路三：所有可能需要的点，要么是left要么是right。
	while i < lens or priority_queue:
            # 新建筑的left在范围内，继续添加进pq
            if not priority_queue or (i < lens and -priority_queue[0][1] >= buildings[i][0]):
                x = buildings[i][0]
                # 一次性把left一样的都添加进去
                while i < lens and buildings[i][0] == x:
                    heapq.heappush(priority_queue, (-buildings[i][2], -buildings[i][1]))
                    i += 1
            # left在范围外，把pq内的处理完再处理新的(group)
            else:
                x = -priority_queue[0][1]
                # overshaodowed parts
                while priority_queue and -priority_queue[0][1] <= x:
                    heapq.heappop(priority_queue)
            
            height = -priority_queue[0][0] if priority_queue else 0
            if not result or height != result[-1][1]:
                result.append([x, height])
        return result

219. Contains Duplicate II
	记录每个数字最近一次出现的下标。

220. Contains Duplicate III
	普通的O(NK)会超时。

	可以用bucket sort的思路来做。（就是这次阿里面试处理大文件的思路）
	判断 [num - t, num + t] 之间有没有符合要求的值。
	我们把 at + b (0 <= b < t) 放进编号为a的桶里。
	这样一个桶内的元素一定是在范围之内的。
	然后这个桶前后两个桶内的元素也有可能落在这个范围内，所以也要检查。


221. Maximal Square
	DP题目。

	最简化的版本没想到。

	dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

222. Count Complete Tree Nodes
	听说是Google今年比较多的题目。

	要充分考虑compelete binary tree的性质。
	上面D - 1层一定是满的，所以我们只需要确定最下层有多少个。
	确定长度，可以用二分法来做。

	如何确定这个位置有没有元素呢，可以用二分法模拟走下来。


	六六真的厉害。还给了另外一个解法。
	利用完全二叉树的性质，查找高度只需要log(N)。
	所以我们计算好最下层最多多少个叶子后，
	可以比较左右子树的高度。
	如果一样高的话，就去查右树，并且一定已经有self.number // 2个叶子了。
	一样的话就去查左树。

223. Rectangle Area
	这题目吧。算了，我直接背吧。真麻烦。

	area = (C - A) * (D - B) + (G - E) * (H - F)
	# Subtract the area of common rectangle
	width = min(D, H) - max(B, F)
	height = min(C, G) - max(A, E)
	if width > 0 and height > 0:
		return area - width * height

224. Basic Calculator
	好题目啊。
	我老是记不住好的写法。自己是递归实现的。

	在处理括号的时候，可以先把前面的符号和结果放到栈里，算完括号再来取。

225. Implement Stack using Queues
	挺有意思的。不可能两个都O(1)。

	要push O(1)的话，就pop的时候全部重新插入。

	要pop O(1)的话，就push的时候全部重新插入。

226. Invert Binary Tree
	标准模板。加一个temp。

227. Basic Calculator II
	计算器。可以不使用stack【我也是惊呆了！
	记录lastSign，初始设置为'+'。
	发现下一个Sign的时候，如果lastSign是'+'或者'-'
	说明前面的部分已经不会再变了，直接加入到sum里。tempSum更新。
	如果是'*'或'/'，不更新sum，只和tempSum互动。

	主要就是因为没有括号。所以可以这么优化。

	补充：
	当然用stack更好做。核心就是多读一个符号。

228. Summary Ranges
	滑动窗口。

229. Majority Element II
	摩尔投票的拓展。

	维护两个变量和两个计数器。

	最后需要再validate一遍。

230. Kth Smallest Element in a BST
	中序遍历就好了。

	follow up的话，考虑会经常删除添加。
	添加的话：加入值比当前值大，无更新。
			加入值比当前值小，加入后找predecessor。
	删除的话：删除值比当前值大，无更新。
			删除值比当前值小，删除后找successor。

	如何找predecessor:
		如果有左子树，则predecessor为左子树一路向右的leaf node。
		如果没有左子树，则为从root到node的最后发生最后一次right turn的node。
		（如果有parent 指针，可以逆流而上。否则需要从root到下找）

	如何找successor:
		如果有右子树，则successor为右子树一路向左的leaf node。
		如果没有右子树，则为从root到node的最后发生最后一次left turn的node。
		（如果有parent 指针，可以逆流而上。否则需要从root到下找）

231. Power of Two
	基础思路就是慢慢除，O(log(n))。
	bit operation有意思。 使用trick x = x & (x - 1)可以抹除最右边的一个1。
	其他解法也挺有意思。

232. Implement Queue using Stacks
	维护两个stack。
	不过不需要每次插入都颠倒。

	可以在需要pop的时候再把stack1的东西都颠倒到stack2去。

233. Number of Digit One
	太震撼了。

	数每一位上1的个数。还能再狠一点吗。

	ans += left * incre
	if reminder > 1:
		ans += incre
	elif reminder == 1:
		ans += right + 1

	比如数 百位 上的'1'。45122，一定有45 * [1000]这么多个1.
	在1000里百位的1有100个 (100, 101, 102, ..., 199) 
	接着，因为当前百位上就是1，所以还要加上
	(100, 101, 102, ..., 122)一共23个。
	如果百位大于1呢？再加上100个。

235. Lowest Common Ancestor of a Binary Search Tree
	模板冲冲冲。

236. Lowest Common Ancestor of a Binary Tree
	和上面一道题不一样的是没有中序排序的性质了。
	所以得遍历。
	仔细思考一下LCA的性质，只有这个node左右可以返回true。

238. Product of Array Except Self
	左右错位累积乘，最后result[i] = left[i] * right[i]

	当然可以优化不用left和right，第一遍往result里直接加如累积乘
	第二遍result[i] *= temp就好了。

239. Sliding Window Maximum
	可以用deque或者dp做。
	dp的做法和trapping water很类似，不过需要额外分块。
	是一个值得记的做法。

240. Search a 2D Matrix II
	和那道传奇二分差不多的思路。沿着左下到右上找，O(n + m)。

	divide and conquer也挺厉害的。

241. Different Ways to Add Parentheses
	memorization或者DP都可以。

	核心思路是每一个operator都可以是最后处理的operator。

	所以拿到left和right的所有可能值，笛卡尔处理。

243. Shortest Word Distance
	记录两个下标，更新时尝试更新mins。

244. Shortest Word Distance II
	因为要多次处理嘛，所以每次扫描所有词太慢了。
	转存一个index_dict。

	问题就转化成了：找两个sorted array中pair的最小值。

	用two pointer做就好了。

245. Shortest Word Distance III
	就让多考虑一个重复情况。

	上面两种做法都可以。

249. Group Shifted Strings
	就是构造相同的key嘛。

	char转int，然后保证头是0就好了。

250. Count Univalue Subtrees
	标准模版，if写的有点多。

251. Flatten 2D Vector
	就是一个2D array。
	比较烦人的是[[],[1]]。
	所以更新i的时候要用loop。

252. Meeting Rooms
	排序后检查有没有overlapping

253. Meeting Rooms II
	神题。
	排序后维护一个min_heap。
	min_heap里面放的是每个房间的使用结束时间。
	如果下一个会议的开始时间小于heap顶的房间使用结束时间，就必须要多开一间房。
	反之，可以把这间房用给新的会议。

	还有一种做法！其实我们只需要看有几个start_event在end_event前面。
	我们把start_time和end_time分开排序。
	然后当前的start如果小于当前的end event，room + 1

254. Factor Combinations
	写这种题有时候就突然不晓得应该怎么写了。

	没理清楚思路。

	ans = []
	def backtracking(processing, number, start):
		for i in range(start, int(number ** 0.5) + 1):
			if number % i == 0:
				temp = number // i
				ans.append(processing + [i, temp])
				backtracking(processing + [i], number // i, i)

	backtracking([], n, 2)

255. Verify Preorder Sequence in Binary Search Tree
	我居然自己想出来了欸。

	一开始想的是查范围，后面发现不用查右边的办法，只用查左边界。

	用单调栈。

	为了实现O(1)空间，只能动刀preorder数组了，因为遍历一定比stack远。

256. Paint House
	现在DP都已经是EASY了啊。

257. Binary Tree Paths
	标准模版嘛。

258. Add Digits
	模9。

	特殊处理一下0和9.

	用 1 + (num - 1) % 9

259. 3Sum Smaller
	就是3 Sum的变形。
	核心点还是sort + two pointer。
	不过有很多可以优化的地方，最大两个值小于target，就直接算C(x,2)
	nums[l] + nums[r] < target,ans += r - l

260. Single Number III
	这个也是神仙题目。我bitwise真的垃圾。

	xor所有结果，会得到x和y独有的bit置位。
	然后用 mask & (-mask) 求得独有的一位。

	然后xor这一位被置位的所有数，得到其中一个结果。

261. Graph Valid Tree
	复习一下树的定义吧。 
	1. 没有isolated node。
	2. 没有cycle。

263. Ugly Number
	有意思哈。数学基础要打好。
	一直除235最后看是不是1。

264. Ugly Number II
	是一道DP思路的题。
	不断2，3，5乘起来。怎么优化这个过程呢。
	用三个pointer表示当前2，3，5使用了几个。
	然后mins = min(res[t2] * 2, res[t3] * 3, res[t5] * 5)

265. Paint House II
	LC 256的follow up。把三个颜色扩充到K个颜色。

	按照256的DP思路
		DP[i][j]表示house[i]用color[j]上色的最少开销
		DP[i][j] = min(DP[i - 1][k] for k in range(k) if k != j) + costs[i][j]
		这个样子的话，更新一个DP[i]需要K^2，整体是O(nk^2)

	仔细理一理，我们可以发现更新一个DP[i]，其实只需要DP[i - 1]中的两个值。
	min和second_min，需要second_min是因为不能相邻涂一样的颜色。比如[[5,1,3],[10,2,6]]

	这个样子的话，我们只需要遍历一次color，将当前的cost加上之前两个值的其中一个，然后继续维护min和sec_min。

266. Palindrome Permutation
	只能有一个奇数次的字符。

267. Palindrome Permutation II
	还是先统计频率。 找一下有没有唯一的奇数次字符。

	然后用带重复数字版本的permutation生成一半，加上中间，加上颠倒的另一半。

268. Missing Number
	很有意思的一道easy题目。不需要使用小李的方法其实。
	等差数列求和再一一减去就可以。
	⭐：或者使用XOR，因为只有一个index和value不会对应。

269. Alien Dictionary
	找出字母的顺序。
	记录每个字母比它大的子母们和比它小的子母们，两个hashmap。

	什么时候加入result string？
		当比它大的字母们为空的时候加入。
		加入后，在所有比它小的字母那边更新。

	这就是 拓扑排序！

270. Closest Binary Search Tree Value
	就正常找呗，每一次算一下min diff更新。

271. Encode and Decode Strings
	用trunked encoding感觉挺不错的。

	用 一个byte + 四个bytes 记录当前trunk是否为前面的连续，和当前的size。

272. Closest Binary Search Tree Value II
	我只想出来了O(N)的方法。
	inorder拿到之后，two pointer左右缩小范围。

273. Integer to English Words
	呵。我服了。这道题。

	我能写的方法就是写一个helper function。用来转1000以下的数字。
	这个function遇到0啥也不返回，其他的保证最后没有空格。

	然后在外面套一个循环，每次取三位。

274. H-Index
	我他妈真的。想了好久！

	记录一个O(N)的做法。基于 counting sort。
	核心就是 min(num[i], len(num))

275. H-Index II
	我他妈真的。又想了好久！

	想不清楚。全靠蒙。
	L = len(citations)
	lo, hi = 0, L - 1
	
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		if citations[mid] == L - mid:
			return L - mid
		elif citations[mid] < L - mid:
			lo = mid + 1
		else:
			hi = mid - 1
	return L - lo

276. Paint Fence
	这尼玛是EASY？

	需要使用DP来做。

	DP[i].same = DP[i - 1].diff
	DP[i].diff = (DP[i - 1].diff + DP[i - 1].same) * (k - 1)

	思路就是粉刷一个篱笆时，他可以和前面颜色一样或者不一样。
	一样的话，那么他就只有一种选择，所以就是DP[i - 1].diff。
	不一样的话，那么他就有K - 1种选择。

	难！

277. Find the Celebrity
	脑筋急转弯题目。没啥意思。
	遍历一遍，A认识B：排除A。最后剩下一个选手。

	再一一检查就好了。
	可以优化的地方：
		1. 第一遍遍历的时候得到X，说明X后面的pair他都不认识。
		   所以查X不认识所有人时，只需要前半部分。

279. Perfect Squares
	可以直接转化成coin的做法。进一步转化成【完全】背包装满的所需最少数量。
	Python会TLE。。一个做法是。。用static记住之前算过的。

	但是用BFS不会TLE！记住！

280. Wiggle Sort
	构造不严格的锯齿形数组。

	我一开始想的是sort之后选择。
	后面想想，要求的是不严格的，直接两两交换就可以了。

281. Zigzag Iterator
	貌似用DEQUE做是最轻松的。代码也最好懂。

	followup也可以用deque。也可以用double circular linkedlist。

284. Peeking Iterator
	就是加一个变量。

285. Inorder Successor in BST
	分两个情况讨论。
	如果有右节点，那么就是右节点的最左。
	如果没有，那么就是从root到这个节点的最后一次往左走。

286. Walls and Gates
	BFS。我老是忘记可以先把所有0加进去再跑一次bfs。

287. Find the Duplicate Number
	延申题目。用龟兔做法。 LC.142

288. Unique Word Abbreviation
	这道题downvote挺多的，但是个人觉得，这才是面试的样子。

	首先要搞清楚input是怎么回事：
		1. dictionary里面可能有重复值。
		2. isUnique可能会测dict里面没有的string。
		3. 考虑empty string。

	这些想清楚了就简单了。 Hashtable + set

289. Game of Life
	这是什么傻逼medium题目。
	follow up里面，针对extremely sparse matrix，转用live cell set比较快。

290. Word Pattern
	一个dict一个set就可以实现了。

291. Word Pattern II
	主体思路肯定是backtracking。
	用一个dict和一个set来维护bijection。
	可以实现一部分剪枝，比如
	if len(pattern) - start > len(s) - scan:
		return False

293. Flip Game
	要是面试都是这样的，就好了

294. Flip Game II
	可以直接用backtracking来做，next state如果是False，那当前就是True

	还可以用游戏论的知识。计算mex和SG来做。

295. Find Median from Data Stream
	还可以的一道题目。很多种解法。
	我的解法用two heap就行。

	使用BST解法：维护BST树，找suc和pre。

297. Serialize and Deserialize Binary Tree
	BFS或者DFS都可以。不过DFS(也就是preorder)因为没有层高信息，所以需要的'#'要多一些。
	不过胜在简洁。
	vals = iter(data.split())
	val = next(vals)
	这个写法要记录一下。

298. Binary Tree Longest Consecutive Sequence
	送分题目嗷！

299. Bulls and Cows
	挺有意思的，感觉题目描述还是不太清楚。
	可以two pass也可以one pass（one pass利用到了负数）。

300. Longest Increasing Subsequence
	一道非常经典的算法题目！
	一般的dp思路就是记录包括每个点的最长长度，下一个slot看情况是否加1。

	关键是O(nlogn)的算法。
	主要思路是记录每个长度最有潜质发展为LIS的sequence。
	如何记录这个？记录每个长度的尾巴值，这样子整个dp就是sorted的，可以用二分查找。
	发现新的最大值长度加一，要不就二分查找对应的位置替换。

	⭐：这个方法最后的dp不是LIS，但是长度是LIS的长度！

301. Remove Invalid Parentheses
	一个非常重要的信息：
		遍历一次string我们就可以知道最少删除多少个slot可以得到valid answer。
		如何实现：
			for c in s:
				if c == "(":
					left += 1
				elif c == ")":
					if left == 0:
						right += 1
					else:
						left -= 1
			left + right就是需要删除的个数。
		做一遍sanity check可以缩短时间。

303. Range Sum Query - Immutable
	只需要用【累计和】就好了。
	因为不改变嘛。

304. Range Sum Query 2D - Immutable
	用一个二维cumu存。

	DP[i][j]表示以[i,j]为右下角的矩形sum。

	求的话就是 整体 - 上面 - 左边 + 重复减掉的

307. Range Sum Query - Mutable
	BIT结构！刚好复习一下。

308. Range Sum Query 2D - Mutable
	二维 BIT结构！！！

	尝试写一下吧。

310. Minimum Height Trees
	暴力解法是O(N^2)，会超时。
	我的思路有一些复杂。
	我们先随便选择一个点作为root，求出所有点对应的height。
	然后我们再从这个点遍历一次，这个点走到neighbor，只需要考虑两个height
	一个是这个子树本身的height，和_from这个点的height。
	因为求_from这个点的height需要一些时间，但是远小于O(N)。
	所以整体接近线性时间。最坏情况是O(N^2)

	再换一个思路想，最多可能有几个点？
	妈的，最多只可能有两个点。
	想简单的，就是一条线，那么只有中间点是可以的。
	有了这个思路，我们完全可以从叶节点删起，删到最后就是中间点了。
	runtime是O(N)

312. Burst Balloons
	我觉得非常难的一道题目。
	完全想不到简单的办法。BF的话又超时。

	最优解DP的关键是选择的这个index是最后被burst的！
	然后转化为他左右两边的case。实现divide and conqure。
	简化写法可以在两边加上1，我们设定不能够选择边界。
	dp[l][r] = max(nums[l] * nums[i] * nums[r] + dp[l][i] + dp[i][r] for i in range(l+1, r))

314. Binary Tree Vertical Order Traversal
	吗的。给绕进去了。
	就是BFS加一个参数，用hashtable存一下最后排序就好了。

315. Count of Smaller Numbers After Self
	好题，难题。
	学习到了BIT这个数据结构。

	最基础的做法就是N^2了，直接遍历就可以了。
	这道题其实是算一个数组的inversion count，不过它没有把inversion count加到一起，而是单独储存在一个数组里。

	优化做法一：用加强版的mergeSort就可以实现这个目标
	在merge这个步骤的时候，我们记录一个right_count变量，表示当前已经有多少个右边的元素被放进了结果中。
	在左边元素被放进结果时，我们更新这个元素对应的inversion count: += right_count
	表示有right_count这么多个元素比左边这个元素要小。
	时间开销O(nlog(n))，空间O(n)
	记得使用index数组。

	还有第二种做法是用BIT，binary index tree。
	BIT的基础做法就是建立长度为max(nums) + 1的BIT数组
	然后反向遍历nums，get之后update
	不过这个不适用于数字太大的情况

	所以这里我们把nums转成相对大小一样，但是范围在[0, N-1] （如果没有重复值的话）。
	indexes = {v:i for i, v in enumerate(sorted(set(nums)))}

316. Remove Duplicate Letters
	基础的回溯TLE了。

	可以用单调栈的思路来做，额外考虑一下栈顶元素是否为最后一次出现。

317. Shortest Distance from All Buildings
	每个building来一次BFS，更新每个0的总和距离。最后取最小值。

	优化：第一次1找所有0，然后把找到的0都减少1。第二次1找所有-1。因为valid 0必须能访问到所有1。

	优化：min也不需要最后再整个搜索matrix。在最后一次处理1的时候，第一次拿到的值就是我们要的最小值。
		 所有每次bfs将min重新设置回INT_MAX，然后更新就好了。

319. Bulb Switcher
	数学题目嘛。
	仔细分析一下，最后亮没亮，只看一个数的因数个数。
	很明显，只有完全平方数的因数个数是奇数，所以只有完全平方数最后会亮。

321. Create Maximum Number
	难啊。。。
	我们可以：
	1. 在线性时间里，求出来一个arr里的长度为K的最大数字。
	2. 在平方时间里，融合两个最大数字。

	所以，我们可以将K = A + B，然后在两个数组里求两个最大数字，融合比较。


322. Coin Change
	一道经典的算法题目。
	算呗 dp[10] = min(dp[5], dp[7], dp[9]) + 1.

	不能！！用greedy从大到小选择。

	还有用DP就可以了。

	BFS更快！！！这是为什么呢？
	BFS的runtime是 (target // min_coin) * number of coins
	DP的runtime是 target * number of coins

324. Wiggle Sort II
	这道题我一直觉得挺难的。

	最简单的做法就是排序，然后把大的一半放在奇数位，小的一半放在偶数位。

	如何实现O(N)？
	最关键的是，我们不需要用排序，只需要找到中位数。
	可以用 【quick select】 线性时间找到中位数。
	剩下的就还是用大小来填就好了。

	注：这里还是有edge case需要仔细想的。因为我求的是下位中位数，所以小的一半，我们需要从右边开始填。

	如何实现O(1)？
	我们需要用flag那道题的思路，维护几个指针，跳着扫描。


325. Maximum Size Subarray Sum Equals k
	详细拓展看归类笔记！

	一个哈希表就好了。

326. Power of Three
	除法啥的就不说了。

	或者 log3(n) = log10(n) / log10(3)，然后判断是否结果是否为整数。

	三的幂数。说明质因数只有3。
	在int范围内，3^19 = 1162261467是最大的合法数。
	3^19 % 其他的三的幂数 == 0

328. Odd Even Linked List
	没啥意思。维护两个指针，even和odd。
	记得最后把even.next = NULL。

329. Longest Increasing Path in a Matrix
	一开始想的是DFS两边找，后面发现不太行。
	仔细想想，可以用memorization做。
	helper(i, j)描述以matrix[i][j]结尾最长的上升路径长度。
	helper(i, j) = 1 + max(valid neighbors)


331. Verify Preorder Serialization of a Binary Tree
	挺有意思的一道题。
	我一开始想的用栈，想复杂了。仔细想想，只需要维护一个变量记录当前可用的slot数量。

332. Reconstruct Itinerary
	我一开始想的是backtracking。最优解是DFS。其实差不多啦。

	为了实现lex order，所以建立ajacent list时排序。

	DFS的核心在于，反向建立答案。
	因为我们一定要遍历所有edge，所以如果提前碰到了dead end，这个dead end一定是顺序的末尾。
	就可以添加进去了。


334. Increasing Triplet Subsequence
	就是用LIS的最优O(nlog(n))的解法。
	不过因为只找长度是3的，可以不需要用二分法，自己比较就好了。

	最优算法核心是找每个长度最具潜力的candidate。

336. Palindrome Pairs
	唉。
	暴力会超时hhhh 因为时间是 O(N^2 * [maximum length of word])

	仔细分析，仔细分析。
	一个word 的 prefix 如果是palimdrome，那么只要对应的reversed suffix在list里，就可以配对。

	这么做就可以 O(N * [maximum length of word] ^ 2)

337. House Robber III
	LC 198强盗联动。
	这次换成了bianry tree还挺好想的。

	还是用LEE大神的模板就好了，不抢当前这个点的最大值是多少，抢了当前这个点的最大值是多少。

	其实这个是post order traversal。

338. Counting Bits
	Dp.
	dp[i] = dp[i >> 1] + (i % 2)

339. Nested List Weight Sum
	就是一个recursion呀。比较坑爹的是。。传进来这个paramter的type不是NestedList

340. Longest Substring with At Most K Distinct Characters
	典型的滑动窗口题目。可以用count dict来做。

	也可以优化到用一个dict记录每个char的最大index。

	需要删除的时候找最小index
	【可能因为char的种类不够多吧，找min index挺快的】

	还有一个很神奇的做法，就是不需要保证窗口是正确的。
	用count dict只要长度大于k，每次left + 1， right + 1
	否则只有right + 1。
	思路是：在窗口失效的情况下，窗口长度是不会变长的。

341. Flatten Nested List Iterator
	本来以为是一道挺简单的题目。

	重点是需要recursion！
	（自己真的不会写C++了）
	可以用stack。

342. Power of Four
	直接bit 操作就好了。
	n & (n - 1) == 0判断是2的幂，然后 n & 0x55555555判断是否为奇数位。

343. Integer Break
	数学题目。
	自己推导一下1到10，发现只需要选2和3，选其他都是亏。

	再仔细想想，其实应该贪婪3。

346. Moving Average from Data Stream
	送分的。

347. Top K Frequent Elements
	和 LC 692 一模一样。
	不过可以关注一下python builtin sort。
	使用的是TimSort。

348. Design Tic-Tac-Toe
	反正我又不需要把整个棋版放出来，那直接用dictionary记录就好了。

351. Android Unlock Patterns
	这个题真的是。。。
	有时间再回来优化吧。真的烦，

354. Russian Doll Envelopes
	转化成LIS。

	按一边排序，另一边用降序。
	神奇。

355. Design Twitter
	其实直接做就好了。
	我想到的优化就是 因为只需要最近的10个动态，所以其实可以限制每个用户的动态个数上限为10个。

357. Count Numbers with Unique Digits
	排列组合题目。
	特殊考虑一下 n = 0。

359. Logger Rate Limiter
	最简单的做法就是一个time hashtable存一存上次的时间。

	当然了，这完全可以提升。首先是优化空间，我们可以用哈希值来当作key，而不是string 本身。
	速度的话，多层hashtable是一个不错的选择，先比较长度，再比较前一小部分的哈希，最后再是整体哈希。

	另一个方面，对于空间而言，我们还需要某种垃圾回收机制，因为我们其实只需要记录最近10秒的log。
	更前面的对我们而言是没有用的。

	如果时间是单调递增的，那么可以维护一个deque来做周期性的清理工作。
	当然了，也可以使用two hashtable swapping的解决方案来做清理工作。

361. Bomb Enemy
	感觉就在那儿。没想好怎么写。

	维护一个row_kill和col_kill[n]变量。
	这样就不需要每个slot查找O(m+n)了。

362. Design Hit Counter
	我的思路是 【累积和数组】 + 【二分搜索上界】

	不过因为它说了time一定是monotonic increasing，并且只要5分钟内的。
	所以可以用circular array （或者dict）做。
	这个机制比我的思路要好很多。
	因为它有垃圾回收机制，保证了整体的空间开销不会爆炸。
	虽然getHits需要遍历，但是也就是O(300)

	上面的做法都太蠢了吧。。
	直接用queue做不应该是最简单的嘛！
	为了处理同一个时间点有大量的hit，我们可以往queue里面插入pair就好了。
	为了避免遍历整个queue来计算有多少hit，我们额外维护一个count变量就好了。

364. Nested List Weight Sum II
	因为不知道depth是多少，所以我的做法是直接明了的求出来depth。
	还有一种做法，不求depth。我们可以统计一个数应该要被加几次。
	因为一个数出现在当前depth，之后直到摸到最深的depth之前，它都需要每次再加。
	所以可以用bfs的思路做。

365. Water and Jug Problem
	长见识了。
	我用BFS做的。哈哈哈哈哈哈哈！5%

	了解一下GCD的几个性质：GCD(X, Y) = D
	一定存在 aX + bY = D，a和b是整数

	所以我们只需要判断Z 是不是 D的倍数就好了。
	很神奇吧！

	为什么呢？
	if x > y: x, y = y, x

	volume = 0
	while True:
		if volume < x: volume += y
		else: volume -= x

		if volume == z:
			return True
		if volume == 0:
			return False
	仔细想想，只可能小桶里有一部分水，大桶有全部水或者没水这几个情况。

367. Valid Perfect Square
	二分法就好了。

368. Largest Divisible Subset
	好题目。
	数学题hhhh

	先排序！这样新加入的元素就是最大的。
	因为这个set要满足所有元素两两为因数，
	所以只需要那当前set最大的去除想放进来的数，除尽了就可以。

	生成结果有点麻烦。个人喜欢backtracking + memo的写法。

369. Plus One Linked List
	我的做法是翻转，加法，翻转。

	因为只加一嘛，所以找最右边的非9的数字，然后将更右边的所有值设置为0，也可以。

370. Range Addition
	可以O(N)做出来。

	活跃计数，先把updates拆开转成两种事件，添加 和 减少。然后保存在对应的下标中。
	然后从左到右模拟一遍时间线就好了。

373. Find K Pairs with Smallest Sums
	pq就可以了。
	可以优化到至多保持K个。这样就是Klog(K)。

375. Guess Number Higher or Lower II
	好题目！一开始以为就是二分路径。仔细想才发现是DP。

	DP[i][j]描述: 猜范围[i, j]需要的最少开销。
	DP[i][j] = min(max(dp[i][k - 1], dp[k + 1][j]) + k)
	直白说就是猜一个值的开销，加上两边较大开销的一边。整体方案取最小值。

376. Wiggle Subsequence
	【锯齿形】数组。

	我只想出来O(N^2)的。
	O(N)的做法就是up = down + 1;和down = up + 1;
	还可以贪心做。很神奇。

377. Combination Sum IV
	backtracking + memorization 或者 DP都可以。

378. Kth Smallest Element in a Sorted Matrix
	我的想法还是用pq做。和merge K linked list思路很像。
	不过这样就没有用到每列也是排序过的这个性质。
	添加两个set后反而还慢了hhhhh。

	标答有nlog(n)，用binary search。
	需要仔细研究！
	def getLessEqual(val):
            res = 0
            i, j = n - 1, 0
            while i >= 0 and j < n:
                if matrix[i][j] > val:
                    i -= 1
                else:
                    res += i + 1
                    j += 1
            return res
        
        while lo <= hi:
            mid = lo + ((hi - lo) >> 1)	# mid不保证是matrix里面的值。
            count = getLessEqual(mid)
            if count < k:
                lo = mid + 1
            else:
                hi = mid - 1
        
        return lo

    第一个要点：最小值在左上。最大值在右下。
    第二个要点：沿着左下到右上比较，当前值如果小于等于mid，那么他上边的所有值都小于。然后往右走。
                                 当前值如果大于mid，那我们只能往上走，因为右边的值也会大于mid。
    第三个要点：以range base而不是index base的binary search一定可以返回array里面的值吗？
               还真他妈可以！还尼玛可以证明！
               lo<=a_k<a_mid<=hi will be true, 
               and the loop ends at lo=hi, which means a_mid has to equal to a_k.

380. Insert Delete GetRandom O(1)
	有意思的一道题目。
	为了实现random是O(1)，所以使用array最方便。
	array为了实现delete也是O(1)，使用一个dict记录index最方便。
	每次remove，拿到对应的index，把尾巴的element放过去，删除尾巴就好。

381. Insert Delete GetRandom O(1) - Duplicates allowed
	和上面那道题差不多。把hashtablde改一下，里面放hashset就好了。
	每次随机选一个victim出来，然后还是一样的，尾巴的放过去。

384. Shuffle an Array
	Fisher-Yate algorithm。
	可以证明对于每一个元素，它最后在每一个slot的概率是一样的。

386. Lexicographical Numbers
	一个DFS就可以了。为了更快一点，可以剪枝最下面一层。加一个break。

388. Longest Absolute File Path
	就是一个栈。我们先预处理一下input就好做了。
	拿到每个file对应的level，name和is_file。

392. Is Subsequence
	扫描一遍就好了。

	但是！如果是用双指针一个一个比较，真的没有使用内建函数find()快！

	python内建函数是真的快啊！

393. UTF-8 Validation
	就是直接验证嘛。读题不仔细，一开始以为只是一个UTF8。

	有什么简单的写法？可以加一个count来表示后面有几个是后缀块。
	当然，这道题可以hardcode出来。只要前提是只有least 8 bits are used。

394. Decode String
	其实就是实现计算器。

	来实现一下上次看到的 可以处理括号的 计算器版本。

	如果发现左括号，就往stack上push之前的结果和之前的符号（这个题里没有符号的需求）

363. Max Sum of Rectangle No Larger Than K
	今天做这道题的状态不是很好。
	这道题是 "Max sum of subarray no larget than k in 1-D array" 的拓展版。
	一维数组的做法就是 【累积和】 + 【二分查找】
	拓展到二维应该也是一样的。

	我们假设number of rows >> number of columns
	row^2 * (col + col*log(col)) >> col^2 & (row + row*log(row))

	这里有一个优化可以做。如果"max sum of subarray"是小于k的，就不需要跑O(Nlog(N))的部分了。
	用的是Kadane algorithm，但是我们还得避免全负数的情况。

385. Mini Parser
	还是用计算器的递归写法做的。

395. Longest Substring with At Least K Repeating Characters
	仔细思考。如果一个char在string中次数少于k次，那么一定不能有它。
	所以会从这里断开。
	断开之后每部分再跑一遍就好了。 RUNTIME呢？


398. Random Pick Index
	重要！！！！
	全新的算法知识。

	蓄水池抽样算法！
	适用于数据流，【在不知道具体有多少数据的情况下】

	拓展开，还有分布式蓄水池抽样算法。
	将数据流分为K分，每个线程跑一个单机版生成M个candidate的蓄水池抽样。
	【数据被选为candidate的概率：M / N_k】
	统计所有数据量，在这个范围内生成随机数，选择对应的线程，等概率不放回地取出一个数据加入结果。
	【选中N_k线程作为生成机器的概率：N_k / N】
	【选中N_k中的一个candiate的概率：1 / M】
	所以一个数据选中作为结果的概率：
		M (重复M次选取) * (M / N_k) * (N_k / N) * (1 / M) = M / N

399. Evaluate Division
	G家的高频题目是不一样呀。

	最简单的就是用图实现了。不过搜索有可能会到O(n)。

	还有一种办法【我想的】。这个方法没有预先计算所有可能！
	这样可以实现O(1)的所有查找。
	核心思路就是用变量代替，解方程组。
	a / b = 3 --> b = x; a = 3x
	如果替代变量不一样，我们就再套一层变量替代。
	a / b = 3 --> b = x; a = 3x
	c / d = 5 --> d = y; c = 5y
	a / c = 2 --> 3x / 5y = 2 --> y = m; x = (10 / 3) * m

401. Binary Watch
	这道题？

	看discussion有一个很简单的python写法。
	['%d:%02d' % (h, m) for h in range(12) for m in range(60) if (bin(h) + bin(m)).count('1') == num]
	就是每个都试一试hhhh

	我的做法是拆开两部分，hour和minute分别生成。hour就那么点，枚举就好了。
	minute的话，用backtracking生成吧。

404. Sum of Left Leaves
	可以recursive。用模板就可以了。我额外加了一个from的parameter来记录from。

	当然iterative也是可以的。我写的是中序。

	也可以不加入_from，使用
	if root.left and not root.left.left and not root.left.right:

405. Convert a Number to Hexadecimal
	这道题对负数的要求挺迷惑的。
	'-1' -> 'ffffffff'。
	这不就相当于，把这个signed int转成unsigned int了吗。。

406. Queue Reconstruction by Height
	这道题真的有意思！！！
	去他吗的backtracking。
	如果从最矮的开始考虑，那么他的k就是它应该呆的位置。
	那第二矮的呢？遍历找够空。所以整体是O(N^2)。

	还有一种办法就是从最高的开始构造。
	核心是：矮的人站的位置对高的人来说，是没有影响的。
	所以我们先把高的人排列好，矮的人自己挑位置就好了。
	这样也是O(N^2)。但是！python的list.insert(index, element)太快了。。
	比上面快了整整6倍。当然，这个方法其实真正O(N)的遍历也比上面少。

	接着开始记录学到的东西。
	1. square root decomposition.
		通过这个方法，我们可以把O(N^2)变成O(N*sqrt(N))。
		核心思路就是把整个array打断成几段。
		这样遍历段只需要O(sqrt(N))，在一个段内插入也只需要O(sqrt(N))。
		if m * m > len(people):
			blocks.insert(i + 1, block[m/2:])
			del block[m/2:]

	2. 计算inversion的变形，用mergesort实现O(Nlog(N))。
		仔细学习一下。
		如果我们一开始把people按照身高从低到高，所需人数从高到低排。
		那么，people[i]左边的都是比他矮或者一样高的，右边都是比他高或者一样高的。

		这样一来，people[i][1]，也就是所需人数，就是inversion的个数。
		计算inversion可以用mergesort来做。

		核心落在了merge这个步骤里。
		L,R描述左右两candidate的身高。
		LL,RR描述左右两candidate的剩下的所需人数。

		我们优先选择剩下所需人数少的，如果一样，选择身高矮的，如果一样，选择右边。
		为什么？作者是用反证法做的。
		1. LL < RR.应该选择L，如果选择R，那么在之后为了满足RR个inversion，LL也会减少。这样LL会变成负数。
		2. LL > RR.应该选择R，如果选择L，那么在之后为了满足LL个inversion，RR也会减少。这样RR会变成负数。
		3. LL = RR.
			I.  L < R. 应该选择L，如果选择R，那么LL会减少1.在之后为了满足RR个inversion，LL会变成负数。
			II. R < L. 应该选择R，如果选择L，那么在之后为了满足LL个inversion，RR也会相应减少到0.但是！因为L在R前面，其实RR会off by 1.



	3. 构造BST然后inorder打印，average O(Nlog(N))。
	4. BIT！

409. Longest Palindrome
	记录一下有没有奇数个的，其他的全部贪婪。

410. Split Array Largest Sum
	Google的题真的好！

	验证一个值是否可行只需要O(n), 因为这里说了所有值是非负数
	二分法找最小可行值。 整体是O(nlog(n))

	用DP。
	DP[i][j]表示 分成 i 组 用前j个数 需要的最小sum
	dp[i][j] = min(max(dp[i - 1][k], cumu_sums[j] - cumu_sums[k]) for k in range(j))
	这个会超时。 不过这个可以用于存在负数的情况。

	可以做超大展开。
	1. 只有非负数，不过是子序列，而不是子数组。
		解法： 排序后，维护size = M的minheap。贪心做法。
	2. 有负数，子序列。
		解法： 排序后用下面的方法。
	3. 有负数，子数组。 
		解法： 和LC410的DP思路差不多，修改一下转移方程即可。

413. Arithmetic Slices
	找长度大于等于的等差数列subarray个数。

	因为是subarray，所以滑动窗口嘛。

414. Third Maximum Number
	炫技炫技！炫炫炫！
	什么min_heap啊，什么quick_select啊，都拉出来溜溜！
	最简单三变量也写一写奥！

415. Add Strings
	又是实现加法。可以reverse之后做，要不就麻烦点，找到共有部分，然后处理。

416. Partition Equal Subset Sum
	好题，好题。
	和LC 1049是同一个概念。

	问题转化：
		0 / 1 背包问题特殊应用。
		我们不在意value，只在意能不能填满size=W的背包。

		可以推广到多重背包，详见《背包问题9讲》。

417. Pacific Atlantic Water Flow
	我们从海洋往内陆找，找哪些内陆可以到达海洋就好了。
	最后再遍历一遍，看哪些内陆可以到达两个海洋。

419. Battleships in a Board
	可以直接用DFS嘛，BFS也行。

	不过为了常数空间和不修改原矩阵，上面两个方法不行。
	因为只可能有一横或者一竖，所以可以很简单的判断一艘船的头部。
	判断左边和上边都没有'X'就可以了。

421. Maximum XOR of Two Numbers in an Array
	这道题。神题目！！！
	mark住！！！

	为了实现O(N)，太酷了。

	可以用hashset或者bitwise trie。

	先考虑 hashset，我们假设最大值的长度为L。
	那么最大值不会大于 2 ^ L - 1。
	我们一位一位地找，对于第一位，如果有一个数第一位是1，那么我们就看有没有一个数第一位是0。
	因为这两个数xor，我们就可以把leftmost的位设置为1.

	所以我们用一个prefix hashset来记录所有数的prefix。
	因为 A XOR B = C -->  A = B XOR C
	所以为了判断我们想要的maximum prefix可不可以实现，我们只需要找 B XOR C 在不在prefix里面。
	(A, B是数的prefix， C是我们的maximum)

	但是这么做不会过滤一些不必要的选项。
	For example, after two steps of max XOR computation (11***)
	it's quite obvious that 25 should be paired with 00 prefix, i.e. with 2, 3, or 5.
	3 = (00011) 10 = (01010) 5 = (00101) 25 = (11001) 2 = (00010) 8 = (01000)
	所以我们引入trie来做，因为在遍历trie的时候，我们还可以过滤一些不需要的选项。


423. Reconstruct Original Digits from English
	挺有意思的。统计字符频率后，用backtracking吗？

	不用哦，0246875319的顺序可以贪婪。

426. Convert Binary Search Tree to Sorted Doubly Linked List
	我记得做过一道转single linked list的。

	思路都是一样的。直接inorder traversal就好了。

	为了写起来方便，可以加一个dummy node。

427. Construct Quad Tree
	我一开始想的先构造完成，然后尝试合并。

	后面发现这个做法貌似慢很多？没仔细想。

	那就先查是不是只有一个值，再做呗。就不需要尝试合并了。

429. N-ary Tree Level Order Traversal
	BFS嘛。写就是了。

430. Flatten a Multilevel Doubly Linked List
	有意思的一道题目。

	如何写才是关键。我自己写的recursive的方法，太慢了hhhh

	可以直接iterative，如果有child就直接找到tail，设置好接着跑。

	还有用stack的方法，感觉也是挺巧妙的。先插入next，再插入child，这样就保证了优先处理child。

432. All O`one Data Structure
	这道题，做了好久。

	这道题就是和LFU非常非常像。可以说是LFU的升级版。
	因为这道题需要我们实现remove，而LFU不需要这个功能。

	为了实现remove并且在O(1)时间找到下一个 min_layer，我们需要再多维护一个链表。
	这个链表里装着哪些layer是有东西的。

434. Number of Segments in a String
	len(s.split())

435. Non-overlapping Intervals
	我的做法居然是最优的hhhh
	可以贪心嘛，我们按照 开始时间，结束时间排序。然后贪心着做。
	如果一个interval (x, y) 和现在的end有重叠，那么end = min(end, y)，然后我们必须舍弃一个。
	如果没有，直接更新end。

	核心思路是保证当前的窗口是最小的。

	DP的做法是O(N^2)，还是需要排序。然后从后往前判断是否有重叠。

437. Path Sum III
	挺有意思的。还是利用 【累计和】 dict。
	结合树的遍历模板。需要主要的是，在遍历完一个节点后，需要 cumus[_sum] -= 1

438. Find All Anagrams in a String
	就是滑动窗口啦。
	python用Counter实现应该是最简单的。

	没用counter的话，我用了两个dict来做。一边是invalid，一边是required。
	只有当两个都是空的时候，才是合法的。

439. Ternary Expression Parser
	我对parser的理解真的不深。

	我的做法还是像计算器的做法一样，维护一个全局的index，然后递归做。

	这道题可以把string反转后，往stack上推，只要发现一个ternary expression，立刻算。

442. Find All Duplicates in an Array
	和448挺像的。标记负号就可以了。

445. Add Two Numbers II
	这道题吧hhh python做真的简单。

	如果考虑其他语言overflow的问题，可以用stack来反转？
	如果stack不行的话，那就只有先遍历找长度，然后再逐步构建回来。

446. Arithmetic Slices II - Subsequence
	就是一个O(N^2)的DP问题。
	我一开始想压缩一下空间开销，发现不太可以。

	这道题估计数据量很大，写法真的很影响时间！
	总结：
		1. collections.defaultdict()如果使用tuple当作key的话，速度会慢一些。因为tuple的hash需要计算。而且gc也麻烦。
		2. if diff in dp[j]:
			dp[i][diff] += dp[j][diff]
			res += dp[j][diff]
			这个代码如果去掉if的话，也会慢很多。因为前面的几个dict其实key是很少的
			但是如果我们删掉if，那么会一直扩展dict里的key，然后dict就需要扩容

	还有一个很难想到但是最快的方法。时间开销在有大量重复元素的时候，接近线性。
	我们用pre 和 post记录每个元素在当前下标i前面和后面的个数。
	然后内层循环我们就不需要遍历下标i前面的所有下标了，只需要遍历pre里的key。
	(a,b,c)是一个等差序列，那么我们可以计算出c=2*b-a。接着我就可以查c是否在post里面。
	如果c在的话，那么就多少个a，就有多少个(a,b,c)。
	接着考虑长度更长的序列，因为dp[i][j]里存的是以arr[i]结尾，前一个元素是j的等差序列个数。
	所以如果a在dp[b]里面，则说明已经有一些以(a, b)结尾的等差序列个数了，那么这些都可以一起加到(b, c)的序列里。

447. Number of Boomerangs
	这道题果然是google的呀。
	需要利用到hashtable把三层循环优化到两层。

	写法还挺重要的，abs(x1 - x2) ** 2的速度慢的令人发指。

448. Find All Numbers Disappeared in an Array
	要O(n) + O(1)。那就用标记负号吧。

449. Serialize and Deserialize BST
	BST的重要性质。只需要前序或者后序就可以重建。
	并且！ 只需要O(N)。用合法窗口做，需要有一个reference of index。
	重点：如果是post order，因为是从后往前，需要先建立right，再left。

	回到压缩的部分来，直接val转str肯定是可以的。
	但是这样的话 val = 12345 就需要 5 个 bytes来储存。

	因为int只有四个bytes，所以可以用四个char来装。
	这样之后，也不需要delimiter了，因为固定每个val用4个bytes来装。

451. Sort Characters By Frequency
	统计词频 + 排序。
	这也是median？？

452. Minimum Number of Arrows to Burst Balloons
	贪心解法。先排序。

453. Minimum Moves to Equal Array Elements
	这道题有意思啊。

	给N-1个元素加1，相当于给其中一个元素减1。
	这个也太牛了。

454. 4Sum II
	把A+B的所有情况统计一下。
	然后跑C+D看看结果的负数有没有在A+B的情况里，有的话就加count。

455. Assign Cookies
	贪心就好了。排序一下。

456. 132 Pattern
	我觉得这道题挺难的。。
	我只能相当用min然后N^2的做法。

	可以用cumu_min + stack做。

458. Poor Pigs
	那道老鼠的千药题目。。。这次是猪猪。

	每只猪猪能提供的信息：能测多少轮 + 1

	pow(猪猪的数量,每只猪猪能提供的信息) > 药的瓶数

459. Repeated Substring Pattern
	这道easy。不简单啊。
	最简单的办法就是直接验证嘛。看看能不能分为几等份。

	还可以用KMP！
	KMP中的 最长公共前缀后缀数组 可以用来解决这个问题。
	我们只需要检查这个数组最后一项，是大于0的，且 _next[-1] % (len(s) - _next[-1]) == 0

	补充！！
	有一个超级牛的做法！
	我们新建一个字符串 t = s + s。
	假设s可以有substring x构成，那么 s = n * x
	那么 t = 2n * x
	我们移除t的开头和结尾，这样会破坏开头和结尾两个substring，t[1:-1] = (2n - 2) * x

	这个时候，如果 s 仍然是 t 的substring，那么 2n - 2 >= n; n >= 2
	如果 s 不是 t 的substring，那么 2n - 2 < n; 0 < n < 2 --> n == 1

	我们可以发现，只有 n >= 2 的时候，s才可以合法地由substring x构成。
	所以我们只需要判断 s 是否在 t[1:-1] 内。

463. Island Perimeter
	O(N^2)扫描一遍就好了。

	可以优化一下策略，不需要每个slot都查邻居。
	我们可以统计有多少个1， 然后乘以4就是总共的边数（有重复）。
	然后统计有多少个边是非法的，这个地方关键是只统计一边，比如左上或者右下。最后乘以2。

464. Can I Win
	又是一道游戏博弈题目。

	分析一下游戏规则，任意拿一个数。先到target就赢了。

	还是top down好想呀。只要result(next_state) == LOSE --> result(cur_state) = WIN
	题目限制了范围，选取范围只有20个数最多。所以用状态压缩会节省大量空间。

	当然了，还可以等差数列求和，算一下简单的case。


465. Optimal Account Balancing
	直接转化为：一个正负整数数组，最少需要多少次合并，使全员变为0。
		比如：[-6, 5, 3, -2, 7, -7]
			7 + (-7) = 0
			5 + (-6) = -1
			3 + (-1) = 2
			2 + (-2) = 0
			一共需要4次。

	值得注意的是，贪心算法是不行的。

	那么如何操作呢。【需要之后仔细研究。】
	只能brute force，因为这个是NP-complete。

	⭐：BFS的写法学习一下。
		res = 0
        while len(balance):
            n = len(balance)
            deq = collections.deque([(balance[0], [0], 1)])
            while deq:
                b, path, start = deq.popleft()
                if b == 0:
                    break
                for i in range(start, n):
                    deq.append((b + balance[i], path + [i], i + 1))
            res += len(path) - 1
            balance = [balance[i] for i in range(n) if i not in set(path)]

	可以优化一下，brute force之前先把类似(7, -7)这种消除。

468. Validate IP Address
	IF编程。
	需要考虑的细节挺多的。要仔细推。

470. Implement Rand10() Using Rand7()
	很有意思的一道题目。彻底学习了什么是【拒绝采样】
	通过 7 * (rand7() - 1) + rand7()，我们可以得到[1, 49]的均匀分布。
	放弃掉[41, 49]，剩下的可以取余。
	这样的【拒绝采样率】接近20%，算一下期望值，E[x] = 2.45

	可以优化嘛？
	肯定可以的，按照信息学理论，一次rand7()可以提供 log_2(7) 个信息
	rand10()可以提供 log_2(10) 个信息
	所以理论极限是 至少需要期望值为 log_7(10) 次 rand7() 来模拟 rand10()

	有一种简单的思路，就是降低【拒绝采样率】。

	在上面的基础方案中，我们抛弃了[41, 49]。其实我们可以接着用。
	7 * (a - 41) + rand7()，可以得到[1, 63]的均匀分布。
	这下子我们就只需要抛弃3个值, [61, 63]。

	再进一步，7 * (a - 61) + rand7()，可以得到[1, 21]的均匀分布。
	这下就只用抛弃一个值了，也就是21。

	这样的流程下来，拒绝采样率有多少呢？ 0.000417
	那期望值呢？ E[x] = 1.98

	另外还有一种思路，rand7 拒绝 [7]， 然后rand7() 拒绝 [6, 7]
	第一个结果决定答案在[1,5]还是[6,10]，第二个结果作为base。
	不过这个方法的期望值是 7/6 + 7/5 = 2.56

	还可以继续优化嘛？
	可以，不过上面这种构造均匀分布的方法已经到极限了。需要从另外的角度入手。

	按照LEE大神说的，我们可以构造
	cache, upper = 0, 1
	def rand10(self):
		cache, upper = self.cache, self.upper
		while cache // 10 == upper // 10:
			cache, upper = cache % 10, upper % 10
			cache, upper = cache * 7 + rand7() - 1, upper * 7
		res = cache % 10 + 1
		self.cache, self.upper = cache // 10, upper // 10
		return res
	这个函数在干什么？和我们上面在干一样的事情，但是注意这一行
		self.cache, self.upper = cache // 10, upper // 10
	和我们上面不一样的是，他保存了一些东西，方便下次的计算。
	而我们的做法每次都是从头开始。为什么保存了会更快？
	核心：
		它保存了什么？保存了十位数。这个十位数其实也是等概率的！
		所以相当于在之后的rand10()中，我们第一次不是rand7()，
		而是rand了之前保存的十位数。因为这个是等概率的，所以我们直接用也没有关系。
	那这个做法的期望值是多少呢？ 
	不太会算hhh但是因为节省了开头中两次rand7()中的一次，所以肯定更优。





472. Concatenated Words
	LC 139 140的联动。
	反正runtime是O(N^2)，所以我先sort了一下。因为长的words必须由更短的多个构成。

	不使用memorization会TLE！

	和LC 140不一样的是，我们是逐个检查再加入到wordstart里面去的
	所以我们只能维护valid_memo。（只记录返回True的memo

	⭐：其实不sort也可以的hhhh 把所有word加到一个set里。
	    逐个扫描时 in range(1, len(word))，这个样子可以避免直接扫描自己整个。
	    剩下的都差不多，不过set还需要在recursion里面更新。
	    比如 "a", "b", "c", "abc": set一开始是{"a", "b", "c", "abc"}
	    在处理"abc"时，set还会添加"bc"。

	    这个方法还是要加memorization的！不过可以记录invalid的case。

480. Sliding Window Median
	我就直接用 O(nlogk) 做了。

	维护一下长度为K的排序窗口。

	剩下的方法之后有空再说吧hhhhhh

481. Magical String
	emmmmm。。

	怎么说呢，我直接生成了。结果还是标准答案？嗯？

482. License Key Formatting
	IF编程题目？没啥难度

485. Max Consecutive Ones
	哈哈啊哈！滑动呗！

486. Predict the Winner
	和那道石头的题目挺像的。

	有很多解法。游戏论的我自己感觉是最好理解的。
	Score(state, player_1) = max(gain + Score(nex_state, player_2))
	Score(state, player_2) = min(Score(nex_state, player_1))

	还有一种DP解法
	DP[i][j]描述当前玩家和另一个玩家分数差距
	a, b = nums[s] - DP[s + 1][e], nums[e] - DP[s][e - 1]
	DP[s][e] = max(a, b)

	这个可以进一步优化为一维的，所以整体来说是优于游戏论解法的。

487. Max Consecutive Ones II
	我用的zero_count来做dictionary，有点小题大做了。

	两个滑动窗口，prev和cur就好了。发现0就轮换。

490. The Maze
	BFS就好了。找目标点写得比较麻烦。

494. Target Sum
	好题！
	我的做法是memorization (start, target)。
	所以DP一定也是可以做的，但是因为target是不连续的，所以DP遍历可能会慢一些。

	当然了，仔细想想，也可以正序直接生成所有结果。用两个dict交换。
	这个方法也挺新颖的，记一下。

	最后一个方法，太牛了。
	sum(P) - sum(N) = S
	sum(P) - sum(N) + sum(P) + sum(N) = S + sum(nums)
	2 * sum(P) = S + sum(nums)
	sum(P) = (S + sum(nums)) // 2

	所以，如果S + sum(nums)是奇数，就不可能存在。
	问题转化成了，在一个数组里，找subset的个数，和为(S + sum(nums)) // 2。

	0/1 knapsack问题，且是刚好填满的变种。

495. Teemo Attacking
	就是一个easy。在末尾加一个float('inf')好写很多。

496. Next Greater Element I
	就是一个构造next_larger数组的问题。
	单调栈就可以了。


498. Diagonal Traverse
	这道题是mathwork的题？
	写得挺麻烦的。看discussion有用排序做的。
	我是更新dx和dy。不过角落点的处理顺序重要。

500. Keyboard Row
	一个哈希表就可以了。

503. Next Greater Element II
	可以直接跑两遍LC496。

	也可以仔细分析一下，我们可以先选到max element。
	然后从这个元素右边开始跑LC496.

504. Base 7
	注意一下负数和0。

507. Perfect Number
	这道题貌似还挺有名的。完美数还真有这个概念。
	不知道这个概念就直接验证吧hhhh

	概念: 偶数完美数必须是形如 2^(p - 1) * (2^p - 1) 的数字。
	其中，(2^p - 1) 是一个质数。
	奇数完美数还没有被找到过，但是推断是有的，比如大于 10^1500.

508. Most Frequent Subtree Sum
	还是一道简单题目。
	标准树模板就好了。遍历完了再找最大的frequency。

510. Inorder Successor in BST II
	这个没有root节点的reference。但是有parent指针，所以也可以写。
	两个情况：
	有右子树，那么就直接在右子树找最小的。（一直向左找）
	没有右子树，那么就得用parent向上走。如果发现当前节点是左节点，就可以返回。

513. Find Bottom Left Tree Value
	为啥是。。medium？

515. Find Largest Value in Each Tree Row
	DFS 和 BFS 都可以。
	DFS需要多传一个depth进去。

516. Longest Palindromic Subsequence
	和longest sequence貌似都是这么做的？

	DP就好了，注意下遍历的顺序。

518. Coin Change 2
	还是一个DP题目。
	是一道经典的knapsack题目。
	用前N种硬币，对于amount = i有多少种组合。
	dp[N][i] = dp[N - 1][i] + dp[N][i - coins[N]]

	也可以转成dp[amount + 1]。
	⭐：coin的loop要写在外面，避免重复。

521. Longest Uncommon Subsequence I
	MDZZ！还是需要逻辑分析下的【不过其实是题目描述的问题！

525. Contiguous Array
	转化一下：
		把0转成-1，最长连续数组和为0。

526. Beautiful Arrangement
	
	用backtracking做就好了。

	不过优化的东西挺有意思的，可以加一个memorization。
	更有趣的是 i 从 N 开始速度会快很多，因为这样更多的分支mod的值都会更小。而不是更接近N。

	可以试试bit mask编码。

528. Random Pick with Weight
	我想的有两种方法。
	第一种就是把weight打开，然后直接random.select()

	第二种就是用 【累积和】 数组，然后在和的范围内random一个值，二分法找合适区间。

529. Minesweeper
	就是一个DFS。

532. K-diff Pairs in an Array
	直接分类讨论。别多说话。

535. Encode and Decode TinyURL
	这其实是系统设计的一部分。

	如何设计TinyURL？

	首先考虑【使用场景】：
		1. 用户拿着longURL来网站注册获得tinyURL。
		2. 用户拿着tinyURL来网站查找对应longURL。
		3. 用户拿着tinyURL来网站修改对应longURL。
		4. 用户拿着tinyURL来网站取消绑定。

	我们需要考虑安全性嘛？
	我个人感觉不需要，因为tiny也好，long也好，反正都是public的。

	如果我们可以用 大小写字母 + 数字，长度固定为7位。
	那么我们一共有 62 ^ 7 个tinyURL可以分配。

	我们肯定需要建立某种 one-to-one 的mapping关系。

	可以使用hashvalue吗？可以是可以，不过处理collsion比较麻烦，所以先不讨论这个。

	最简单的就是使用increment id，然后把id转化成tinyURL。
	这样做的话，longURL和tinyURL之间其实是没有直接联系的。
	所以tiny和long都可以是primary key。

	如何处理distributed system？
		我们可以在tinyURL前面加 几位的服务器编码， 这样我们就可以去对应的服务器拿到longURL。
		这个样子的话，会有single point of failure。
		如何避免这个问题呢？RAFT协议？过半数的服务器保存？

538. Convert BST to Greater Tree
	好题目。
	哇，这居然就是reversed inorder traversal
	那就把三个方法都复习一下吧。

539. Minimum Time Difference
	暴力的话是O(N^2)，所以肯定排序会快很多。

	先把所有时间转成数字，排序后把第一个加 24 * 60插进去。
	这样就考虑了所有的情况。

	然后正常找就好了。

	有一个很有意思的优化，考虑鸽子洞原则，如果length > 24 * 60，就直接return 0。

540. Single Element in a Sorted Array
	需要log级别的时间开销，肯定是二分查找了。

	一个关键点，这样的一个数组，长度一定是奇数。
	如果我们找到一个pivot，和左右值都不一样，那么就找到了。
	如果和其中一边的值一样怎么缩小搜索范围呢？ 看长度！
	记得上面的关键，有final value值的数组，长度一定是奇数。
	当我们发现一个重复数字的时候，我们就将数组切割成了两块。只有其中一块是奇数长度。
	（因为只有 偶数 + 奇数 = 奇数）

542. 01 Matrix
	BFS就可以了。从所有0开始蔓延。

	还可以用DP的做法嗷，第一次上和左。第二次下和右。

543. Diameter of Binary Tree
	求高度。

545. Boundary of Binary Tree
	挺有意思的一道题。
	其实就是preorder加一些东西。（right boundary的时候是post？）
	需要加一个flag来标记当前的节点。


546. Remove Boxes
	这道题真的想不出来。

	DP[i][j][k]描述范围[i, j]且尾巴上有连续k个值和boxes[j]相同。

	temp = (1 + k) ** 2 + helper(i, j - 1, 0)
	temp = max(temp, helper(t + 1, j - 1, 0) + helper(i, t, k + 1))

	可以用pre数组优化遍历的部分。

547. Friend Circles
	undirected graph. 遍历需要访问几个点。

549. Binary Tree Longest Consecutive Sequence II
	和那道path的题目挺像的，返回之前额外考虑一下左边和右边通过node连起来的情况就好。

551. Student Attendance Record I
	没注意连续的。。。
	直接两个string.count就可以了。

	当然了，正则酷啊！  r".*(A.*A|LLL)"

556. Next Greater Element III
	就是next larget perumutation。

	唯一不一样的地方就是需要处理一下overflow。

557. Reverse Words in a String III
	python一行。split。

558. Quad Tree Intersection
	题目没有说清楚 一个是叶子节点，一个不是 要怎么操作。
	不过其实还是树的递归做法。真的比。。二叉树难写多了。

561. Array Partition I
	排序就好了。
	不过因为范围挺小的嘛，[-10000, 10000]。所以直接用计数排序可以优化到O(N)？
	还是看testcase的大小。

563. Binary Tree Tilt
	树模板。

564. Find the Closest Palindrome
	个人感觉，这道题其实是 LC. 866 的退化版本。

	只要知道如何构造next_palindrome和prev_palindrome就很简单了。

	我自己写得很复杂hhhh

	如果最后答案和原来数字同位数，假设原数字是abcde，那么答案一定是在 [ab(c+1)ba, ab(c-1)ba, abcba] 之中。
	如果位数不相同，那么答案只可能是 [99999, 100001]。

	实现这个就好了。

565. Array Nesting
	脑筋急转弯的感觉。
	因为长度是N，元素范围是[0, N - 1]，所以不可能有两个pointer指向同一个slot。
	所以直接遍历就好了。优化额外空间可以inplace改成None或者其他值。

572. Subtree of Another Tree
	可以每个点都跑一次check。
	或者前序？这是个好方法。转化成了strstr。

583. Delete Operation for Two Strings
	和edit distance是一模一样的。

589. N-ary Tree Preorder Traversal
	Iterative的做法有些意思。

590. N-ary Tree Postorder Traversal
	Iterative在二叉树的时候，需要引入一个last变量，来记录最后一次print的节点。
	现在不需要这个了。因为我们需要记录index，所以只需要判断index是不是到了len(children)

593. Valid Square
	检查四个点能否构成正方形。我们任意选择三个点，这三个点一定是等腰直角三角形。
	然后剩下这个点，到选出来的三个点的距离排序后和等腰直角三角形三边是一样的。

605. Can Place Flowers
	贪心就好了。从左种到右。
	傻逼优化可以在N == 0的时候就停止。

609. Find Duplicate File in System
	文字游戏。读清楚了挺简单的。

	follow up更有意思。
	BFS一般而言会更消耗空间，考虑一下BFS搜索的例子。但是可以有locality

	对于大文件，我们可以先比较文件大小！！！这个点非常有意思。然后可以hash一小部分比较！！
	最后再比较全部的。

616. Add Bold Tag in String
	这道题如果直接暴力做，时间是 N * sum(len(word) for word in words)

	我的做法是KMP求出所有interval，然后merge，最后得到结果。
	这个样子的runtime是 # of word * (N + len(word)) + sort

	再一次。自己手写的KMP，和自带的find方法，差太多了。
	差了他妈的8倍！

617. Merge Two Binary Trees
	简单题目。
	直接dfs。模板就行。

621. Task Scheduler
	我一开始想的是模拟hhhh

	模拟的思路其实很简单。
	不过采用时间块的做法挺新颖的，这样就节省使用了deque。
	为什么时间块是可以的？这才是有意思的地方，因为一般思路都是一步一步做。
		直觉上来看，时间块长度为N + 1，那么下一次选择的时候，
		变成可选的除了里面还有的，第一次被选出来的也可以被选了。但其他的都还不行。

		假设我们选出来了K个，这K个的count都减少1，那么他们的相对大小关系是没有变的。
		下一轮我们要么选第一个选出来的，或者选其他没被选出来的。
		如果选第一个被选出来的，那么是可以的，选其他的也可以。
		过一轮，选出来的第二个cd有结束了。所以方案正确。

	还有一种方法就是直接算有多少idle。
	仔细思考一下，空闲的时间其实只由出现频率最高的任务和cd大小决定！
	其他剩下的任务就是往里面填格子！

	所以total = maxi + n * (maxi - 1) + extra
	如果total小于length，说明不需要任何的idle。

628. Maximum Product of Three Numbers
	排序是标准的sequence做法。
	不过也可以暴力点，记录两个最小值和三个最大值。

634. Find the Derangement of An Array
	好题目！
	我自己的思路是这样的：
	N个人，我们先让第一个人选择，他有N-1个选择。选择一个座位k后，轮到第k个人选择。
	第k个人选择时，有两种情况：
	1. 第k个人选择了第一个座位，那么问题就变成了 N - 2 个人 选座位。
	2. 第k个人没有选择第一个座位，那么就有 n - 2个情况是这样的，轮到第三个人选择。

	这样子的递推式就很麻烦。。
	(n - 1) * (self.findDerangement(n - 2) + (n - 2) * (self.findDerangement(n - 3) + (n - 3) * ...))
	就需要写一个helper方法。

	上面的方法是对的，可惜是递归的，MLE了。然后我他妈。。转不出来iterative的。
	其实问题主要出在第二个情况，仔细想想。
	第k个人没有选择第一个座位，那不就是说明，在这个情况下，第k个人不能坐在第一个座位上了吗！
	就变成了 N - 1 个人 选座位！

	递归的还是MLE了hhhh，写iterative的吧。

635. Design Log Storage System
	因为数据量够小，所以其实直接存起来，然后需要的时候遍历就可以了。

	更加优化的做法是Trie，比较难写。
	retrieve分为两部分，第一部分是s和e相同的时候，相当于在trie里搜索common prefix。

	第二部分s和e不一样，中间部分我们直接全部retrieve，两头分开处理。

636. Exclusive Time of Functions
	就是用stack来做。每次insert新的时候，更新上一个task的一部分消耗时间。

	但是这道题目有问题，它rescheduling的顺序就是stack。
	我们来考虑一下拓展版的这道题。
	1. 如果rescheduling是在一个task结束后，优先选择pool里id最小/最大的。
		那就不能使用stack了。应该使用deque来做。
		并且还需要维护一个current_id变量，因为涉及到两种结束，没有发生rescheduling和发生了。


640. Solve the Equation
	IF编程。无敌。百度人工智能。

642. Design Search Autocomplete System
	Amazon高频题目。
	我的想法是用trie做。
	一开始的想法是用最简单的trie做。然后找frequency top3需要dfs当前节点所有sentence，排序后选前三。
	后面觉得这个办法有点慢，因为需要找到当前节点下的所有sentence。

	改进了一下，系统中一个hashmap存<index, (sentence, time)>。
	每个节点存top3的index。
	因为只存前三的index，所以排序的时间就是O(1)。

	然后是修改input方法，当用户输入完一个sentence后，我们检查当前节点是否被标记为了特殊。
	如果被标记了，所以这个sentence之前已经出现过了，那我们就只需要修改storage里的time，然后再插入一次。
	如果当前节点是None或者没有被标记，都说明这个sentence是新的，那么我们就在storage插入一个新的键值对。
	然后执行插入。

	这个样子做的好处，首先是查找的速度是O(1)了，因为不需要再去找所有sentence。
	而且每个sentence我们只存了一遍，三个index也就是三个int，并不会消耗很多的内存。


646. Maximum Length of Pair Chain
	抽象出来就是 最长上升子序列。

	可以用N^2的DP，也可以用Nlog(N)的best candidate

	不过有一个很聪明的写法。按照end来排序，然后直接贪心就可以。

649. Dota2 Senate
	唉，感觉都已经想出来了。差一点点。
	就是模拟，因为最优策略肯定是ban他后面第一个异类。
	先遍历一遍找到双方人数，然后模拟到一方人数为0.
	可以优化，模拟到一方人数大于另一方的两倍就可以停了。

652. Find Duplicate Subtrees
	可以serialization每个节点。用hashtable存一下。
	发现重复的，就加入到结果里去。

653. Two Sum IV - Input is a BST
	送分题目。

654. Maximum Binary Tree
	基础做法就是左右递归。

	可以线性时间做出来。用循环结合单调递减栈就好了。

656. Coin Path
	使用BFS会超时！
	只能用DP思路想。和那道minimum jump挺像的其实。
	dp[i]表示这个点到终点的最小开销。
	对于每一个dp[i]，搜索dp[i+1]...dp[i+B]找到最小开销，并记录下一个点的位置。
	这个样子的runtime是O(nB).

	可以使用deque将时间优化到O(n)。
	dp的东西还是不变，关键是优化搜索最小开销。
		while i >= 0:
            if not window: break
            if A[i] != -1:
                cost = A[i] + window[-1][0]
                to = window[-1][1]
                dp[i] = (cost, to)
                while window and window[0][0] >= cost:
                    window.popleft()
                window.appendleft((cost, i))
            if i + B == window[-1][1]:
                window.pop()
            i -= 1
    window右边表示最远可以跳到的点。发现一个cost，如果左边的cost大于他，那就不要左边的了。

659. Split Array into Consecutive Subsequences
	我的做法是用heap + 贪心做的。整体应该是 O(Nlog(N))，不过heap的size应该远小于N，所以还真的挺快的。

	还有一个O(N)的做法思路很巧妙。
	我们统计下有多少个chain在num x结束。然后如果数组里有x，那么就让这个chain在x + 1结束。
	太巧妙了！ 核心思想仍然是贪婪。


660. Remove 9
	这道题有点意思哈。

	 1 2 3 4 5 6 7 8
	 10 11 12 13 14 15 16 17 18
	 20 21 22 23 24 25 26 27 28

	 仔细看看，这不就是！！！ 九进制吗！！！

	 拓展！

	 那如果单独删除一个7会怎么样呢？
	 	还是 九进制。 7 map to 8, 8 map to 9。

	 那如果删除3和7呢？
	 	八进制。 012不变，345->456 67->89。

	 魔法。

661. Image Smoother
	嗯。和那个alive game差不多。要inplace的话就用高8位。

662. Maximum Width of Binary Tree
	BFS就好了。加一个index来记录长度。

663. Equal Tree Partition
	可以。
	我的做法是存一下每一个点的sum。
	但是我之后撒比了，又遍历了一次找有咩有合法的cut。

	分成和相等的两部分啊！！！
	只需要看total / 2在不在set里不就好了吗！！！
	记得root的sum不能放进set！

666. Path Sum IV
	这道题一开始觉得暴力就好了。不过写起来还挺麻烦的。
	我自己的做法是把nodes分层了。
	然后统计每一层的reference count，乘上对应的value就拿到结果了。
	写得比较复杂。

	仔细想想，(depth, pos)不就已经完全定义了一个node了吗！
	所以还是可以用树的模板来做。
	left = (depth + 1, 2 * pos - 1)
	right = (left[0], left[1] - 1)

667. Beautiful Arrangement II
	差值要出现K个不同的，可以用前 K + 1 个元素构造出来，剩下的直接正常顺序就好了。

668. Kth Smallest Number in Multiplication Table
	其实和 LC.378 思路是一模一样的。
	不同的一点在于， LC.378数有多少个比value小需要时间 O(M + N)。

	核心仍然是二分法。

	这道题因为matrix是固定的，所以我们可以优化这个。
	用除法就可以优化到 O(M) 或者 O(N)。（这里就可以用倒置，来做第二个优化，选择小的参数来遍历）

676. Implement Magic Dictionary
	可以将每个字符换成"*"然后再存到hashtable里。
	有一个优化的方法，就是二层哈希表，第一层用长度来区分。这样可以快很多。

678. Valid Parenthesis String
	我的思路是贪心，记录一下star的个数，发现非法的 右括号可以直接用star抵消。
	最后再查非法的 左括号。但是只记录star个数没有办法知道这个star在不在非法左括号的右边。
	所以两边跑一次，就知道结果了。

	这个样子空间开销是O(1)，如果我们用两个stack来记录的话，空间开销是O(N)，但是我们就可以知道
	star是不是在左括号的右边了。所以只需要跑一遍。

	标答的方法也挺有意思。
	也是贪心。
	维护lo和hi两个变量。

679. 24 Game
	肯定是backtracking题目。不过自己想复杂了。没写好。
	关键的python简单写法没记住啊
	from operator import truediv, mul, add, sub

	discussion里面的神仙，服了。
	https://leetcode.com/problems/24-game/discuss/107670/topic
	bad = '떢븻각걎냇갅갸꺚뵟숣욄뵴뵞뤼갈갌뤔떌옊메늄숭캸긶꺛옖갍뇐쩢곴듇걯궄옕왹눞솴걃끗긬땉궿가쌀낐걄숤뺴늘걘꽸숢걂갋갃쫐꼔솾쩡쇔솿끛뤜간븺쩬웨딴옠뤛갂뵪덠놤빐옋귒늂갰갖놥궾갆옌뼘묰거갎긷낤겼'
    return chr(int(''.join(map(str, sorted(nums)))) + 42921) not in bad

680. Valid Palindrome II
	从外面开始匹配，找到第一个不匹配的字符对，要么删前面，要么删后面。

681. Next Closest Time
	挺有意思的一道题目。直接模拟时钟tick，慢慢找到个合适的就行了。

687. Longest Univalue Path
	首先要注意的是，这道题定义的path是edge数量，不是点的数量。
	一开始写的比较繁琐，不过肯定是bottom up就是啦。

690. Employee Importance
	就是一棵树，求和。

691. Stickers to Spell Word
	神题目！
	其实就是背包问题的变种，不过挺复杂的。
	我们得先预处理item_Set。全部转成counter。
	然后只保留有交集的。
	domain = [collections.Counter(sticker) & needed for sticker in stickers]
	然后过滤被完美替代的。
	if any(domain[i] == domain[i] & domain[j] for j in range(len(domain)) if i != j):
		domain.pop(i)

	python的Counter使用不够熟悉是个问题！需要从后向前删也是一个技巧！

	然后剩下的就可以DP做了。
	不过应该是因为测试集的关系，用BFS会快很多。
	for char, count in s.items():
		new_T = new_T.replace(char, '', count)
	这个BFS的写法就很简单清晰，从结果往前搜索也是一个大优化。

692. Top K Frequent Words
	统计用hashtable。
	找前K个，可以sort全部。

	⭐：用constant size heap 和 quicksort都需要再sort一次。
	因为这两个不是stable sort。

693. Binary Number with Alternating Bits
	送分题，转化成string或者直接除都可以。

694. Number of Distinct Islands
	因为island之间可以移动进行比较。所以只能记录形状。

	形状怎么记录？
		我想的是，保证一定的遍历规则，记录每次方向就好了。
		后面发现有点小问题，还得加上step。

695. Max Area of Island
	DFS.优化visited数组可以直接把当前点设置为0.

696. Count Binary Substrings
	这道题还挺难想的。
	我一开始的想法是 N^2。用类似palindrome from center的做法。
	然后意识到肯定可以 O(N) 之内用 滑动窗口 解决，不过代码不怎么好写。

	最后才想到可以用 果树 那道题的写法，用(end, front)交替来记录两种字符的个数。

697. Degree of an Array
	emmm。记录一下degree，然后找左右。

698. Partition to K Equal Sum Subsets
	神题。 backtracking需要灵魂的if优化。
	排序后先放大的会快很多。
	if slots[j] == 0: break
	这一句if提升至少100倍速度。因为当前如果是空的，就不用去下一个空的了。

704. Binary Search
	程序员检测。

706. Design HashMap
	如何处理collision才是关键。
	要么probing，要么chaining。

	probing的一个重要问题就是，需要引入state: EMPTY, OCCUPIED, DELETED
	为什么？因为如果删除直接将slot清空，那么会导致接下来的查找在这个slot停住，而不是接着往后找。

	chaining就没啥了。链表就好。

	然后引入balance factor，在需要的时候扩大哈希表，提高性能。

708. Insert into a Sorted Circular Linked List
	遍历一遍就可以了。
	【这道题我做的时候是有问题的，所以用python模拟了一个do while loop】

712. Minimum ASCII Delete Sum for Two Strings
	就是 edit distance 的变形。
	准确是一模一样。

	有一个很有意思的做法。
	我的做法是直接计算开销，使用了大量的ord()函数。
	我们可以把思路颠倒过来，统计有多少字符是不用修改的。
	最后算出来总和，减去合法的，就是修改需要的数值。
	这个样子的话，ord函数的使用就少很多。


716. Max Stack
	好题目。真的是好题目。

	两种做法，two stack或者 double linked list + heap + lazy remove.

	第一种只有popMax()是O(N)，其他是O(1)。
	第二种除了两个top()是O(1)，其他是O(logN)。

	java里面有treemap，可以好写很多。

718. Maximum Length of Repeated Subarray
	edit distance变形基础题目。没想明白有点难过。

	DP[i][j] = DP[i - 1][j - 1] + 1 if A[i] == B[j]。

	同样的，只求最长的长度，可以用 binary search + rolling hash。

	rolling hash记得要 取模！！ MOD = 10**9 + 7

719. Find K-th Smallest Pair Distance
	这道题又是验证的思路。
	因为求有多少pair是小于distance只需要线性时间。
	所以可以二分法求最小满足条件的distance，在范围[0, max - min]。
	整体runtime是 Nlog(W) + Nlog(N)。后面这个是因为要排序。

721. Accounts Merge
	这道题的关键，我个人认为是双层的union find结构。
	当然了，最底下一层不需要改变。
	我们需要改变parent[person]，这样子，整个过程就快了很多。

723. Candy Crush
	直接做就好了。。
	写法能写简单点就更好了。python的简便写法还是要记住的。
	zip(*matrix)就可以实现倒置！

725. Split Linked List in Parts
	这道题没啥意思，注意一下需要断开每部分的连接就好了。

731. My Calendar II
	这道题线段树的标准适用场景啊？？？
	怎么他妈的能这么慢。

	还有一般思路的O(N^2)解法，我们两个数组，里面放区间。
	先去2区间查有没有交集，有的话就不能加。
	没有的话，就去1区间查交集，放进2里面，然后把这个区间放进1。

	还有一个做法是active window。
	和事件挺像的，我们将(start, open), (end, close)加入到有序的时间序列里。
	然后遍历一遍时间序列，如果active大于2，就说明刚刚添加的两个有问题，需要删除。

733. Flood Fill
	BFS, DFS.

734. Sentence Similarity
	一个hashtable就好了。

735. Asteroid Collision
	用stack做！

737. Sentence Similarity II
	这道题我记得做过啊，可能有很类似的吧。
	就是一个union find就好了。为了优化空间和时间，我们可以不用string本来作为key。把它离散化了。

739. Daily Temperatures
	还是构造next larger数组。
	单调栈解决。

740. Delete and Earn
	我自己一开始想的是状态压缩然后backtracking。结果TLE了。

	仔细想想。这居然就是一个rubber house的变形！！！
	太厉害了。

	DP[i]描述： 前i个key可以得到的最大值。
	if keys[i - 1] + 1 != keys[i]:
		DP[i] = DP[i - 1] + values[keys[i]]
	else:
		DP[i] = max(DP[i - 2] + values[keys[i]], DP[i - 1])

741. Cherry Pickup
	这道题真的。。做不出来。脑子不够用了。

	首先想到的是，过去一趟回来一趟，其实就是过去两趟。

	相当于两个人同时过去。

	如果用 (x1, y1), (x2, y2)来描述两个人的坐标。
	那么可以知道x1 + y1 = x2 + y2
	所以我们只需要这四个变量中的三个，就可以得到两个人的坐标。

	所以就是三维DP。。。

	DP[x1][y1][y2]。

	转移方程的话，考虑两个人都往下走，都往左走，一个一个分开走，一共四个情况。。
	还需要特殊处理两个人在同一个坐标的情况。

	太震撼了。

742. Closest Leaf in a Binary Tree
	两种做法。
	第一种，转化成图hhhhh 然后bfs。

	第二种，先遍历树找到path，然后再根据path的节点搜索。这个解法代码量有点高。

744. Find Smallest Letter Greater Than Target
	一开始没有注意是sorted的。

	直接binary search就好了。

	return letters[bisect.bisect(letters, target) % len(letters)]

746. Min Cost Climbing Stairs
	送分DP？
	可以优化到二变量。

747. Largest Number At Least Twice of Others
	可以一遍做出来。
	找第一大和第二大的元素。

752. Open the Lock
	Google面试题。

	BFS就可以了。visited和deadends可以合并一下。

	优化的话，个人感觉可以双向搜索。不过写起来挺麻烦的。
	【双向不太行，舍弃】

754. Reach a Number
	数学问题。貌似从easy修改到了medium。

	我们先用等差数列可以求出来需要最少一直 加【或者减】多少项，才能到达或者超过目标。
	maxi = int((2 * target) ** 0.5)

	如果结果和目标值一样，直接返回。
	如果结果和目标值差距是偶数，那么我们可以翻转中间一个合适的值，步数不变。
	如果差值是奇数，我们没有办法通过翻转来消除差值，一定需要引入更多步。
	再引入一步，如果差值变成了偶数，那么就可以了。
	如果还是奇数，那么就再引入一步，这两步是一定可以构成 +1 【或者-1】的，让差值变为偶数。
	所以最差就是 maxi + 2.


755. Pour Water
	这道题有意思的。官方答案居然是模拟，也太慢了吧！

	可以用两个stack来做。还需要left_bound和right_bound两个变量。
	每次浇完水后，尝试拓展两个bound。
	如果左边可以，那么就取左边stack的顶浇水
	之后，如果这个slot的高度和右边一样，就pop。
	如果这个slot左边的比他低，加入stack。

756. Pyramid Transition Matrix
	一开始没有读懂题目。
	我的想法就是backtracking + 二层的hashtable。
	为什么要用二层的呢？因为可以更快的剪枝。
	其实python直接用(A,B)作为键值也是可以的。

759. Employee Free Time
	最简单也是最简洁的做法，和merge interval一样的思路。
	先排序，然后就可以找到中间的间隔了。

	假设每个人有K个工作时间段，一共N个人。
	上面的做法是 NK * log(NK)

	但是我觉得这个做法，就没有利用题目里面每个人的时间段已经被排序了 这个性质。
	因为已经被排序了，所以我们是可以在线性时间内求出来 当前空闲时间段 - 当前人工作时间段 的结果的。
	这样子的话，我们的runtime是 (P + K) * N， P是当前空闲时间段个数。

	可以看出来，如果当前空闲时间段个数是比较少的，这个做法是优于上面做法的。

763. Partition Labels
	count_dict后 接一个 滑动窗口 就好了。

764. Largest Plus Sign
	我一开始的想法就是遍历几次，统计一下每个slot的最小值。整体是O(N^2)。

	还有一个做法记录一下。我们把row和col分开，然后把所有mines的坐标分别放进去排序。
	这样之后，我们就知道里面没有出现的坐标都是'1'。
	一行一行遍历，我们就可以拿到left和right。up和down可以用二分法在对应的col里找。

	这样子最差是O(N^2 log(N))，但是因为 max(N) = 500，而mines最多只有5000个，所以极端例子只会出现在 N = 70的时候。
	完全可以接受。 整个matrix越稀疏，这个方法就越快。

	然后还有一步灵魂优化，我们在遍历range(left + 1, right)的时候，完全不用考虑差与当前answer的点。
	用range(left + 1 + answer, right - answer)可以超级高效！

766. Toeplitz Matrix
	easy题目。验证简单。
	follow up才是有意思的部分。
	如果只能一次加载一行？如何验证？我想的是类似rotate array，只需要记录上一行。
	如果一次只能加载一行的一部分？
		分几部分验证也可以？
		或者hash两行！

767. Reorganize String
	贪心做法就好了。
	统计出现次数，每次都用最高的两个构成。

	如果一个数超过了长度的一半，就不可能构成。

769. Max Chunks To Make Sorted
	脑筋急转弯？
	给我们一个值，我们可以知道它应该在有序数组的哪里，所以中间的值必须在一个chunk里面。
	我的做法是存一个下标的hashtable，然后从0到len(arr) - 1，不断合并区间，如果不需要合并则说明找到了一个chunk。

	这个做法还可以优化，我们可以直接拿原数组从左边开始找。
	并且只需要维护right变量。

772. Basic Calculator III
	这道题和 计算器2【LC.227】 就没什么区别了。
	用stack还是好做很多。
	我用了递归的思路做的，也可以直接用iterative的办法，因为递归只是在最后把stack加起来了。
	所以我们可以在iterative里，碰到右括号的时候，把stack里一连串的数加起来就好了。

773. Sliding Puzzle
	这道题有意思啊。
	核心是转化成图。找一个点到另一个点的最短路径。
	我们可以把board转成一个string，这样方便找。
	最短路径用BFS找。
	neighbors = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
	这个写法也挺好用的

780. Reaching Points
	个人觉得是个好题目。
	从sx,sy出发找tx,ty比较难。
	但是从tx,ty找回去，会很简单。
	因为sx,sy都是非负数，所以一定只有一条路可以回去。

	还是不够。还得继续思考。
	如果tx > ty，那么下一次迭代回去一定是(tx - ty, ty)
	如果这次还是tx > ty呢？还是这么迭代。什么时候停止，只有当第一项小于ty才停止。
	所以是取余数加快过程。
	
785. Is Graph Bipartite?
	 我一开始做的挺复杂的，没有想明白其实就是dfs或者bfs上色。

	 我的做法是建立两个set，尝试往里添加，然后set交换检查正确性。

	 但其实只需要dfs或者bfs来标记颜色就好了。
	 遇到没处理过的点，上色。处理过的点，检查颜色是否合法。

787. Cheapest Flights Within K Stops
	就是Dijkstra's实现嘛。

	不过因为还有stop的个数要求，所以visited的处理需要修改一下。
	之后的同城市访问，stop个数需要小于保存值，才允许接着跑。

788. Rotated Digits
	自己写的是backtracking。和LC.1088. Confusing Number II差不多。

	不过其实完全没有必要，因为是digit单独旋转。
	所以最差的做法也就是O(Nlog(N))。

	关键是O(log(N))的做法。太秀了。
	对于当前的digit，遍历比它小的digit，记作k。
	如果k属于[0,1,8,2,5,6,9]，那么我们可以算出来保持这一位是k，右边所有位合格的数字个数。 7 ** (len(N) - i - 1)
	如果k属于[0,1,8]并且已经见过的数字里没有[2,5,6,9]，那么我们还需要减去 3 ** (len(N) - i - 1)

	如果k不属于[0,1,8,2,5,6,9]，直接返回。

	最后还需要查N是不是合格的。

791. Custom Sort String
	这就是拓扑排序吧？
	用count sort的概念可以线性时间。

792. Number of Matching Subsequences
	LC.392的拓展。

	我的思路是扫描一遍S，然后把index都记下来。
	之后检查word就可以用二分法搜索了。
	但是最坏情况挺差的，如果S只有一种字母的话，runtime是O(N^2*log(N))

	还有一种方法就是一次性跟踪所有的words进展情况。

	值得一提！python如果直接用LC.392内建的find函数，其实还要快一些。
	再提一下！对于我的方法，bisect这个module比自己写的binary search快太多了。

794. Valid Tic-Tac-Toe State
	就只有一个关键点：
		先手赢的话，棋子个数多一
		后手赢的话，棋子个数相同

797. All Paths From Source to Target
	DFS。

801. Minimum Swaps To Make Sequences Increasing
	google面试题！dominos的进阶版本。
	我一开始的想法是贪心，总共需要O(8N)。

	其实可以用DP来做。
	DP[i][0]和DP[i][1]描述 到 arr[i] 为止，维持两个arr都是increasing的最小开销。
	0 表示当前 这个下标没有被旋转， 1表示当前 这个下标被旋转了。

809. Expressive Words
	其实就是一个线性扫描而已。

814. Binary Tree Pruning
	LEE大神的标准树题型的模板！
	膜拜。

824. Goat Latin
	注意下大小写。没了。

828. Unique Letter String
	一直在考虑如何从substring的角度做。
	后面发现只需要考虑有多少个包括num[i]的substring，且num[i]是uni的。
	这样想，就可以构造next和prev数组
	然后计算每个范围中有多少个substring就好了。

	牛啊。
	Lee甚至还可以做到只用一遍遍历。
	index = collections.defaultdict(lambda: [-1, -1])

829. Consecutive Numbers Sum
	看不懂discussion的方法。。
	我的做法就是O(sqrt(N))。
	判断等差数列是否满足。
	因为 [x + (x + n - 1)] * n = 2 * N
	范围是 range(1, int(N ** 0.5) + 1) --> 这个是项数的枚举

834. Sum of Distances in Tree
	好题目。其实关键就是如何利用一个节点的结果，快速计算其他的节点。
	我们一次DFS可以求出来一个节点的total distance。
	然后我们从这个节点走一步，到它的neighbor，那么这个节点的其他距离都会 +1，neighbor这边的距离都会 -1。
	所以，整体是O(N)。

	我们用一次DFS求出来节点0的整体距离和每个节点的child_count。

	然后再用一次dfs从节点0出发，计算每个节点的整体距离。

836. Rectangle Overlap
	和 LC.223 一个意思。
	还是写法问题而已hhh
	两个min，两个max

837. New 21 Game
	一开始就想到了DP。
	但是我的递推式，是从前面往后面推的，需要O(NK)，没法优化。

	但是如果换个思路，从后面往前面推，就好想很多。
	在[K,N]的起始点中，概率都是1。

	f(x) = (1/w)*(f(x+1) + f(x+2) + .. + f(x+w))

	f(x+1) - f(x) = (1/w)*(f(x+2) + f(x+3) + .. + f(x+w+1)) - (1/w)*(f(x+1) + f(x+2) + .. + f(x+w))
	              = (1/w)*(f(x+w+1)-f(x+1))

	f(x) = f(x+1) - (1/w)*(f(x+w+1)-f(x+1))
	     = (1+w/w)*f(x+1) - (1/w)*f(x+w+1)

	这样递推式就可以直接O(N)算出来结果了。
	※：非常重要的一点，我这个递推式，base case需要手算f(K - 1)。

	还可以再优化，不需要每次都去乘。
	我们加一个变量 S = f(x + 1) + ... f(x + W)
	那么 f(x) = S / W，我们只需要维护S就好了。

	正向做也是可以O(N)的，只是我傻逼。

838. Push Dominoes
	仔细读完题里的描述，就是判断'.'离'L'还是'R'更近。
	最简单的做法就是两遍遍历，分别找到'.'左边R的距离和右边L的距离。

839. Similar String Groups
	思路挺快的。union find + 线性时间查similar。

	M, N = len(A), len(A[0])
	上面的方法runtime是 O(MMN)

	如何优化？
	如果 M < N 的话，上面的方法挺好的。
	但是如果 M > N, 我们可以优化到O(MNN)

	如何优化？我们可以枚举一个word的所有similar word，这一步耗时N^2
	然后用哈希表存所有word，查每一个similar word在不在这个表里，是O(1).

	这个优化太有意思了！！
	需要具体分析参数大小，有意思。

	比较坑的一点是，input里面有重复项。


840. Magic Squares In Grid
	IF编程。

841. Keys and Rooms
	直接用DFS就可以了。
	不知道会不会有重复钥匙，用hash set方便一些。

843. Guess the Word
	这道题有意思诶！
	其实最核心的点是，我们可以过滤哪些不可能的单词。
	假设 guess(word) = 3，那么其实，任何和word的match不是3的我们都可以过滤！

	基于这一点，我们就可以写出来最初步的一版，每次都选第一个去猜，然后过滤不可能的选项。

	但是这个做法还不够，问题就出在，我们应该选哪个去猜。这里有很多个思路。
	1. 我们选最有可能的单词去猜。
		这是我的想法，我们统计(char, index)的频率，然后算出每个单词的经验得分，每次用最高分去猜。
	2. 我们选可以过滤最多不可能选项的单词去猜。
		这个想法也挺有意思的，我们可以事先算出来每一个单词 W，组合 guess(W) 的结果，还会剩下多少单词。
		我们选会剩下最少单词的那个单词，去猜。
	3. 分析。
		这个思路和第二个挺像的。因为是 完全独立且随机的字符，所以两个单词完全不match的概率高达80%。
		我们也可以事先算出来，一个单词和多少个单词完全不match。
		然后我们选择完全不match最少的那个单词，因为这个单词和更多的其他单词有match。
		如果这个单词和答案完全不match，那么我们一下子就可以过滤掉一大堆可能性。

844. Backspace String Compare
	简单的做法就是构造嘛。
	空间开销如何优化到 O(1) 才是关键。
	我们可以从尾巴倒过来遍历，两个string拿到不能被删除的字符对，进行比较。

	python solution真的。。。太漂亮了。
	def F(S):
		skip = 0
		for x in reversed(S):
			if x == '#':
				skip += 1
			elif skip:
				skip -= 1
			else:
				yield x
	return all(x == y for x, y in itertools.izip_longest(F(S), F(T)))

846. Hand of Straights
	我的做法是count dict + sort(keys) + 遍历

	时间是O(Mlog(M) + MW)，M是不同的元素个数。

	但是如果W过大，这个方法有可能不行。
	LEE大神太牛逼了。

	用一个deque来保存当前打开了多少个session。

	deque的长度够了说明最左边的session们完成了，pop掉并更新open_session_count。

	最后检查count是否为0。

848. Shifting Letters
	花里胡哨的。
	就是一个suffix sum + 取模。

849. Maximize Distance to Closest Person
	我的做法是把所有人的位置提出来，然后遍历一遍就好了。

	也可以直接扫描。

850. Rectangle Area II
	妈的，自己写了两个小时，结果是错的。
	和sky line，一条线扫描挺像的。结果我的方法，记录open和close的时候，把interval给merge了。
	这个样子的话，我就没有办法记录重复的interval，而重复的interval是需要被记录的。

	那就直接暴力做，把计算一条线的算法修改一下就好了。

	线段树看自己的总结！

851. Loud and Rich
	描述还是挺花哨的，仔细想想，就是一棵树。

852. Peak Index in a Mountain Array
	？这是啥？
	在A最后面加一个-1。方便写。

	当然了，也可以二分法做。

853. Car Fleet
	哎，没想出来。我想着模拟了。

	一个很关键的点，每辆车到达终点的时间是可以计算出来的。
	如果后面的车到达终点的时间比前面车要短，那么他们一定是会碰到的。

	基于这个，我们可以先把车按照位置排序，求出对应的时间，然后从右边查起。O(N)扫描 + O(Nlog(N))排序

855. Exam Room
	和 LC.849 挺像的，我的做法就是维护一个有序的座位表。
	然后插入的话，就找里面最大的间距的位置，然后二分法插入。

	删除就直接O(N)删除。

	看了discussion，自己真的是垃圾。。
	居然还可以seat和leave都是O(log(N))。

	我们可以记录空出来的座位区间，然后给它们一个priority。
	需要处理两个特殊情况，就是头和尾。单独计算priority就好了。

	然后我们leave的时候，需要额外两个hashtable来帮助我们合并区间。
	合并区间并不需要当时就去删除这个区间，因为删除之后需要heapify，O(N)。
	我们可以把这个区间标记为invalid，之后heappop的时候忽略他就好了。

856. Score of Parentheses
	我发现这种题目我不太擅长，要想一会儿。

	不会做出了最优解还可以hhh
	不需要使用stack，因为只有括号。
	stack的思路是计算器，先算里面的。
	我们完全可以记录当前的level，直接在扫描到base case "()"的时候，计算出这个base case的值。
	if c == '(':
		multi *= 2
	if c == ')':
		multi //= 2
		if S[i - 1] == '(':
			result += multi

861. Score After Flipping Matrix
	这道题。。个人猜出来了肯定是贪心。。结果细节没想清楚hhh

	backtacking和brute force都不行。
	不过brute force的写法挺有意思的。
	用到了 trans = state ^ (state - 1) 来计算哪些row需要被flip，从上一个state到这个state。

	贪心的做法就是保证第一列都是1，然后之后的列就看max(col, H - col)了。

863. All Nodes Distance K in Binary Tree
	我的做法就是加parent node。
	然后就直接BFS。

	还可以存路径？然后搜索吧。

866. Prime Palindrome
	这道题我写了好多代码。。。

	复习一下 is_prime(N) 的做法。
		就说一下方便记忆的吧，肯定是遍历range(2, sqrt(N))。
		有一个优化，因为所有质数都在6的倍数的两侧，所以我们可以在这个范围内，只用6倍数两侧的数去除N，看看能否除的尽。
		证明: 6k, 6k + 1, 6k + 2, 6k + 3, 6k - 2, 6k - 1
			 6k, 6k + 2 和 6k - 2 被 2 整除。 6k + 3 被 3 整除。
			 所以只有 6k 两侧的数可能是质数。

		所以可以把range优化成range(5, 1 + sqrt(N), 6)

	然后是另一个证明，所有偶数长度的回文数字，都被11整除。
	11 % 11 = 1111 % 11 = 111111 % 11 = 11111111 % 11 = 0
	1001 % 11 = (1111 - 11 * 10) % 11 = 0
	100001 = (111111 - 1111 * 10) % 11 = 0

	abcddcba % 11 = (a * 10000001 + b * 100001 * 10 + c * 1001 * 100 + d * 11 * 1000) % 11 = 0

	好了。前面的工作说完了。

	怎么做呢？
	我们可以在log时间级，求得下一个回文数字。然后去验证这个数字是不是质数就好了。


886. Possible Bipartition
	DFS上色就好了。两个颜色。

875. Koko Eating Bananas
	还是因为验证只需要线性时间，所以可以二分 + 验证。
	整体是O(Nlog(N))。 （python的for loop是真的慢啊）

	还有一个做法，个人感觉应该是testcase给的不好，所以快很多。
	就是求和算平均值，验证平均值可不可以。
	不可以的话就+1，重新验证。

	验证了一下，就是testcase给的不好。估计testcase的值分布比较接近。
	比如[1,1,1,1,1,1,99999998,99999999]，这个做法必TLE。因为average远小于max，而最后值必须是max - 1。

877. Stone Game
	hhhhhh 这就是那道传说中的【return True】.

	还是做一下其他的拓展吧。

	总长度是【奇数】:
		def stoneGame(self, piles):

			@functools.lru_cache(None)
			def helper(i, j):
				if i == j:
					return piles[i]

				return max(piles[i] - helper(i + 1, j), piles[j] - helper(i, j - 1))

			return helper(0, len(piles) - 1) > 0

889. Construct Binary Tree from Preorder and Postorder Traversal
	一开始没有什么头绪。仔细思考一下，post order前面的元素个数就是他左右子树的大小。
	所以可以用范围来做。

	优化成O(N)有很多做法。第一种就是转index_hashtable，这样就优化了线性时间的index()。
	Lee大神给的解法很清晰！记录一下。
	preIndex, posIndex = 0, 0
	def constructFromPrePost(self, pre, post):
		root = TreeNode(pre[self.preIndex])
		self.preIndex += 1
		if (root.val != post[self.posIndex]):
			root.left = self.constructFromPrePost(pre, post)
		if (root.val != post[self.posIndex]):
			root.right = self.constructFromPrePost(pre, post)
		self.posIndex += 1
		return root
	这个写法可以转成iterative stack版本。很精妙。

	三种组合都可以生成二叉树啦。
	而且都可以O(N)。都可以用index_hashtable做。

890. Find and Replace Pattern
	直接做就可以了。题目意思挺麻烦的，要求是bijection。

897. Increasing Order Search Tree
	啊。还是中序遍历嘛。
	Morris依然可以实现，所以最优的肯定是Morris。
	（就是不需要recovery那一步了。然后记录一个pre node）

904. Fruit Into Baskets
	就是longest atmost 2 distinct subarray.

	只有两个嘛，所以可以有简单点的写法。
	记录 a 和 b，b是两个distinct出现最后的
	a = b = b_count = cur = res = 0
    for c in tree:
        cur = cur + 1 if c in (a, b) else b_count + 1
        b_count = b_count + 1 if c == b else 1
        if c != b:
            a, b = b, c
        res = max(res, cur)
    return res

905. Sort Array By Parity
	就是 快速选择排序 里面的 partition 部分。

906. Super Palindromes
	这些palindrome的题目，究竟是谁想出来的？？

	因为开方的计算量比乘法大，所以我们可以只用一次开方，之后的都有乘法来验证。
	求得第一个比sqrt(L)的回文数 N，然后一直生成下一个回文数，判断 N * N <= R

	看discussion发现了一个很牛逼的东西。
	# n, n^2
	(1, 1) (2, 4) (3, 9) (11, 121) (22, 484) (101, 10201) (111, 12321) (121, 14641) (202, 40804) (212, 44944) (1001, 1002001)
	(1111, 1234321) (2002, 4008004) ...

	除了前三个，只由 0 1 2构成。。所以比我那个做法的search space还要小很多。

907. Sum of Subarray Minimums
	很有用的一道题目。学习了单调栈的应用。

	我的解法是用单调栈来维护每个index的增量。
	这个解法也是O(n)，因为每个元素最多被访问两次。

	标准解法我觉得需要很强的逻辑分析能力。

	这个做法的核心是通过观察发现的:
    [1, 4, 5, 3, 7, 8, 2]: 包含3的subarray有多少个？
    3到左边界有4个元素，到右边界有4个元素，(包括自己)，那么一共有4 x 4 = 16个subarray。
    这16个subarray 的 最小值只可能是1，2，3。
    那我们把范围缩小一点，[4, 5, 3, 7, 8]这里面包括3的subarray的最小值只能是3。
        
    所以思路就出来了，对于每一个值，我们要找到它【左边比它小的】和【右边比它小的】值及对应的index。
    用【单调栈】可以在线性时间内找到每个点需要的左右边界。
    再求出到左右边界的距离，就好了。
        
    还有一个问题，重复值如何处理？
    prev_less, next_less分别设置为严格递增和递增就好了。	

908. Smallest Range I
	脑筋急转弯这道题。
	就是看diff = max(A) - min(A) 和 2 * K 之间的关系。

909. Snakes and Ladders
	其实就是BFS就可以实现了。

	但是二维是真的麻烦，尤其是他还是颠倒的。我直接转成了一维的。

	因为board其实挺小的，最大20 * 20。所以也不需要啥优化。

	优化一：
		如果是普通的slot的话，其实只需要走到最远的那个格子。

910. Smallest Range II
	这道题还挺有意思的。 和LC.908挺像的。
	考虑一个区间[A, B]，我们肯定不会[A - K, B + K]
	所以只剩下[A - K, B - K], [A + K, B + K], [A + K, B - K]。
	我们把数组排序，然后拿到min和max。
	如果整个数组都是加K，那么diff就是max - min。（answer的默认值）

	那么对于任意的A[i], A[i + 1]。我们肯定不会做 ++ 或者 --。
	因为 ++ 是我们得到answer默认值的操作。 --只可能扩大diff。

	所以只剩下 +- 了。
	那么直接求呗。answer = min(answer, max(a + K, _max) - min(b - K, _min))



915. Partition Array into Disjoint Intervals
	因为是分成两个subarray嘛。所以挺简单的。
	维护left_max和max_so_far就可以了。

921. Minimum Add to Make Parentheses Valid
	就是直接遍历一次，统计一下有多少个非法括号。

922. Sort Array By Parity II
	这种题目，还是 O(1) space的写法有意思。

924. Minimize Malware Spread
	DFS就好了。也可以union find。

	我一开始想了好久，以为删除一个点是任意一个点。。
    如果只能删除初始感染点，那就简单多了。
    每个没有访问过的初始感染点跑一遍，计算size和访问到的其他初始感染点数量

    只有感染点数量为1的connected component可以参与竞争。
    没有感染点数量为1的话，删谁都一样，删个index最小的。

930. Binary Subarrays With Sum
	和LC.560是一样的，subarray with sum equals k。

	因为是binary的数组，所以出现S之前一定得出现S-1。
	所有可以用滑动窗口来做。
	
	第一种思路就是把 【刚好和为S的数组个数】
	转化为 【至多和为S的数组个数】 - 【至多和为S - 1的数组个数】
	这道题要特殊处理一下0

	另一种思路就是直接数！
	找到了一个符合条件的窗口，缩小到最小窗口，记录缩小量
	窗口不合法了，重置缩小量，并更改左指针找到合法窗口
	⭐：和substring with k different characters差不多。

933. Number of Recent Calls
	和 LC.362 是一模一样的。
	啧啧啧，当时362的做法，太蠢了。

934. Shortest Bridge
	DFS + BFS。

935. Knight Dialer
	基础的DP题目。
	但是！！ LEE大神的做法太震撼了。
	问题可以转化为每个node到其他node的step为N的路径的总和。
	The power of matrix reveals the number of walks in an undirected graph.
	可以再次转化为matrix相乘。即可实现O(log(n))。

939. Minimum Area Rectangle
	我自己没想到优化的做法。可惜了。

	可以一层一层地遍历，然后把见过的 两点对和对应的x 记录一下。
	再看到 储存过的 两点对 时，就说明可以构成矩形。

947. Most Stones Removed with Same Row or Column
	union find就可以了。
	有一个union find的小技巧。
	parent = list(range(20000))
	px, py = find(x), find(10000 + y)

	因为只有10000个嘛。所以可以这么做。

948. Bag of Tokens
	贪心就可以了。
	先排序。然后左右两个指针。优先使用开销小的令牌。能量不够了就消耗一个点数兑换能量最大的令牌。

949. Largest Time for Given Digits
	可以暴力做嘛。反正就24个排列。

	还可以复习一下全排列的代码。

951. Flip Equivalent Binary Trees
	二叉树标准模版。
	可以分两种情况查，左左匹配和左右匹配。

953. Verifying an Alien Dictionary
	联动LC 269.没啥，转一个dictionary查找快很多。
	需要特别注意下 “apple” 和 "app"。

954. Array of Doubled Pairs
	count_dict然后sort之后贪婪。

	要处理下负数，我一开始是用了lambda sort，不过只要加abs就好了。
	sort dict.keys()而不是A会快很多。

955. Delete Columns to Make Sorted II
	贪心就可以，如果一列中间一对不行，只有删除。

	优化可以避免每次扫描所有str，而是去扫描仍然需要查找的。

957. Prison Cells After N Days
	这个可以转化一下。其实就是找无限循环小数的循环部分嘛。

	不过看discussion，才知道原来cycle最大长度是14。也是很有意思。

959. Regions Cut By Slashes
	挺有意思的一道题目。
	我们把一个正方形分成四个三角形，然后用union find就好做了。

961. N-Repeated Element in Size 2N Array
	count_dict的解法就不写了。
        
    2N个空格，N个空里的数值是一样的，剩下N个空的值不一样。
    而这个值是一定存在的，所以最坏情况就是间隔出现这个值。
    可以提前判断最坏情况，然后检查连续的对子就好了。

    类似排列组合的【插板问题】。

962. Maximum Width Ramp
	我自己的想法是单调栈 + 二分查找upper bound。

	其他的O(nlog(n))的解法还有直接下标排序。

	O(n)的做法有一个很神奇的：
		结合 累积最小值 和 反向累积最大值。
		如果cumu_min[i] <= r_cumu_max[j],
			说明在j之后（包括j）一定有一个大于cumu_min[i]的值，所以incr j。
		反之，incr i。

	震撼人心的还是LEE大神。优化了我的单调栈到O(n)。

	不需要每找到一个大于栈顶的值就二分法。
	可以把整个栈构造完，然后反向扫描数组，pop掉小于扫描值的栈顶，计算距离！

965. Univalued Binary Tree
	模板。

967. Numbers With Same Consecutive Differences
	注意一下 N = 1 或者 K = 0 的特殊情况。
	如果是用set来做bfs的话，就不要特殊考虑 K = 0了。

969. Pancake Sorting
	啊，听说比尔盖茨还有一篇这个的论文？
	我们还是写笨方法吧，每次找剩下元素的最大值
	和对应的index，先flip(index)然后再flip到对应的位置。

	没有使用"A[i] is a permutation of [1, 2, ..., A.length]"

	还有一种解法是不修改原来的数组。
	解法二：先将原来的数组的index排序，从大到小排。
	       最大值的好想，直接res.extend([i, N])
	       其他的值，我们需要模拟出这个元素在经历之前的flip后的真正位置。
	       for f in ans:
                if i <= f:
                    i = f+1 - i

970. Powerful Integers
	因为可以随便什么顺序嘛，所有简单很多。

	直接暴力枚举就可以。优化一下可以先算出来所有的component值，这样可以避免重复运算。

975. Odd Even Jump
	很有意思的一道题目。

	是 【单调栈】 的应用。

	奇数次：A[i] = x, 跳到 i右边的 大于等于 x 中的最小值
    偶数次：A[i] = x, 跳到 i右边的 小于等于 x 中的最大值
	问题的关键就在于如何（省时地）找到每个x后面的这两个值。

	如何将问题退化到 【单调栈】？

	我们将index按照元素大小排序，这样问题就转化成了找每个元素右边第一个大于它的元素。
	因为排序帮我们实现了极值的部分，找大于是为了实现找到i右边的部分。

	太牛了！

976. Largest Perimeter Triangle
	转化一下题目，找长度为3的sequence，max(sequence) < sum(sequence) - max(sequence)

	所以就是sort后从右到左滑动窗口。

977. Squares of a Sorted Array
	简单题目嘛。直接平方后sort是O(nlogn)

	还有牛逼的标准解答：
		观察发现大于等于0的部分平方后是不需要排序的。
		所以可以把A分成两部分，小于0的和大于等于0的。
		然后用类似merge two linked list的做法来做。
		这样是O(n)。

978. Longest Turbulent Subarray
	滑动窗口标准题目。

	需要额外注意下 "==" 的情况：直接left = right

979. Distribute Coins in Binary Tree
	有意思的一道题目。
	bottom up就好，保证每个subtree里面都是1。
	我的方法要修改树本身，就是child需要或者送出多少个，就更新count和parent。

	标准解法不需要修改树，不同的思路是不在child中更新，而是直接返回需要或者送出多少个。
	在parent里面统计两边再更新。

981. Time Based Key-Value Store
	本来我以为每个key存list，list需要按照timestamp排序，这样插入就是O(n)了。

	不过有一句话The timestamps for all TimeMap.set operations are strictly increasing.
	真好！所以插入就是O(1)，查找就是二分O(logn)。

	傻逼优化要记住，优先比较list头尾可以不用二分查找，只有中间的才需要！

982. Triples with Bitwise AND Equal To Zero
	这道题应该只有暴力枚举吧。。
	不过可以加一些memorization，比如选择i, j后，如果i&j在memo里，就不用再算了。

983. Minimum Cost For Tickets
	这道题肯定是用DP了。

	DP[i]描述到days[i]的最小开销。
	如何找到最小？遍历days[i]早的所有slot，如果相差小于7天，则min(dp[i], dp[j - 1] + costs[1])
	类推一下。
	挺慢的！！！！


	另一种做法，其实直接就用时间来当dp就好了，最长就365天嘛。

	今天不出门旅游的话，DP[i] = DP[i - 1]

	出门旅游的话，DP[i] = min(DP[i - 1] + costs[0], DP[max(0, i - 7]) + costs[1], DP[i - 30] + costs[2])

	和 332. Coin Change是一模一样的做法！

984. String Without AAA or BBB
	还是模拟？

	肯定是不用backtracking的，可以贪心来建造这个string。

	A > B就加aab, A < B就加bba, A == B就加ab。

	更新：模拟个屁啊。直接算就可以了！

985. Sum of Even Numbers After Queries
	送分题，模拟就是了。

986. Interval List Intersections
	emmmmmmm......

	我逻辑分析真的不强。

	我的第一个AC，居然是很单纯，很纯粹的模拟。。。

	聪明的做法是[max(start), min(end)], 如果min(end) >= max(start)

	那怎么更新pointer呢，A和B谁的end小，更新谁的。

987. Vertical Order Traversal of a Binary Tree
	这道题老子一开始想的top down。

	结果有一句话：
	If two nodes have the same position,
	then the value of the node that is reported first is the value that is smaller.

	因为要考虑同层的同vertical index的node，所以用BFS就好了。

	BFS每层结束后加入ans，记得先sort。

988. Smallest String Starting From Leaf
	这道题一开始我是用的bottom up。

	不过过不了最后一个test case！因为 s1 < s2并不保证 s1 + ch < s2 + ch。

	比如 abab < ab，但是 ababz < abz

	所以只能top down来比较完整的字符串！

989. Add to Array-Form of Integer
	送分啦！

	我写错啦！

	一定要记得连续进位的问题！【可以把进位加到K里面去】

990. Satisfiability of Equality Equations
	union find标准题目。

	第一遍先找等于的，建立union。

	第二遍找不等于的，看看又没有违规的。

	也可以用DFS做，connected conponent。给每个conponent上色嘛


991. Broken Calculator
	贪婪算法。
	需要思考一下数学的东西才好想。
	正向，反向都可以。
	反向的话：能除一定要先除，因为只能乘二，所以如果拿到奇数我们得先加一再除。

	正向的话：能乘一定要先乘，最后多的部分，需要在尽量前面减去。(这个跑得真慢啊)。

992. Subarrays with K Different Integers
	好题。
	有很多种思路可以做！

	值得记住的有：
		1.先算至多K个不同的subarray个数，再算至多K-1个不同的subarray个数
		  最后减法就好。
		2.先找到一个valid的滑动窗口，然后尽可能缩小他（找最短的K distinct）
		  左指针每移动一次，dp+=1
		  发生len(count_dict) > K的时候，重置dp = 1

993. Cousins in Binary Tree
	DFS或者BFS。改一改更快哦

994. Rotting Oranges
	BFS，最后检查是不是所有fresh都没了。

995. Minimum Number of K Consecutive Bit Flips
	这道题最基础的就是O(nK)的模拟。

	为了优化这个多余的K，我们可以维护flipped这个变量。

	1. 用一整个array来记录flip情况，O(n) + O(n)
	2. 用Deque来记录flipped需要变化的位置，O(n) + O(K)
	3. inplace方法，就是在A里面记录哪些subarray被翻转了。

996. Number of Squareful Arrays
	一开始读错题了。

	相当于找所有符合条件的排列嘛。
	考虑到有重复元素，我们可以修改下count dict的排列生成代码。

	思路是backtracking，不行了就提前结束分支。

	LEE大神提到还可以用dfs，结合提前计算所有可能的valid pair。

997. Find the Town Judge
	LC 277换个方法讲。
	只给了信任表，法官必须被N-1个人信任。
	所以被信任+1，信任-1(单纯为了排除这个人)。

998. Maximum Binary Tree II
	挺简单的一道题目。
	新插入的值在数组的最后：
	这个值如果大于当前max，那么就把整颗树作为这个值左子树。
	否则就递归到右子树解决。

999. Available Captures for Rook
	啊。直接搜索呗。

1000. Minimum Cost to Merge Stones
	这个我真的想不到啊。。。好难啊。

	第一个关键：可以直接判断长度是否可以merge为1个slot
		(n - 1) % (K - 1) == 0

	第二个关键：如果可以merge，那么如果把K个元素拿出来，剩下的也应该可以，除非长度不够

	第三个关键：其实不需要更新array来模拟整个过程。

	[3,2,4,1], K = 2:
		我们选择先merge [3,2]，然后是 [4,1]，最后是 [5,5]。
		cost = (3 + 2) + (4 + 1) + ( 3 + 2 + 4 + 1 )

	也就是说，我们要可以把前面的部分留给subcall来计算，我们只要计算最外围的3 + 2 + 4 + 1就可以了。

	在考虑一个例子： [3,2,4,1,5], K = 3:
		当我们选择左边为[3]，右边为[2,4,1,5]的时候，[2,4,1,5]本身并不可以被merge成1个slot。
		所以 cost = 0 + (2 + 4 + 1) + 0 + (3 + 2 + 4 + 1 + 5) (因为单个元素的cost是0)

	所以只有在当前长度可以merge为1个slot的时候，我们才就算整体的和。

	那为什么步长要设置为 K - 1呢，因为。。。要保证一边是可以merge的？
	要不然[2,4,1,5], K = 3我们选择左边为[2,4]，右边为[1,5]，两边cost和整体cost都是0，就错了。

	def mergeStones(self, stones, K):
        n = len(stones)
        if (n - 1) % (K - 1): return -1
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stones[i]

        import functools
        @functools.lru_cache(None)
        def dp(i, j):
            if j - i + 1 < K: return 0
            res = min(dp(i, mid) + dp(mid + 1, j) for mid in range(i, j, K - 1))
            if (j - i) % (K - 1) == 0:
                res += prefix[j + 1] - prefix[i]
            return res
        return dp(0, n - 1)

1002. Find Common Characters
	送分题目哈。

	不过python有简便写法，需要记一下。
	def commonChars(self, A):
        res = collections.Counter(A[0])
        for a in A:
            res &= collections.Counter(a)
        return list(res.elements())

1004. Max Consecutive Ones III
	联动LC. 487，这个用zero_count来做dictionary就刚刚好hhhh。
	核心思路仍然是cumu sum。

	我日！他妈的还是小题大做了，单个滑动就可以解决了。
	核心思路是at most K distinct。

1005. Maximize Sum Of Array After K Negations
	排序，反转K个负数。

	如果负数反转完了K还有剩且为奇数，
	sum -= 2 * min(A)

1006. Clumsy Factorial
	正常思路来说，我觉得考点是：
	先把前置的 "*" 和 "/" 计算了，然后就可以模式匹配了。

	但是大神们吓着我了，居然可以O(1).

	N - (N - 1) * (N - 2) / (N - 3)
    = N - (N * N  - 3 * N + 2) / (N - 3)
    = N - (N * N  - 3 * N) / (N - 3) + 2 / (N - 3)
    = N - N * (N - 3) / (N - 3) + 2 / (N - 3)
    = N - N + 2 / (N - 3)
    = 2 / (N - 3)
    所有只要 N > 5, 这一串的结果就是0。

1007. Minimum Domino Rotations For Equal Row
	自己写的太杂揉了，虽然效率差不多但没有可读性。

	分为几次遍历会清晰很多。

1008. Construct Binary Search Tree from Preorder Traversal
	单调栈生成next_larger可以解决，有效范围也可以。（后面这个写法挺有意思的）

	要不然就循环 + 栈。栈的话，加一个dummy node会方便很多。

1009. Complement of Base 10 Integer
	直接转进制，转码，转回来。

	特殊处理0.

1010. Pairs of Songs With Total Durations Divisible by 60
	count dict标准题目，特殊处理下余数为0的情况。

1011. Capacity To Ship Packages Within D Days
	这种二分法的应用，需要好好学习。

	验证一个max_weight可行只需要O(n)。
	如果max_weight可以，那么max_weight + positive int都可行

	二分法找最小可行weight。

1012. Numbers With Repeated Digits
	找有重复digit的数字，相当于找没有重复digit的数字。
	如何计算长度为N，且没有重复digit的数字个数？
		排列：（首位不能用0）9 * Permutation(N - 1, 9)

	然后先找长度小于len(N)的。
	然后用set来找长度等于len(N)的。

1013. Partition Array Into Three Parts With Equal Sum
	target = sum(A) // 3
	然后滑动窗口就好了。

1014. Best Sightseeing Pair
	有意思的一道题目。
	A[i] + A[j] + i - j 可以拆开变成 (A[i] + i) + (A[j] - j)
	这样子两项就无关了，只要求i < j
	直接扫描记录以前的最大值就好了。

	或者记录以前最大值，每一次扫描后减少1作为惩罚。

1016. Binary String With Substrings Representing 1 To N
	我感觉挺难想的一道题。
	不过最后发现，要不然就从用一个seen set记录出现过的。
	要不然就先构造出二进制的字符串再strstr。

1017. Convert to Base -2
	这道题是CMU的面试题。
	当时没有做出来。
	其实和转其他进制是一样的，保存余数，然后翻转。
	负进制的关键是要保证余数是正的。

1018. Binary Prefix Divisible By 5
	维护余数就好了。
	余数每次 * 2 + (1 or 0)再mod 5。

1019. Next Greater Node In Linked List
	单调栈。linked list麻烦一点的就是不知道长度。

	要么就先遍历一遍求长度。
	要么就stack里面放index和val。
	关键：每扫描一个node，ans先append一个0。

1020. Number of Enclaves
	有一道题和这个一模一样，忘记了题号。
	四周dfs变0就好了。

1021. Remove Outermost Parentheses
	记录opened
	c == '(' and opened > 0 or c == ')' and opened > 1:
		add

1024. Video Stitching
	我的思路是贪心，结果少考虑了一个情况。

	排序后，维护两个变量，reachable_end和current_end就好。
	只有一个current_end是不够的。

	看discussion，发现排序都不需要。。因为对于每一个start来说，我们只需要end最大那个。
	所以可以用hashtable来事先处理一下clips。

	还可以用DP！
	这个是真的没有想到。

	DP[i]描述要一个[0, i]的剪辑需要最少几个clips。
	DP[i] = 1 + min(DP[start] for start, end in clips if start <= i <= end)

1026. Maximum Difference Between Node and Ancestor
	直接套用模板也可以。
	bottom up 的话，就需要记录左子树和右子树分别的最大最小值。
	如果是top down的话，就简单很多。只需要记录当前path的最大最小值。
	为什么是path？因为只用考虑ancestor。
	走到None的时候就尝试更新。

1027. Longest Arithmetic Sequence
	DP[i][j]描述的是以A[i]和A[j]开始的等差序列。
	这样的话需要O(N^3)。

	要不然就DP[diff][index]描述以A[index]结尾且递增diff的长度。
	这个方法用dict写。

1028. Recover a Tree From Preorder Traversal
	个人感觉就是parse麻烦点？
	因为已经是preorder了，所以直接拿到对应深度后直接构造。

	记一下iterative的写法，感觉挺简洁的。
	自己的iterative写法一直不是很明白，stack进出需要再仔细学一下。
	这个题里，stack长度就是深度。

1029. Two City Scheduling
	先安排所有人都去第一个城市，然后贪婪选择一半人去第二个城市。

1030. Matrix Cells in Distance Order
	诶，这道easy有想法的。
	肯定都会做bfs啦。
	但其实。。可以直接用一个hashtable，用distance作为key啊。。。。

1031. Maximum Sum of Two Non-Overlapping Subarrays
	最暴力的做法就是O(N^2)。枚举一个子数组的位置，然后再枚举另一个。

	可以O(N)做出来。
	只用考虑两种情况：M在右边和M在左边。
	对于每一种情况，在右边的子数组通过扫描得到，然后再一个变量记录左边到某一个下标为止最大的子数组。

1035. Uncrossed Lines
	好题目。
	居然可以退化成LCS。完全没有想到。

1041. Robot Bounded In Circle
	emmmm。一开始想复杂了。

	很简单的hhh
	模拟一遍，结果如果 【在原点】 或者 【不在原点且方向不为上】 就可以。

1042. Flower Planting With No Adjacent
	直接模拟。贪婪。

1043. Partition Array for Maximum Sum
	貌似只能用DP做。
	O(NK)。

1044. Longest Duplicate Substring
	就是实现binary search + rolling hash!

1047. Remove All Adjacent Duplicates In String
	栈。

1048. Longest String Chain
	好题目。
	我的做法是O(N^2 * W)，和LIS一样。

	为了优化一个N，我们可以不用DP，改用一个DICT。
	dict里面记录出现过的 以 word 结尾的最长序列长度。
	这样我们只需要试试当前的word的prev在不在mem里，就可以了。
	这样做是O(NW)

1049. Last Stone Weight II
	我觉得这个是一道神题，是我需要学习的！

	抽象为：一个数字分为互斥两组，求两组的差值最小值。
	抽象过程：

	解抽象后的问题：
		一个DP记录可以生成的和。

1051. Height Checker
	我只想到了sort。

1052. Grumpy Bookstore Owner
	求得本可以满意的顾客个数和。

	然后用cumu的思想记录不满意的顾客和，然后遍历一遍找
	使用一次能力，可以获得的最大potential

1054. Distant Barcodes
	和有一道字符处理的一样的。

	记录count，用heap每次拿最多的两个操作。

1055. Shortest Way to Form String
	我的做法是index_dict + binary_search

	有四个follow up。用two pointer的做法想明白了。

	flatten indexes来优化binary_search太震撼了！！

	第四个没有看懂。。之后再说。

1056. Confusing Number
	好烦啊，写了一会儿才发现是旋转整体。不是逐位逐位旋转的。

1057. Campus Bikes
	Google的题，都是那种看着简单的。。

	一般思路就是先算出来每个人到所有自行车的距离，然后排序一下，反向排序是因为list.pop()只需要O(1)。
	维护一个size = len(workers)的min_heap
	每次取出最小的，如果人和车都可以，就记录一下

	在Discussion看到的方法，因为是manhatten distance，最大值是2000。
	所以可以利用计数排序！

1062. Longest Repeating Substring
	最长相同子字符串。
	最简单的就是二维DP，进一步观察转移方程可以优化到两个一维DP。
	这样时间是O(N^2)，空间O(N)

	更快的方法就要涉及二分法了。
	不同于subsequence验证需要O(N^2)，我们验证符合某个条件的substring一般都是O(N)
    
    又因为如果有长度为5的common substring，那一定也有1，2，3，4的。
    所以我们可以用二分法找最大长度。时间为(Nlog(N))!

    值得一提的是，普通的hash算法不是O(1)，是O(n)。
    但是因为每次我们hash的长度是固定的，所以可以近似看为O(1)。
    要实现真正的O(Nlog(N))，需要用到rolling hash。

    rolling hash涉及选择 两个 参数。一个类似于进制数，一个是取模数。

    取模数要求为质数，或者如果可以保证没有碰撞，可以用很大的随意一个数。
    进制数一般就是 number of candidate + 1。

1066. Campus Bikes II
	这个问题可以转化成房子上色，每个颜色只能用一次，求全局最低开销。
	虽然我还没有想出来这个问题的解法。。。

	貌似这种题目，没有巧妙解。。
	所以基础思路都是暴力破解，可以用backtracking，可以用priority queue

	用bit来记录状态变化

1074. Number of Submatrices That Sum to Target
	先算每一行的累计和数组。
	然后遍历 矩形的左右边界（列的pair），问题就转化成一维的了。
	整体是O(N^3)。 细节一点是O(W^2 * H)

	有一个优化，就是如果W > H，那么就把矩阵倒置了。

1078. Occurrences After Bigram
	直接遍历到倒数第三个word就好了。

1079. Letter Tile Possibilities
	就是排列嘛。

1081. Smallest Subsequence of Distinct Characters
	我记得我做过这道题。估计有重复的吧。

	先找到每个char最后出现的下标。
	然后一个单调栈就好了。不过需要pop stack的时候需要加一些条件。

	还需要一个set来记录哪些char可以用。

1088. Confusing Number II
	只有0 1 6 8 9这些数字可以用。
	可以直接用DFS一个一个验证嘛。为了节省验证时间，我们可以同时更新rotation的值。
	不过python有一个很神奇的事情，可能是因为最下面一层的计算量太大了。
	所以如果在for loop里break的话，可以节省大量时间。
	否则会TLE。

	貌似还有一种方法是算01689所有构成数字，然后删掉反转后一样的数字。

1089. Duplicate Zeros
	写得挺烦的。

	我觉得好的思路其实是，统计多少个0，然后从后往前扫描。
	算出来真正的位置，再决定填不填。

1092. Shortest Common Supersequence
	问题转化一下。

	第一步：找到LCS，并用类似edit distance的方法，记录走向。

	第二步：逆向找到路径。

	第三步：根据路径生成字符串。

	LCS可以优化到空间O(n)。 因为转移方程只涉及上面一行。

	dp = [''] * (1 + len(str2))
	for i in range(len(str1)):
		prev = ""                # 甚至不需要两行dp，prev表示DP[i - 1][j - 1]
		for j in range(1, 1 + len(str2)):
			temp = dp[j]         # 甚至不需要两行dp，temp表示DP[i - 1][j]
			if str1[i] == str2[j - 1]:
				dp[j] = prev + str1[i]
			elif len(dp[j - 1]) > len(temp):       #DP[i][j - 1] 就是 DP[j - 1]
				dp[j] = dp[j - 1]
			else:
				dp[j] = temp
		prev = temp

1093. Statistics from a Large Sample
	傻逼题目。

1095. Find in Mountain Array
	有意思的一道题目。
	结合 LC 852. Peak Index in a Mountain Array
	我们可以先找到peak index。
	然后左右跑binary search。

1102. Path With Maximum Minimum Value
	dijkstra'algorithm 经典实现。

1105. Filling Bookcase Shelves
	DP[i]描述前I个需要多少高度的书架。

1108. Defanging an IP Address
	？一行？

1109. Corporate Flight Bookings
	区间标记！
	很久没做过这样的题了。
	区间给定是[i, j]，我们就在arr[i] 加上k，在arr[j + 1] 减去k。
	这样最后的前缀和就是结果！

1110. Delete Nodes And Return Forest
	有意思的一道题。看了好久才发现只需要添加root。。。
	所以直接模版就好，但是要更新left和right。

1114. Print in Order
	最基础的lock。

	要避免busy waiting嗷！
	python的lock： from threading import Lock

1122. Relative Sort Array
	桶排序arr2的元素，剩下的再常规排一次。

	或者整体自定义key的方法，因为范围是[0, 1000]
	所以不在arr2的元素 + 1001
	在arr2的元素放回对应的index

1123. Lowest Common Ancestor of Deepest Leaves
	LEE大神的标准树解法就可以了。

	日常膜拜！

1124. Longest Well-Performing Interval
	
	提炼出来，就是[1, -1, -1, 1, 1]找longest subarray sum > 0

	因为这道题是特殊情况，整个cumu_sum是连续的，所以我们不需要用专题里的方法。

	拿到一个cumu，只需要看cumu - 1出现过没有就可以了。

1128. Number of Equivalent Domino Pairs
	直接搜索是 N ^ 2，所以用哈希表优化到 O(N)。
	因为数字在范围[1, 9]，所以可以直接用 10 * a + b 来快速计算key。

1130. Minimum Cost Tree From Leaf Values
	Matlab高频题目。

	我的想法类似用max binary tree做。耗时O(nlog(n))。

	仔细思考一下，[a,b,c] where a > b and c > b
	我们肯定选择 b * min(a, c)
	用单调栈可以解决！

1138. Alphabet Board Path
	用一个hashtable记录一下二维的位置。
	然后特殊处理一下'z'的情况就好了。

1140. Stone Game II
	这种游戏的题目是真的有意思。

	想不清楚就真的比较麻烦。
	还是min max的互动。
	return cumus[start] - min(helper(start + j, max(M, j)) for j in range(1, 2 * M + 1))

1143. Longest Common Subsequence
	和edit distine几乎一样的dp写法。

	DP[i][j]描述text1[0:i]和text2[0:j]的最长子序列。

	转移方程:
	DP[i][j] = DP[i - 1][j - 1] if text1[i - 1] == text2[j - 1] else max(DP[i - 1][j], DP[i][j - 1])

1144. Decrease Elements To Make Array Zigzag
	奇数次做一次，偶数次做一次。
	反正也是O(N)。在首尾加上一个float("inf")可以少写很多if。

1147. Longest Chunked Palindrome Decomposition
	贪心就可以做了。一般的字符串匹配做法是O(N * len(string))。
	如果实现一下rolling hash，可以降低到O(N)。

1150. Check If a Number Is Majority Element in a Sorted Array
	直接判断中间值是不是target是不行的，因为没有假设 这个数组一定有mjority
	因为是排序过的，所以肯定可以二分法找上下限.

1153. String Transforms Into Another String
	看着挺难的，其实仔细分析下来，就是找图里有没有cycle。
	因为可以替换成任意小写字母，所以只需要考虑特殊情况就是所有小写字母都被使用了。
	如果这个时候整个图是一个cycle，那么就不行。如果部分图是一个cycle，我们可以删掉一些节点。
	比如 a->c; b->c，那么我们可以先把b转成a，这样b就没有被使用了。

	还有更简单的做法！！
	直接查是否source和target都使用了26个字母！！
	因为我们上面说的特殊情况的部分图是cycle，意味着target一定没有使用全部字母！

1162. As Far from Land as Possible
	就是一个BFS。关键点就是 用一堆点开始BFS。

1163. Last Substring in Lexicographical Order
	我是模式匹配做的。
	维护一个answer和candidate，candidate < answer，在处理当前字符前。
	如果当前字符 c > answer[0]，那么answer = c，candidate = ""
	如果当前字符 c < answer[0], 那么answer += c, candidate根据 answer[len(candidate)] 和 c进行改变。
	如果当前字符 c = answer[0]，和上面差不多，但是candidate的变化规则有一个很特殊的点。
	if answer[len(candidate)] == c:
		candidate = c if len(candidate) == 0 or candidate[-1] < c else candidate + c
	比如：
	caca
    ca
    如果下一次又是字符c，那么answer = cacac, candidate有可能是 cac 或者 c，我们可以推理出 c是绝对优于 cac的。
    因为如果再下一次字符大于a，那么answer会变成cd，如果小于等于a，candidate会被清空或者是ca。          

1167. Minimum Cost to Connect Sticks
	肯定从小的粘起。
	分析：
		为了得到1个，当前范围内的所有sticks都会被粘，所以sum(sticks)
		但是有的值会被使用多次，那么肯定用小的值。

1169. Invalid Transactions
	貌似直接暴力N^2也可以实现。
	不过肯定可以优化嘛。
	我们按照时间排序后，就可以优化搜索的部分。可以用类似 循环数组 的方法，及时地删除过老的数据来保证搜索空间够小。

1170. Compare Strings by Frequency of the Smallest Character
	估计考点就是一个 累积和数组 吧。
	先把words全部转化了，然后统计频率，然后再造累积和数组。

	之后的每个查询就只需要O(1)了。


1177. Can Make Palindrome from Substring
	没啥更好的做法了，前缀和优化一下。

	我们只需要知道奇数次的个数 M，判断 M // 2 <= K就好了。

	再仔细想想，因为我们只关心奇偶性，并且只有小写字母。所以可以状态压缩到一个int里。
	这样就快很多了。

1181. Before and After Puzzle
	python处理字符串还是简单。
	可能用defaultdict记录<word, set(index)>优秀一些。

1184. Distance Between Bus Stops
	直接求和，然后求一部分的和。比较两个值谁更小。

1185. Day of the Week
	直接算嘛。闰年的公式还挺麻烦的。。。

	python可以！
	datetime.datetime(year, month, day).weekday()

	这东西居然还有专业公式？！！！
	我服了。

	Zelle congruence.

1186. Maximum Subarray Sum with One Deletion
	就是kadane algorithm的进阶版。

	维护两个变量，unmodified和modified

	转移方程是
	modified, unmodified = max(unmodified, modified + n), max(0, unmodified) + n

1187. Make Array Strictly Increasing
	和LIS挺像的。
	DP[i][j]描述arr1的前i位，以数字j结尾，需要的最少operation。

	优化一下，我们把key和value颠倒一下。
	类似LIS的最佳candidate做法。
	整体runtime是 N^2 * log(N)

1188. Design Bounded Blocking Queue
	Semaphore.

	python的semaphore怎么写的呢？
	from threading import Semaphore

1189. Maximum Number of Balloons
	统计一下就好了。

1190. Reverse Substrings Between Each Pair of Parentheses
	就是计算器。

	可以用recursion做，也可以用stack做。

1191. K-Concatenation Maximum Sum
	这道题有点意思。kadane algorithm变种可以做。

	因为只有三个情况：
	最大值出现在boundary内
	最大值出现在跨boundary。
	最大值出现在整个序列。

	所以可以求最大前序和，最大后续和。
	有一个优化，最大后续和可以用 和 - 最小前序和。
	而最大子数组和，也可以用 当前和 - 当前最小前序和。

	所以只需要一次遍历。

1200. Minimum Absolute Difference
	就是排序，找差值。

1201. Ugly Number III
	回忆一下数学的东西。
	GCD(A, B) * LCM(A, B) = A * B

	使用inclusion exclusion原则：
	被A整除的 + 被B整除的 - 被LCM(A, B)整除的 = 一定范围内 ugly number 的个数。

	拓展到ABC也是一样的。

	然后就可以用二分法了，值得注意的是，当 number(mid) == n的时候，不能直接返回。
	因为有可能它之前的数字的范围也是一样的个数。

1207. Unique Number of Occurrences
	哈哈哈。

1208. Get Equal Substrings Within Budget
	滑动窗口解决。

1216. Valid Palindrome III
	花里胡哨，直接二维DP解决。

	仔细想想，就是求longest plaindromic subsequence的长度。

1219. Path with Maximum Gold
	其实这道题挺简单的，因为数据的量很小。
	直接每个点dfs + backtracking也可以过，虽然挺慢的。

	那么优化呢？
	我的想法是，起点一定不可能是有三个或者四个valid neighbor的点。这一个优化就已经很快了。

	还有一个优化也是不难想的，就是在当前max_path上的点，一定不是更大path上的起点。所以就不需要从这些点跑dfs了。

	关键！这两个优化，是不能同时用的！！太神奇了。

1223. Dice Roll Simulation
	好题目。
	我的DP，真的慢。哈哈哈哈哈哈哈哈
	因为只要求连续的个数嘛，所以我的DP[i][j]描述的是 以 i 结尾，连续j个 的valid sequence个数。
	然后就递推就好了。

	有一个快炒鸡多的做法。
	DP[i][j]描述 长度为 i，结尾是j 的valid sequence个数。
	这样做的好处，是我们可以快速算出来
	if i - rollMax[j] > 0:
		invalid = DP[i - rollMax[j] - 1][6] - DP[i - rollMax[j] - 1][j]
		DP[i][j] -= invalid
	在干什么？总长度是 i，然后允许连续长度是rollMax[j]，那么只要最后 rollMax[j] + 1个都是 j，就不合法了。


1227. Airplane Seat Assignment Probability
	return 0.5

	哈哈哈哈哈哈哈。
	可以推出递推公式后用induction证明。

	也可以换个方法理解。第一个人上来如果没选到自己位置，那么之后的人就把他起来，重新选。
	所以当最后一个人上来的时候，第一个人要么在自己位置，要么在他的位置。1/2

1236. Web Crawler
	就是一个bfs或者dfs。

1238. Circular Permutation in Binary Representation
	这道题可以直接用iterative做。

	但是有一个知识点 【grey code】。
	https://cp-algorithms.com/algebra/gray-code.html
	这个 code 就保证了 相邻的只有一个bit不一样。

	G(n): return n ^ (n >> 1)

	但是这道题还要求了需要从 start 这个数 开始。
	所以用G(n) ^ start就好了。

1239. Maximum Length of a Concatenated String with Unique Characters
	挺有意思的一道题。
	把每一个string转成bit信息，然后用 & 来判断有没有重复的character。

	用DP来遍历所有可能的组合。

1245. Tree Diameter
	哇。这道题完全说明。我本科没学好嘛。。。
	有标准做法。两次BFS就可以。
	第一次BFS选择随机点，然后拿到最远的点u。
	第二次BFS从点u跑，拿到最远的点v。
	distance(u, v)就是longest path。

	这个算法的核心证明在：证明第一次BFS拿到的最远点一定是最后答案的一边。

1249. Minimum Remove to Make Valid Parentheses
	扫描两遍就很简单了。找invalid的括号。

1256. Encode Number
	?什么题目。
	没想到直接 bin(n + 1)[3:] 就好了。。
	我只发现了长度的规律，然后数字去减。。

1257. Smallest Common Region
	就是lowest common ancestor。
	因为有这么一个限制:
	"If you are given regions r1, r2 and r3 such that r1 includes r3,
	 it is guaranteed there is no r2 such that r2 includes r3"
	所以一定是一棵树。

	然后就简单了嘛。因为没有root，就从下往上找，找两个的path，一个转为hashset。
	用另一个查就好了。

1258. Synonymous Sentences
	DFS或者BFS就好了。
	更关键的我认为在如果构造bags of synonyms。
	肯定是用union find来做的。不过我没有想到可以 parent[s] 就是 s。
	我额外引入了一个bag_id, 相当于两层的所属关系。

1260. Shift 2D Grid
	哇，这道题。
	一开始没有考虑O(1)空间实现，挺简单的。
	O(1)空间就麻烦多了。。。
	需要的思考就多起来了。

	k 和 M*N 互质的话，就只需要从任意点跑一次。
	否则需要从 gcd(k, M*N) 这些点都跑一次。

1262. Greatest Sum Divisible by Three
	没想到用DP，还是知识点有漏洞。

	DP[i]描述 余数是i 的和的最大值。

	我自己的方法其实更快hhhh。
	因为 sum(nums) % 3 只有三个情况，如果余数是0，直接返回。
	如果余数是1，我们可以 减去最小的余数是1的值，或者减去两个最小的余数是2的值。
	如果余数是2，我们可以 减去最小的余数是2的值，或者减去两个最小的余数是1的值。

1266. Minimum Time Visiting All Points
	贪心着做就好了。尽可能走对角线。
	最后发现其实只需要走max(x, y)。

1267. Count Servers that Communicate
	我一开始还想着造图然后dfs呢。hhhhh

	做法挺多的。
	我们先把一行有多个的都统计了。然后在这之中记录一下每一列的个数。
	最后再看处理一行只有一个的，只要他们在的列有多个，那么也统计进来，

	也可以统计行数，统计列数，只要row[x] + col[y] > 2，就一定可以交流。

1268. Search Suggestions System
	LC. 642的弱化版本，就不需要那么多的优化了。

	我就直接用bfs过滤就好了。唯一一个优化就是，第一层先选了再排序，不要排序了再选。

1278. Palindrome Partitioning III
	挺好的一道题目。 和 LC.131 挺像的。

	我一开始觉得用DP就可以了。

	DP[i][j] 描述: 在 substring[:i] 分割成 j 个回文，最少需要替换几个字符。
	转移方程：
		DP[i][j] = cost(k, i - 1) + DP[k][j - 1] for k in range(i)

	这个样子的话，整体的时间是O(N^2*K*N)，因为cost函数是O(N)。
	也能过，但是太慢了。

	核心优化，cost函数我们可以提前算好，而且可以再用一个DP优化计算。
	DP2[i][j] 描述: 让 substring[i:j + 1] 成为回文，需要替换几个字符。
	转移方程：
		DP2[i][j] = DP2[i + 1][j - 1] + (s[i] != s[j])
		DP2[i][i] = 0
		DP2[i][i + 1] = s[i] != s[i + 1]

	这个样子，我们可以在O(N^2)算出来所有的cost结果。

	然后上面的DP就可以优化到O(N^2K)。
	然后就是细节优化了，遍历的范围可以缩小一些。
	比如 left 的范围就是 range(num_substring - 1, right)
		 num_substring 的范围就是 range(2, min(k, right) + 1)

	解法2：
		核心还是用O(N^2)算出来所有的cost。
		然后我们不用DP，用和LC.130类似的backtracking做也是可以的。（其实就是 top-down DP）

1315. Sum of Nodes with Even-Valued Grandparent
	？脑筋急转弯？

1328. Break a Palindrome
	emmm。脑瓜测试。。。

1332. Remove Palindromic Subsequences
	脑瓜测试。。。。
	不过如果alphabetSet是[a-z]，就麻烦很多了。

98. Validate BST
	见整理笔记。

366. Group Leaves of BT
	就是算height，然后分类一下。

560. Subarray Sum Equal K
	滑动窗口是不行的，因为可以这个数组可以包含0和负数。

	最简单的肯定还是O(N^2)搜索。

	另一种方法，考虑cumulative sum.
	sub_array_sum(i, j) = cumu_sum(j) - cumu_sum(i) = K
	cumu_sum(j) = cumu_sum(i) + K

	换句话说，找并记录所有的cumu_sum.
	如果这个cumu_sum - K被记录过，代表我们找到了一个sub_array_sum = K

	当然，还得记录每一个cumu_sum出现的次数，因为找到一个被记录的cumu_sum - K，可能代表找到多个子数组。

	记得加入(0, 1)

523. Subarray Sum Equal n*K
	考虑cumulative sum.

	如何判断subarray等于n*K，当两个cumulative sum同余的时候。

	如何保证size >= 2,hashmap里面存上(mod, index).

812. Largest Triangle Area
	数学题目。
	遍历就好了。
	给定三点求三角形面积：
	Shoelace formula
	A = 0.5 * |x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3|

973. K Closest Points to Origin
	
	quick select方法。
	因为quick select有部分排序。平均可以优化为O(n)。

1025. Divisor Game
	直接返回 N % 2 == 0。

	证明一下吧：

	一个奇数的因数也只能是奇数。（因为偶数乘奇偶都会是偶数。）

	所以拿到奇数的人一定会返给对手一个大于零的偶数。

	偶数永远可以选择1，来返给对手一个奇数。

	奇数的base case：1 --> 输。

	所以只要alice开头拿到偶数，一定赢。因为每次轮到她还是偶数。