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

补昨天 day 21

lc 4
694. Number of Distinct Islands
通过方向来标记岛屿的形状

209. Minimum Size Subarray Sum
two pointers

6. ZigZag Conversion
use current row and goingDown

1487. Making File Names Unique
晕死我了。。用map存lastused， 用seen存所有的

2020年6月20日 第二十天发帖。今天刷了5道题，同时和另外一个朋友mock了一场interview（不是在pramp上做的，所以就不算credit了）：

97. Interleaving String。今日份DP，定义一个二维的DP数组，然后压缩成一维，很快就AC了。index数值需要注意-1，除此之外没有什么坑。
739. Daily Temperatures。今日份stack题。这属于那种“寻找位置上next greater element”的问题，根据之前总结的经验一直pop栈顶知道找到一个更大的元素或者栈空为止，不到10分钟就搞定了。
959. Regions Cut By Slashes。今日份graph题。今天第一道自己完全没有思路的题目，后来看了答案惊叹它那个定义node的方式：把一个正方形按对角线分成四个等腰直角三角形，每个这样的三角形算是一个node，然后做并查集操作，数representitive node的个数。这道题的难点在于想出这个node的定义方式，开了眼了。
371. Sum of Two Integers。今日份位运算题。一开始自己的思路是：直接按位运算加法的方式进位，只计算前32即可。后来看了答案意识到自己用了自增运算符（++），也算是用了加号。答案中模拟进位是把所有的进位当做一个数继续加，循环迭代直到进位之和为0，同理还有它的借位。难点在于对二进制加减法更深刻的理解，而不是位运算本身。
968. Binary Tree Cameras。自己想的DP思路是：dp1表示一个节点为root下这个问题的答案，但是root上必须安摄像头；dp2表示一个节点为root下这个问题的答案，但是root上必须不安摄像头（除非它是叶节点）。但是在定义状态转移的时候犯了一个很致命的错误：我假设了对于同一个节点，dp2一定小于dp1，同时也假设了两个相邻的节点肯定不会同时安装摄像头。后来不得不修正了3、4次状态转移，到最后发现那些假设全都是不正确的。AC后看答案表示，那个贪心的解法是我真的想不到的。

总结一下：
0. 今天学习到了切割正方形union find的思路；
1. 对于DP问题，如果状态转移的定义涉及到最大最小值的运算，最好直接把可能的结果全部代入计算，除非能够理论证明某个值一定不是最值；
2. 对于DP问题来说，如果状态转移涉及最大最小值的运算的时候，plan B可以考虑贪心算法；

Day21 三道题

20200621:
3: 1488
4: 0174, 0358, 0502, 0759, 0871
5: 0818, 0857, 0864, 1439

本月全勤(但目前只申请了超过五天的奖励)
https://leetcode.com/null7ptr/
(7月末将尝试更改用户名)

第四次打卡：
#262: 要注意细节 要求两位decimal 所以要加上round()
#601: 自已用了self join，window function也可以，不过要加上平时比较少用的 (rows between X preceding and X following)
#602: 余数的表达不常用 忘记了 id%2 = 1 --> odd
#626: 思路上可以拆成odd/even,之后再join回去就好了
#627: update的用法 平时工作中很少去修改database， 所以update/delete这种接触的较少
P.S 之前有两次打卡没加到大米诶 希望大大看到之后能帮我加一下 缺大米看不到面经好痛苦。。。

06/21/2020， Day18
今天刷了3道题

今日4题

第五天

world ladder 2。 主要难点是图的构造。
decode ways。dp的基础题
path sum2. 名义上的easy，不过实际最优解感觉有med。维护一个全局的preSum hashmap，动态的加入之前路径上的 从root出发的pathsum：多少条路径。follow up就是返回所有路径。这时候将value换成List of List就行了。

补前天～打卡day20

lc 6
24. Swap Nodes in Pairs
创建dummy node，两个一换，注意最后有落单的就不要换了

491. Increasing Subsequences
回溯，注意检查tmplist的size>1，标记访问过的数字

419. Battleships in a Board
就看一个cell的上面和左边有没有，one pass

426. Convert Binary Search Tree to Sorted Doubly Linked List
初始化头尾，在helper method linknode， 回去后记得close

548. Split Array with Equal Sum
build a presum array, j for middle cur, i for left, k for right

298. Binary Tree Longest Consecutive Sequence
dfs

哭哭 今天把号丢了 希望明天能找回来
bfs刷的我要吐了