7月缺米的来刷题/Mock interview活动

7/8 今天比较惭愧，就做了两道题，明天补多几个
350 卡了很久，就边界条件有点坑，而且想不出很有效率的解法，但这题蛮好的，讨论里用 HashMap 我咋就没想到呢（拳头硬了）
326 这道还行，数学题。

7/8/2020 Binary Search

1283 Find the smallest divisor given a threshold
用0 到list的最大值来做binary search, 如果大于threshold就要增大divisor。

222. count complete tree nodes
分别对左右的树查看是perfect complete还是还是complete, 递归

240 search a 2d matrix ii
从右上到左下search

34 find first and last position of element in sorted array
二分法的lower bound 和 upper bound

33. search in rotated sorted array
查看是在左还是右，是rotate的还是不是rotate

SQL
1212  Team scores in football tournament
这里我是用了分别求客场和主场。但是可以用or 在join的时候，把condition放到select部分

1270 all people report to the given manager
这里就是用多几层subquery

180 consecutive number
用lag 和 lead

Day3 - 7/8 DP分类4道 DP好难，挑简单的练练先

Jun 8 打卡第7天，
720. Longest Word in Dictionary, sort + hashset；也可以用trie + dfs ／bfs；
724. Find Pivot Index, 可以直接用sum和leftsum作为两个变量，更加清晰；
931. Minimum Falling Path Sum, 路径问题经典DP。
168. Excel Sheet Column Title, 类似于base10-base2；注意0-index和1-index；
1011. Capacity To Ship Packages Within D Days, 注意left是max，每天的货物需要在一天运完！

7.8 打卡

Rotate List       
4Sum
3Sum Closest

今天做了Subsets II, Permutations II, Combinations，这几道题都是backtracking，但是有重复元素时可能需要注意下。子集有重复时，需要先给nums排序，然后如果前面的相同元素不考虑，那么后面那个和它相同的元素也不考虑。全排列有重复时，可以先用map存下每个元素出现的次数，然后backtrack注意更新次数。组合C(n, k)用backtrack可以解决，但是可以优化，还没看完这部分。

7.8 zszszszszszszszszszszszsz

菜鸡七月第九天

1. 3 Sum: 之前学过但已经忘了（叹气， 先loop 0到nums.length - 2， 然后每次当成一个two sum来做，先sort array，
    注意每次要skip duplicates，每次不管sum是多少都可以看看两个pointer有没有可以跳过的部分
2. permutations II：用的backtracking，可以用一个Boolean array来标记有没有重复，如果有用过或者标记重复就跳过，
    不然的话先加到list里面再backtrack再减掉，记得把Boolean改成相应的值
3. next permutation：总的来说先从右向左找到非decreasing的index，找到以后再找比nums[index]大的对应坐标swap，
    剩下的就说明没有办法swap并且是decreasing，可以直接reverse
4. permutation sequence：有n个数想找第k个permutation，每次可以确定最高位，ex. 第一位之后又(n-1)!个permutation，
    第k个可以通过k/(n-1)!来确定，第二位同理
5. last stone weight: 可以用priority queue，把所有的element都加进去之后开始poll，如果一大一小就把两数之差重新放进去，
    最后看priority queue是不是空的，不为空的话就poll一个，空的话就说明都cancel掉了

Array + DP
DP的题感觉还是有点难，得需要先做比较简单的题，有点思路之后才能做稍微难一点的题...
慢慢来，鼓励自己...

0708 Day8 打卡四题

3Sum，2sum的拓展，使用Two pointer或是HashSet均可，注意为了避免重复在使用hashset是要对3-tuple编码，使用3-tuple的最大值与最小值组合可以唯一确定一组tuple
Split Array Largest Sum，Binary Search，可能的解的取值范围在[min{nums}, sum{nums}]之间，复杂度为O(n log k)，k为解空间长度。DP复杂度高，为O(n^2 m)
Interleaving String，DP，通过剩余字串长度确定子问题
Median of Two Sorted Arrays，Binary Search，注意到merged array的前k个元素是由m1个nums1的元素，k-m1个nums2的元素组成，给定一个k可以通过binary search确定m1，于是我们可以设k=len(num1)+len(num2)/2。注意edge cases：m1==0，m2==0，m1==len(nums1), m2==len(nums2)。