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

# 第4次打卡（6.12）

216(M)/3(M)/206(E)/70(E)

今天做了一道简单的DP，一个滑动窗口，两个递归。
感觉现在知道思路之后写代码速度还可以，但还是很难一下子想到合适的解法，还得再刷题，多思考，增强自己对各种算法的理解以及熟悉度。
216和昨天的一道题基本一样，感觉连着做了几道回溯之后，有点公式化处理这道题了，希望未来复习的时候也能这样熟练。
（今天剩的时间还很多，原则上还应该再做两道DP，但因为还有别的项目要做，所以今天的刷题就到这里啦！明天再加油⛽️）

6.2开始，今天第12天

打卡第11天， 刷了3道有关树的题

337 House Robber III
用recursive, 感觉有点象DP。 子函数rob_recursive(root) 返回包含这个节点和没包含这个节点的最大值

404. Sum of Left Leaves
DFS，recursive， 加个的is_left变量给子函数

437. Path Sum III
和337有点类似，迭代的子函数返回包含这个节点的所有path的sum，和不包含这个节点的path和为target的数目

Day 8
A little busy with chores today, only did 3 problems

TGIF
5th day

打卡day3 刷题第26天
主要还是dp解题，最近集中刷dp

64 Minimum path sum
dp[j]记录到下标(i,j)位置时的minimum path sum, 同时注意对于边界情况（i==0 || j ==0）时的处理。
另外，滚动数组可以把空间优化到O(2N)。

931 Minimum falling path sum
同样是给定一个grid的题，dp[j]记录到(i,j)结束的minimum falling path sum，而下一行的结果可能取dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]中最小值再加上自身。

338 Counting bits
复习了一下位操作符。可以用dp记录i的二进制表示有几位1，但不用开数组也可以直接做，比较简单。

Reconstruct Itinerary, 首先想到用DFS，卡在了如何排序机票，以及如何标记用过的机票，因为用过的机票就不能再用了，一开始我想用Heap来排序，用过的机票就从Heap里删除，但发现backtracking时还要把删除的机票重新添加回来，一旦重新添加回来，heap每次取出的就都是同一个值了，后来用了一个pair解决了。之后看了高手的代码，发现不用定义pair直接用个list就可以，每次用过机票就从list中删除，回溯时在加到指定位置。还有一种更快的解法是什么欧拉图，欧拉图是指图里遍历图并且图里每条边都访问一次。这种图有条件，每两点之间都通路，而且对入度出度还有要求。做法类似后序遍历，访问过的边删掉。时间复杂度O(N).

Evaluate Division, 这题有很多Corner case要一一想清楚，第一是要求的被除数或除数可能不在map里，第二是，被除数和除数相等，第三是被除数和除数可能不连通，最重要是的已经访问过的节点就不要再访问了，否知会照成死循环。

Course 2 这题和1差别不大。

一共三道题。

打卡第12天

Day 8 2020.6.12
98. Validate Binary Search Tree 29min
105. Construct Binary Tree from Preorder and Inorder Traversal 42min
103. Binary Tree Zigzag Level Order Traversal  11min
今天写的都比较简单 第二题卡了一会

打卡第一天,刷了六道SQL题, SQL还是要常刷常新的,求大米鼓励!