缺大米的请参加这个刷题/Mock interview活动

6.2开始，今天第15天

Day2:
今天上班不开心，一个bug总也修不好，虽然tester很帮忙了。因为想让自己开心一点，奖励自己几道easy和median的题，大约12题左右，都是在Amazon的tag下的，大部分是tree相关。都不难。

希望在virtual onsite前把这四百多道题都刷一遍吧。

Day 10:
#987. Vertical Order Traversal of a Binary Tree: 先先序遍历二叉树，给所有节点(x,y,val)坐标，接着根据坐标进行排序
#269. Alien Dictionary：graph, 首先遍历每个string以及它的相邻string构造图（graph(map<char,set<char>>),indegree(map<char,int>)，接着找到所有link为0的节点放入队列，调用bfs
#1192. Critical Connections in a Network: 这个hard好难。。。Tarjan's algorithm

Day 15, 三道新题：

Split Array Largest Sum        LC 410
Divide Chocolate        LC 1231
Best Sightseeing Pair        LC 1014

1. dp / 二分答案。二分答案的思路跟LC 1011挺像的，比较不直观，但实际上是一样的。二分最大子数组和，如果找到一个子数组和x，可以找到一种分法满足所有子数组和 <= x，那么所有y > x都可以被满足，换言之，可以被二分掉。用子数组个数 (相当于天数)跟既定的m比较，mid相当于capacity，写法都是一样的

2. 二分答案。LC410是求minmax，这道题是求maxmin。如果找到一个x，满足切成K+1块后最小甜度 >= x，那么所有y < x都可以被ignore，据此二分。用get_pieces_by(mid)和K + 1比较，如果 < K + 1，说明mid要进一步降低，end = mid; else: start = mid

3. 观察目标函数A[i] + A[j] + i - j => (A[i] + i) + (A[j] - j)，对于每个j来讲，A[j] - j是固定的，所以只需最大化A[i] + i。max(A[i] + i)在j遍历时同时维护即可

2020-6-16

打卡第17天，今天刷了6道新题，3道旧题。

上周有点事情没能刷题，这周继续今天的四题是bfs，dfs相关的

day2 0616 3道
Valid Palindrome
Valid Palindrome II
Generate Parentheses  
还是联系递归的coding思路 谢谢楼主！

Jun 16 打卡第16天，6道题
468. Validate IP Address, 字符串题目；题解中trick：验证IPv6，转换成Uppercase，then Character.digit(s.charAt(p), 16)==-1…
395. Longest Substring with At Least K Repeating Characters, 第一眼类似于340，可以针对出现26种不同字符进行遍历，two-pointers；还可以用递归思想，找出出现次数小于k的作为split point； 340题解出现维护字符的last occurrence，然后不用遍历到count符合条件，可以直接跳转；用的是TreeMap，也可以用LRU；
1244. Design A Leaderboard, map, 期间可以计算top k，除了pq外，可以用map+treeset；
422. Valid Word Square, 可以写简便一点，不一定需要建立char数组，直接对每一列比较即可；
658. Find K Closest Elements, 找到一段绝对值差最小，直接对左右两个端点进行操作，r-l>=k，并且直接保证顺序！
292. Nim Game, B取走后A就会出现九种情况，可以发现n-4出现在任意的三类中，所以只要出现4，A就赢不了。

打卡第十天
98, 530, 700

打卡第15天， 刷了3道题

9. Palindrome Number
偷懒把int转换为string，然后判断是否Palindrome

76. Minimum Window Substring
用hash table 存t中字符使用情况，用双指针对s进行扫描，并用counter记录当前扫的字符串是否包含了t，每当有t中的字符就对hash table和counter进行更新。

109. Convert Sorted List to Binary Search Tree
用双指针找出中间的节点，记得把中间节点之前的节点的next变成None。 以中间节点的值创建个TreeNode， node.left 指向前半段list产生的TreeNode，node. node.right指向后半段list产生的TreeNode。