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

2020-6-13

打卡第14天

338. Counting Bits：dp加bit manipulation题目，dp[i] = dp[i>>1] + (i&1)，e.g., 11101 = 01110 + 1，一个二进制数的1的个数等于它向右shift 1位后数的1的个数加上最后一位是1还是0。i>>1就是i/2。

371. Sum of Two Integers：用a&b<<1来代表进位，进位^a^b就是最终结果。

417. Pacific Atlantic Water Flow：这道题trick的地方是可以从boarder开始逆流而上dfs marking节约时间，用一个矩阵存pacific的结果一个矩阵存atlantic的结果，最后取交集。

435. Non-overlapping Intervals：按end排序后逐个扫描，如果两个interval overlap，删除end大的保留end小的，最后返回删除interval的个数。

449. Serialize and Deserialize BST：preorder traverse for serialization，deserialization时第一个是root，往后扫描找到所有比root小的值是left child的，剩下的是right child的。

572. Subtree of Another Tree：建立一个helper function sameTree()，如果s的root.val等于t的root.val，and sameTree(s, t)返回true，t就是s的子树，否则的话recursive call isSubTree() on left child and right child of s。

1143. Longest Common Subsequence：dp题目。如果第i位和第j位的字符一样，dp[i,j] = dp[i-1，j-1] + 1，否则的话dp[i,j] = Math.max(dp[i-1，j], dp[i，j-1] )。

2020-6-13

打卡第14天

338. Counting Bits：dp加bit manipulation题目，dp[i] = dp[i>>1] + (i&1)，e.g., 11101 = 01110 + 1，一个二进制数的1的个数等于它向右shift 1位后数的1的个数加上最后一位是1还是0。i>>1就是i/2。

371. Sum of Two Integers：用a&b<<1来代表进位，进位^a^b就是最终结果。

417. Pacific Atlantic Water Flow：这道题trick的地方是可以从boarder开始逆流而上dfs marking节约时间，用一个矩阵存pacific的结果一个矩阵存atlantic的结果，最后取交集。

435. Non-overlapping Intervals：按end排序后逐个扫描，如果两个interval overlap，删除end大的保留end小的，最后返回删除interval的个数。

449. Serialize and Deserialize BST：preorder traverse for serialization，deserialization时第一个是root，往后扫描找到所有比root小的值是left child的，剩下的是right child的。

572. Subtree of Another Tree：建立一个helper function sameTree()，如果s的root.val等于t的root.val，and sameTree(s, t)返回true，t就是s的子树，否则的话recursive call isSubTree() on left child and right child of s。

1143. Longest Common Subsequence：dp题目。如果第i位和第j位的字符一样，dp[i,j] = dp[i-1，j-1] + 1，否则的话dp[i,j] = Math.max(dp[i-1，j], dp[i，j-1] )。

打卡第一天，刷题6题。

学习三点：
1. 代码风格非常重要，空格一定要加。
2. 逻辑关系不能都写在一起，尽可能写子函数。
3. 使用含义清晰的变量名命名。

6.13 day 15824 easy 解法很简单，但比较running time发现stringbuilder比string+=快很多，遇到大量字符串append的时候还是使用stringbuiler更合适
825 medium 可以根据题目要求缩小搜索范围，化简到极致可以直接用部分和做
785 medium 自己想了个遍历的解法没能ac，改用了dfs思路更清晰了速度也更快一些

我看好久没有人加大米了，是这个活动停止了吗？@yeehaah

06/13 打卡第四天 三道题

不知不觉已经第11天了，这次是中国人，水平很高，看到了差距。继续通过不断的练习提高。

打卡第13天

#第五次打卡 今天写了三道题。很奇特的是两道hard的题很快就用backtracking做出来了，反倒是easy的题要求用Divide and Conquer费了好一些时间，还提交了好几次才最终accepted。这道easy的题我原来就会greedy的O(n))解法，不过今天尝试了实现Divide and Conquer的O(n)解法，有了完全不一样的体验，还是很有收获的！

6.2开始，今天第12天