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

Jun 12
65. Valid Number, 注意三个变量digitSeen, eSeen, pointSeen; DFA也可解；
689. Maximum Sum of 3 Non-Overlapping Subarrays, 1. DP 既要维护sum，也要维护index; 2. 利用两个left，right数组【会用到DP思想】，因为三段都有index范围，对第二段可能值进行遍历，找出最大值；
158. Read N Characters Given Read4 II, follow-up from 157. 注意点在于一个read4可能会被分开加入buf，所以需要维护一个指针指向当前读到的位置；if(curPtr>=len) curPtr=0; 读到末尾，ptr置为0；
287. Find the Duplicate Number, tortoise and hare 与 linkedlist cycle相同，找到环的起点，数学推导；

连续第 9 天打卡，完成 5 道 String, Design 题：(4.5/5)
1. String to Integer (atoi)
2. Reverse Integer
3. Roman to Integer
4. Integer to Roman
5. Insert Delete GetRandom O(1)

Tips 总结：
1. String, Math 题目有很多 edge cases 要处理，思路较为简单要有信心做得出来，但是要仔细一些；
2. String to Integer 类型题目一般用一个 pointer 去遍历 string，然后根据题目要求将 res 构造出来，很多 if-else 罢了；
3. Integer to String 类题目乍看之下较难处理，但其实本质上是相同的，一般用 // 和 % 去“遍历” integer， 然后将 res 构造出来，注意这里的 res 首先是一个 list，返回的时候 join 成 所需 string 罢了；
4. 最后一道 design 题目做出来了还是蛮值得开心的 lol；

6.12 day 14
863 medium 有了大致思路但没想到怎么实践，其实利用hashmap建立子父关系就可以了，还是需要多刷题积累经验
855 medium 其实就是简单的模拟，但自己想复杂了，以为还有更优解法
839 hard n^2的模拟+并查集能过test case，但还有更快的bfs dfs解法，需要都敲一遍学习思路

Day1

复习了 下 DFS/backTracking/Tree

今天刷了6道Backtrack

Day 9

SQL 6道题

总共第九天，题目没啥难度，就只能训练口语了。

Day8:
#142. Linked List Cycle II: 双指针+公式推导
#416. Partition Equal Subset Sum ：一维DP
#494. Target Sum：这个medium二维DP也太难了。。

2020-6-12

打卡第13天（求加米从第5天开始到第13天的，楼主辛苦了）


207. Course Schedule：topological sort的应用，先建一个adjacency list，然后用两个set，一个代表这个点已经扫过并且没有环，一个代表本次扫描里visited status，然后从每个点dfs，如果碰上有visited就是有环。

217. Contains Duplicate：一边扫描数组元素一边往set里加，直到set.add返回false说明里面有duplicate。

226. Invert Binary Tree：recursive bottom-up或者iterative top-down都可以invert binary tree。

295. Find Median From Data Stream：建一个min heap一个max heap，确保min heap最多比max heap多一个，每来一个新元素，offer进min heap，如果min heap比max heap多两个元素，从min heap里poll一个最小的元素offer进max heap里。findMedian返回min heap poll的最小元素，如果min heap size比max heap大1；如果两者相等，从min heap和max heap里各poll一个，返回平均值。

300. Longest Increasing Subsequence：dp经典题，dp数字里记录当下结尾的longest increasing Subsequence的length，如果原始数组里的元素小于当下元素，那个位置的length+1就是当下位置dp数组里的值，需要注意的是每一个位置都要扫描所有之前的位置然后取最大的length存在dp数组里。

322. Coin Change：这道题开始以为是dfs，但是tle了，反应过来是dp后豁然开朗，dp数组存当下coin change的最小coin数，当下dp数组的值可以从current index-coin面值的index的dp值+1得来，要把每个coin面值都考虑一边，取最小值就是当下dp的值。

Day5, Database Questions, 共3題