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

07/06

三道dp题
学习了 python initialize 2d array的时候不能用 * 会是浅拷贝

66. Plus One
426. Convert Binary Search Tree to Sorted Doubly Linked List ： 分治法，最后记得首位相连
46. Permutations： backtrack 第i个数可以放哪些位置。

第五天打卡
刷了3题

Query on a permutation key
Paint House III
Plus One

最近比较太累了。

2020-07-06
三道题
1. Binary tree pre-order traversal
2. Binary tree in-order traversal
3. Plus One (July challenge)

07/07 第七天

路径总和 递归分别求取自由子树 直到到达叶子节点
整数转换 实际为汉明距离的变化 利用位操作来实现
不邻接植花 考察邻接表💹 哈系表存储可用的颜色

6 theme about trees, only 5 of them got passed

搞了一个电面，只刷了三道题，好累。。。 明天加油！

Day 2:
Summary
Valid Palindrome , isalnum
Read N Characters Given Read4 II - Call multiple times,  the read4 may return 0. when cur pos == read pos, call read4
Pow(x, n) ,for negative n, 1/x * 1/(Pow(x,-(n+1))), this is for INT_MIN,-INT_MIN is over flow

Day 3: 只做了两题。Palindrome partition系列：
1 是典型的 dfs，回溯， 套用subsets的模板，对于每个位置，切还是不切。
2 是求最小切割数，用的dp，需要padding，已经不太熟悉了。得空要复习一下。

7月5日，第二天发帖。今天刷了3题。不过今天有进步，三个题全是hard且都是一次AC。

363. Max Sum of Rectangle No Larger Than K。这道题算是当日份的DP题。通过这道题目才了解到那一类针对数组把dp[i]定义为必须以第[i]个元素结尾的算法叫做Kadane算法，而这道题目是一个二维的Kadane，这是其中一个难点。同时还有一个难点：寻找一个序列中不大于某个值的元素的最大值。遍历一遍数组肯定可以做到，但是用TreeSet可以在O(logN)时间内做到。这也是这道题唯一能优化的地方。所以相对于brute force，这道题优化并不多。
214. Shortest Palindrome。这道题等价于：寻找一个字符串中开头位置最长的回文结束的位置，于是很自然想到Manacher算法。
882. Reachable Nodes In Subdivided Graph。这个题其实就是先针对全图做一个Dijkstra找出所有原图中节点的“最小距离”，然后根据这个最小距离数每条边上可以访问到的新节点的个数就可以了。这个题比较恶心的地方在于计算距离的时候要考虑原图中节点本身所以要+1。

总结一下：
1. TreeMap和TreeSet的作用：在去重的条件下 1. 动态寻找最大值、最小值：O(logN) 2. 动态寻找不高于某个cap或不低于某个floor的最大值、最小值：O(logN)。3. 动态查找某个区间范围内的值的个数：O(logN)。
2. Manacher算法本质上是用前若干部迭代得到的回文范围内对称的特性，缩短一部分计算时间。根据镜像值找出半径后，还要自己继续扩容验证直到不再是回文为止，结束后一旦半径范围超过之前的回文，需要重置当前回文。
3. 朴素的Dijkstra原本是基于BFS，或者是Queue的，同时需要两个集合来分别记录是否需要update某一个节点的距离。用优先队列改进后的Dijkstra需要根据当前距离排序，同时不需要访问整个图，因为通过邻接表在未来的迭代中可以达到相同的效果，所以只需要关心与访问过的节点直接相连的节点即可。由于设置的条件保证只有最短距离发生更新时才会再次处理某个节点，最终结果也是满足Dijkstra的要求。

action item：
1. 明天开始刷面经题目