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

打卡第三天，关于dp的题目。

https://www.1point3acres.com/bbs/forum.php?mod=attachment&aid=MzQxNjAzfGY3NTE5NGM2ZWI2MjM0MTJlYjg4MWJlOGM5NmJkZWI3fDE3OTQ1Mzg0NjI%3D&request=yes&_f=.png

Day 13，刷了三道题，两道新题：

Longest Common Prefix        LC 14
Cheapest Flights Within K Stops        LC 787

1. Longest Common Prefix, 横向比较：两两比较；纵向比较：比较所有字符串的第一个、第二个...直到发现不同，return

2. 最便宜机票within K Stops，方法很多，可以用bfs，dfs，dp，最短路算法，这里主要研究了dijkstra算法。pq优化版本。pq每次pop时，表示将pop的节点加到已确定最短路的集合，pq中剩下的是还没有确定最短路的集合。在pop的点上进行松弛操作。

3. 两数相加，while条件可以简化成while head1 or head2 or carry，循环主体判断head1、head2是否为空。

2020年6月13日，第十三天发帖，今天刷了8道题：

781. Rabbits in Forest。这算是用map可以解决的比较经典的问题了，唯一比较tricky的地方是如何数兔子，比如要考虑到情况：如果有四只兔子说有两只同类跟自己一个色，那么其中三只可能是一个色，另一只和另外沉默的两只是一个色。
188. Best Time to Buy and Sell Stock IV。股票买卖系列的DP，这次是差那么一点点就自己定义状态成功了，同时并没有意识到k大于天数一半时的特殊情况。
728. Self Dividing Numbers。数学题，因为有10000的限制，所以不需要把数字转化成字符串来找0。
1041. Robot Bounded In Circle。又是一个数学题，第一时间想到的是数学里收敛和发散的特性。很快就发现了收敛的条件：要么每次循环后都回到原位，要么每次循环后方向都不和之前一样。据此就很容易做了。
660. Remove 9。又是个数学问题。尝试数了一下：第81个数是100。于是想了想，或许这个问题可以归纳为：可以将input展开为9的幂级数，然后计算相同系数的10的幂级数。虽然到最后这确实是正确答案，不过我并没有当场给出一个证明。但是这实际上是一个将一个10进制数转化为9进制数的基本思想。
784. Letter Case Permutation。没啥好说的，回溯法穷举就可以了。
316. Remove Duplicate Letters。这个问题挺有意思的，知道要用栈，不过在什么情况下入栈出栈还是没有彻底搞清楚。后来看答案才发现这又是个类似单调栈的用法。
417. Pacific Atlantic Water Flow。这个题思路是从边缘开始，逆向BFS整个图，太平洋可以流水的地方全部打上一种标记，大西洋能流水的地方全部打上另一种标记，最后看哪些地方被同时打上了两种标记就可以了。这个标记还兼顾了visited数组的功能。我用了整数来做标记，1代表太平洋，2代表大西洋，如果某个地方最后结果是3，那就是一个结果。

总结一下：
0. 今天复习了一下如何使用位运算做标记；
1. DP问题也是可能存在通解不work的特殊情况，这种时候要单独拿出来分析；

action item：
1.继续刷栈类的问题；

06/14/2020 打卡第15天

今天完成6道
Minimum Number of Days to Make m Bouquets - medium 知道用binary search后不难，但知道用binary search这件事，很难。
Kth Ancestor of a Tree Node - hard 评论区大多是用binary lifting。 我在讨论区找到一个不是用这个算法的，很容易理解也很快。当然对新手也是一样不容易想到。
House Robber II - medium 我用的方法是包括第一家的dp，不包括第一家的dp；两种取最大值。
Best Time to Buy and Sell Stock II -easy
Reverse Linked List - easy 这道题也是traverse和recursive两种方法都要会。
Valid Anagram - easy

All My Submissions
Time Submitted        Question        Status        Runtime        Language
0 minutes ago Valid Anagram Accepted        3 ms        java
2 hours, 44 minutes ago        Reverse Linked List        Accepted        0 ms        java
3 hours, 15 minutes ago        Best Time to Buy and Sell Stock II        Accepted        2 ms        java
3 hours, 40 minutes ago        House Robber II        Accepted        0 ms        java
3 hours, 42 minutes ago        House Robber II        Runtime Error        N/A        java
7 hours, 43 minutes ago        Kth Ancestor of a Tree Node        Time Limit Exceeded        N/A        java
8 hours, 50 minutes ago        Kth Ancestor of a Tree Node        Accepted        2199 ms        java
9 hours, 31 minutes ago        Minimum Number of Days to Make m Bouquets        Accepted        24 ms        java

#第六次打卡 今天刷了四道题，一片wrong answers或者runtime error，简直惨不忍睹。。。我发现我举一反三的能力还是不强，做到相似的题就容易被原来的解法给限制住思维，导致我借鉴思路的时候反而束手束脚的。

2020.06.14  Day 14. (1-indexed)

今天做了一个公司的笔试（四道题），然后在pramp上做了两道题。但是不太方便截图。
另外在pramp上做了一个mock，如图。

Main takeaways today:
1. Catalan number. (2->n)II(n+k)/k
2. Understand C++ new features more
3. 在面试一开始提前说出所有可能可以的算法会让自己更从容一些。

第四天

Find the Smallest Divisor Given a Threshold 复习了一下二分法。强记了c++包中的写法。「first，end）中第一次出现的不小于value的值。
Encode and Decode TinyURL复习了一下Grokking the System Design Interview 。先马明天接着看
Implement Queue using Stacks        用两个stack。s1上新下旧，push新。s2上最旧下次旧。pop的时候先peek。peek先查看有无东西，没有东西的将s1的pop反向押入s2.

06/14/2020 Day11
今天刷了3道题，周末事情太多，反倒没时间刷题了。

06/14 Day 10: 六道题

6/14 第五天

现在题都能做出来，但是都不是最优解。在写完代码后，还是要细细看每行代码，算出计算量，并思考如何用更短的代码和更少的计算量实现相同的逻辑，并且尝试寻找更快的方法。
127. Word Ladder
139. Word Break
140. Word Break II