7月缺米的来刷题/Mock interview活动

7/4 打卡第一天
1. LC 目前5题
    3Sum 记住关键词 2 pointers, 注意查找过程中skip duplicates就可
    Product of Array Except Self 记得第一次遇到没有想到，现在看到能够回忆起当时看的套路，用当前数左边的cumulative product * 右边的cumulative product
    Ugly Number II 今天的daily challenge， 看了hints能够马上想到用heap来存储ugly number， 每次取出一个ugly number，用此number制造后面的ugly number并存入heap, 注意skip duplicates
    Longest Substring Without Repeating Characters 也是使用2 pointers, 每次right pointer指到前面的repeating character 就记录一下当前最长的substring，然后把left pointer缩减到repeating character的右边
    Decode Ways 是准备mock前做的，用backtrack recursion做了，但是有TLE，所以是需要用memoization来解决

2. Mock
    第一次用Pramp，peer是天竺哥，还是挺nice的，遗憾的是我觉得我做interviewer的技能没有对方好，可能对方的experience没有我好
    得到的feedback也挺有用的，说我的communication还是少了一些，这一点不出所料...
   

连续第 3 天打卡，完成 5 道 Backtracking, DP, Heap 题：(3/5)
1. Next Permutation
2. Permutation Sequence
3. Subsets
4. Subsets II
5. Ugly Number II

Tips 总结：
1. Subsets 的两道题就是最为基本的 Backtracking 题，非常模式化；
2. Permutation Sequence 这道题要求我们找出第 k 个 permutation sequence，如果使用一般的 backtracking 肯定就 TLE 了，所以这题的关键其实就是 math 里面的找规律，挺特殊的，可记；
3. Next Permutation 这一题也不是传统的 backtracking，我发现这类题目就是间接地考察了我们对 backtracking order 的掌握；
4. Ugly Number II 我竟然用 Dijkstra's algorithm 写出来了，给自己点个赞。但是这道题最好的方法还是 dp，个人认为非常巧妙，利用了三个指针保持整个 ugly numbers 的顺序。

7/4 打卡第4天， 刷了3道题

77. Combinations
backtracking, combine(n-1, k) 和 combine（n-1, k-1)

78. Subsets
backtracking, 用stack

1496. Path Crossing
用set记录走过的点

07/04 新手第一天登录
刷了三道binary search
其中sqrt 在循环里比较条件的时候不能用 int * int 会超出int类型数值上限

第一天发帖。

今天开始在7月贴发帖了。最近同时在准备一些面经（非leetcode）和system design，刷题数量减少了。

410. Split Array Largest Sum。挺中规中矩的一个DP，这次边界值处理得比较好，所以很快就写出来了。
895. Maximum Frequency Stack。这个题目一开始理解错了：以为一旦删除一个数就要把全部相同的数都清空。于是用了LFU的做法，果断错了。看了一下答案，用了stack嵌套stack的方法，这样就能表示每个frequency的值的分布情况了。
611. Valid Triangle Number。这道题最brute force的想法就是N^3三层迭代循环，于是自然联想到用排序来降低时间复杂度。于是排序后可以发现：先选择最小的两个边长，那么最大的边长取值范围就是连续的了，所以可以用二分查找。看答案还有一种方法：维护一个边界值k，这样在选择第二条边的时候不断更新这个k，就不用花时间二分查找了。

总结一下：
1. 连续性问题由于问题本身的限定条件，可能存在比二分查找更优的解。所以当限定条件比较多时，思考一下会不会有O(1)的解法。

action item：
1. 明天复习一下manacher，prim和kruskal算法；
2. 明天做一道关于line sweep的题目；

7月打卡第二天  3道：449，1469， 938

1. 总结了JAVA中String, StringBuilder, StringBuffer的区别。
String是final类，生成的变量在class文件常量池且只保存一份。在每次循环String +操作中都会开辟新空间。对String对象的任何改变都不影响到原对象，相关的任何change操作都会生成新的对象。
StringBuilder只会开辟一次，后续循环在第一个的基础上append;
StringBuffer适用于synchronized多线程的情况。

2. String、StringBuilder、StringBuffer三者的执行效率：StringBuilder > StringBuffer > String  (事实上String + 操作会自动被JVM优化成StringBuilder)

3. 文件常量池 VS 堆空间
JVM执行引擎会先在运行时常量池查找是否存在相同的字面常量，如果存在，则直接将引用指向已经存在的字面常量；否则在运行时常量池开辟一个空间来存储该字面常量，并将引用指向该字面常量。
通过new关来生成对象是在堆区进行的，不会检测该对象是否已经存在的，创建出的一定是不同的对象，即使字符串的内容是相同的。

刷题 继续刷题 每天刷7题+1每日1题 等于8题 冲

Jun 4 打卡第3天，7道题
305. Number of Islands II, Union Find, 注意parents数组的初始化，以及每次添加一个新的position时，将parent进行更新union。
887. Super Egg Drop, 将问题转化为m moves，k eggs，最多能check多少floor；不管egg碎不碎，move都用了一步；
688. Knight Probability in Chessboard, BFS会TLE；需要使用DP，循环K次，每次基于grid操作，最后总和即可；

20200704:
3: 0234, 0445, 0873
4: 0264, 0895
5: 0335

Day 4: 今天刷了五题，Ugly number II，diagonal traverse，house robber I，II，III
Ugly number II：这题如果用min heap做非常的慢，更好的方法是dp的做法记录第n个ugly number，然后用三指针分别指向最近一次乘2，3，5的ugly number。转移方程是每次取乘积最小的数。
diagonal traverse：不难，跟BST zigzag traverse很像
house robber I + II： I是经典dp问题。II加了一个环形数组的条件，比较清晰的做法是两个dp array分别求取一，不取最后和取最后，不取一的两种答案再return较大的数
house robber III：在tree上做同一问题，recursive的方法更简单。可选择divide & conquer 合并时还是有root取或不取两种情况。或者dfs+memo做，memo用hashmap存储dp的values