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

day 27

lc new 6 review 10+
338. Counting Bits
dp, dp[i] = dp[i>>1] + i%2

1027. Longest Arithmetic Sequence
Map<diff, cnt>[] dp

1216. Valid Palindrome III
dp[i][j] 是要remove的使之valid的char的个数


742. Closest Leaf in a Binary Tree
target就是叶子结点那么就是它自己，零距离

328. Odd Even Linked List
用四个pointer建立odd和even两个list 再连起来

995. Minimum Number of K Consecutive Bit Flips
还没懂。。。

Possible Bipartition   2 minutes ago
AcceptedjavaPossible Bipartition   8 minutes ago
AcceptedjavaPossible Bipartition   34 minutes ago
Wrong AnswerjavaPossible Bipartition   34 minutes ago
AcceptedjavaPossible Bipartition   35 minutes ago
AcceptedjavaLongest Absolute File Path   1 hour, 39 minutes ago
AcceptedjavaSingle Element in a Sorted Array   1 hour, 48 minutes ago
AcceptedjavaFraction to Recurring Decimal   1 hour, 53 minutes ago
AcceptedjavaFraction to Recurring Decimal   2 hours, 21 minutes ago
AcceptedjavaFind Minimum in Rotated Sorted Array II   2 hours, 33 minutes ago
Wrong AnswerjavaFind Minimum in Rotated Sorted Array II   2 hours, 39 minutes ago
AcceptedjavaFraction to Recurring Decimal   3 hours, 22 minutes ago
AcceptedjavaFind Minimum in Rotated Sorted Array II   3 hours, 24 minutes ago
AcceptedjavaMinimum Area Rectangle II   3 hours, 45 minutes ago
AcceptedjavaMax Consecutive Ones III   4 hours, 3 minutes ago
Wrong AnswerjavaMax Consecutive Ones III   4 hours, 4 minutes ago
AcceptedjavaMax Consecutive Ones III   4 hours, 6 minutes ago
AcceptedjavaRectangle Area   4 hours, 21 minutes ago
AcceptedjavaFind Largest Value in Each Tree Row   4 hours, 31 minutes ago
AcceptedjavaMinimum Area Rectangle II   4 hours, 36 minutes ago

day25
3道题！
binary search

Day 8:
System design:
Google crawler system:
Algorithm:
https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/submissions/
https://www.careercup.com/question?id=5103530547347456
word break 2

2020年6月27日，第二十五天发帖。昨天因为被想去的公司拒了，面试了快一个半月了找不到工作，心态崩了，所以中断了一天。楼主加米加到这里时请注意这一天gap。

今天主要去做了一个take home project，所以只刷了3道题。全都是google tag：

1320. Minimum Distance to Type a Word Using Two Fingers。今日份DP，我之前好久没有被DP题难住过了，但是这道题真的把我难住了。自己建立状态的思路是：用两个一维数组来跟踪到某一步最小的步数，但是这个模型完全没有考虑手指移动的距离。后来看了答案，果然是一个三维的DP数组，而且这道题如果用bottom-up的话计算量会非常大，因为计算了很多不可能出现的情况。所以这道题更适合top-down的DFS+memo类型的DP。
1376. Time Needed to Inform All Employees。今日份DFS，最标准的DFS写法了。
844. Backspace String Compare。这道题的栈解法6分钟就AC了。但是followup做了足足30分钟才AC。O(1)空间解法受限制条件非常多，于是也导致了edge case 也非常多，WA了好几次最后才AC。

总结一下：
1. top-down DP的计算是递归依赖后面的计算结果，同时用DP数组存储进行优化；bottom-up则是迭代计算，依赖数组中存储的已经计算好的结果。
2. 如果一个序列中有专门的符号代表出栈，那么这个解决这个序列的问题或许可以不用真正的建立一个栈，而是使用指针来模拟。

action item：
1. 明天要刷关于segment tree的题目；
2. 明天学习算法：Manacher Algorithm
3. 明天复习算法：union find。

打卡第一天！
1. Android Unlock Patterns 一道典型的backtracking的题，可以in-memory修改grid
2. Find Numbers with Even Number Digits 一道常规题。。
3. Minimum Value to Get Positive Step by Step Sum 这道题可以O(n) one-pass 解出来哦 ，不需要二分查找阈值～

Day 14 06/27: 七道题

竟然还有这种好事，刚发现，先补下前几天刷的

6.27 连续第七天 打卡5题

Check If Array Pairs Are Divisible by k，195周赛第二题，将所有值mod k（注意对负数的处理），然后根据余数x进行匹配（x与k-x配对）
Path Crossing，195周赛第一题，HashSet
Split Array into Consecutive Subsequences， Greedy，greedy策略：将每个数尽可能的连到之前的continuous subsequence上
Bulls and Cows，字符串处理，根据规则模拟就好，注意计算Cows时，不要重复计算位置内容完全一样的
Perfect Squares，DP/BFS/Math 用数学方法最快，但是解法中用的不是常见的数学性质

打卡第26天， 刷了6道题

12. Integer to Roman
建个从大到小（1000， 900， 500， 400， 100， 90， ...) 排好序的map, 然后依序比对

13. Roman to Integer
string, 判断是否存在'IV', 'IX'...

14. Longest Common Prefix
双loop，外层str【0】的字符

61. Rotate List
linked list, 先测长度， 并保存最后一个node， 再 找到 （k %= length）-1 位置的node，rotate

82. Remove Duplicates from Sorted List II
linked list, 用dummy，dummy.next = head, 如有重复，记得把之前node的next先设为None

83. Remove Duplicates from Sorted List
linked list

打卡第27天