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

20200614 LC206/400by200705计划第19天 地里发帖第15天
今日完成3题 /leetcode 78, 90, 77

连续打卡第二天

刷题6题      +2米  

总结： +1米
1. 数组题大多会想到双指针算法
2. 同向双指针用得很广
3. 核心考察点：时间复杂度。


ps: 昨天刷的6道题啊，+2米？但只获得了1米:(

谢谢

打卡第5天
主要还是dp类型的题 今天3题983 Minimum cost for tickest
123 Best time to buy and sell stockⅢ
Lintcode Paint house Ⅱ

第11天，主要的突破是one pass和two pass之间的转换。
需要注意到是变量的命名，比如n和k，不要用混了。很难debug。

打卡 13 天
1. Cheapest Flights Within K Stops: DFS, BFS, DP: dp[k][citiy]: min cost from src to v with up to k flights
2. Unique Paths: cur[j] = pre[j] + cur[j-1], swap(pre, cur)
3. Climbing Stairs: pre = 1, cur = 1, for 2 to n : sum = pre+cur, pre = cur, cur = sum

06/14 第十三天 继续继续 今天三道

最长公共前缀 这道题时间复杂度要求较高 采用两个指针比较 从下标0处开始比较，判断两字符串的下标0，是否全部相同。遇到不全相同的下标。时间性能为O(n*m）
重新排列日志文件 将日志的标识和内容换位，Arrays.sort 排完序，再还原标识符和内容位置
检查平衡性 第归检查 根 左右子树

Day 9
3 problems today
The one about binary searching a tree is interesting.

菜鸡第十五天

今天看了看double pointer
1. Container with most water: 这个隐约记得有做过，两个指针向中间移，每次算一下面积。如果左边value比右边低，就移左边pointer，
    因为虽然底面积-1但有可能高更大了；右边value低就移右边的，直到两个pointer相遇
2. Implement strStr()：这个感觉就brute force做的，在每个haystack的index里loop needle，如果两边不相等就break开始下一个haystack index，
    如果needle loop完了就说明找到match而且是从i开始的，return此时的haystack index i。还可以用kmp做但没太看懂，明天再研究一下
3. Find the duplicate number: 看了答案，和linked list cycle很像，使用index->array[index]来构造一个linked list，然后就根据linked list cycle
    用slow fast pointer走两次找beginning of cycle。有一点没太搞懂的是，如果index-array里面有cycle， ex. arr[1] = 2, arr[2] = 1, linked list怎么办？
    看了comment好像有人说不会影响，但感觉还是要想一想

明天希望可以多看几道题，这两天应该看看bfs dfs之类的了

打卡第14天

Jun 14 七题 KMP！！！
787. Cheapest Flights Within K Stops, Dijkstra… trick在于使用priorityQueue后，遇到city==dst后直接返回即可，因为保证了是cheapest。
628. Maximum Product of Three Numbers，只有两种情况，最左*2*最右 vs 最右*3；
214. Shortest Palindrome, 可以转变为找出start index为0的最长回文子串，KMP算法；关键在于table的获取，注意不匹配的时候不需要直接跳回到0，可以跳到table[i-1], 因为table记录了之前匹配成功的位置！
797. All Paths From Source to Target, DFS寻找路径，回溯。前提是DAG；题解有map记录memorization，helper方法有arraylist返回值。
1047. Remove All Adjacent Duplicates In String, 每遇到两个重复字符就移除，pair这种思想—>stack！
404. Sum of Left Leaves, recursive可以引入一个参数isLeft，或者全局变量sum。