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

打卡第14天，加米加米！～坚持就是胜利！

06.25.2020 刷题第十四天 打卡十四天（共四道题）

1. longest substring with at most K distinct element;

Mindset: use a sliding window to maintain a size k ds
use a int variable to keep record the maximum length which ends with index i;

2. Binary Watch

Mindset:
DFS with back tracking.
combining with permutation

3. Strobogrammtic number
Mindset:
use a hashmap to store the possible matched pair
then use two pointers to find the result;

4. MySQL
Mindset: use "select and from" to combine two tables

day23
三道binary search 今天又是忙碌的一天，binary search 估计周日都要再重新做一波。。

day 25

lc new 6 review10+ mock
405. Convert a Number to Hexadecimal
四个bit一换
3Sum系列都可以用双指针
16. 3Sum Closest
找到最小的diff，

259. 3Sum Smaller

708. Insert into a Sorted Circular Linked List
考虑四个情况
case 1 : insert within the list
case 2 : insert after the tail node, if the value of new node is the max or mini of the current list
case 3: the list contains uniform value, the entire list has only one single unique value
case 4: we have an empty list

25. Reverse Nodes in k-Group
cnt数到k，call 一次 reverse（），注意传入的头尾是不颠倒的部分，只是作为连接的reference

865. Smallest Subtree with all the Deepest Nodes
bottomup 返回最深的深度和该子树的符合条件的节点

mock题目是regular expression matching 真是太晕了 多练

day 24

lc new 6 review 10+
154. Find Minimum in Rotated Sorted Array II
考虑三个case，如果pivot和hi相等，左移hi一步

166. Fraction to Recurring Decimal
考虑overflow，转成long，用map来检查循环

388. Longest Absolute File Path
用\t 来区分substring， 当遇到带“.“的substring更新max

540. Single Element in a Sorted Array
只在even index检查

408. Valid Word Abbreviation
双指针

1373. Maximum Sum BST in Binary Tree
postorder 返回 上下界和sum

06/25/2020, DAY 20
今天刷了3道题。

20200625:
3: 0129, 0716, 1042
4: 0287, 1152
5: 1203

2020年6月25日，第二十四天发帖。今天刷了7道题。

前三题是整理链表题：
19. Remove Nth Node From End of List。维持一组间隔为N + 1的快慢指针。
86. Partition List。用三个指针（curr，prev，smallListTail），curr为循环当前访问节点，prev为前一访问的节点，smallListTail则永远指向小于x的最后一个节点。一旦curr的值小于x，通过三个指针可以将这个节点挪到smallListTail后面。
142. Linked List Cycle II。这道题如果要用空间O(1)的解法需要知道龟兔赛跑算法。
743. Network Delay Time。这道题为了复习Dijkstra，同时作为今日份图论题。
28. Implement strStr()。这道题为了复习KMP，同时作为今日份dp题。
856. Score of Parentheses。今日份stack，这道题自己用了办法是：想象自己在爬山，如果遇到左括号就高度+1，右括号则高度-1，以此把这个字符串分割成若干独立的括号字符串，使每个字符串代表“一座”完整的山（而不是好多山从高度为0的地方挨在一起），然后用递归计算每座“山”内层的分数*2，把每座山的得分相加。这样的最坏时间复杂度是O(N^2)。那个优化的O(1)空间算法真的神了。
389. Find the Difference。今日份位运算题：把每个s，t中的字母转化成不同位上的掩码，一直做异或操作后，把最后得到的掩码反过来转化为字符。

总结一下：
0.今天总结了一部分链表题，至少是自己做过的部分，同时复习了Dijkstra和KMP算法。
1.如果节点集可以用有限个连续的int来表示，可以用Integer array存储距离信息（初始化为null 或者Integer.MAX_VALUE）；
2.链表题的骚操作非常多，但是总结起来也就那么些花样：三个指针iterate反转，快慢指针找结尾N的位置或者中点，龟兔赛跑找环，还有copy节点操作最骚的138题。这些题本质上都是：在一个集合中，每次只知道一个位置的元素，解决一些集合相关的问题。

action item：
0.明天学习算法：SegmentTree
1.明天复习算法：Trie
2.明天总结题目：二叉树系列

打卡第十一天刷了3个题（昨天太晚了睡觉忘了发）
（版主前十天都没加米，第一天在1053楼，第二天在1111楼，第三天在1166，第四天1234，第五天1286，第六天1327，第七天1385，第八天1425， 第九天1472，第十天1531，求加米！！QAQ）

Day 13 06/25: 六道题