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

7/16 leetcode打卡
286
看了题解 BFS神仙做法
把所有门都找出来， 对所有门，使用队列，同时都走了1步，先到达的就是距离短的
BFS可以在低TC和SC的情况下 保证最短距离
200
做过的题，可以将访问完的1设置成0，这样就不需要再另设置一个visited二维数组
130
不看题解 真没想到一个DFS都能玩出花来，从边界出发先找和边界联通的区域 之后再把剩下的标记

今日水题14道，都是中等难度，哎，又是低效率度一天，求加米。

day 9 - 7 questions
dynamic programming
将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。
无后效性: 未来与过去无关
最优子结构性质: 大问题的最优解可以由小问题的最优解推出
重叠子问题（overlapping subproblems）性质-->递归算法反复求解相同的子问题;
         在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。
设计DP算法: 1) 设计状态:  2) 设计状态转移方程: 自顶向下的备忘录法; 自底向上的动态规划

一杯茶，一包烟，每日一题写一天

Day 6

50. Pow(x, n), 分治 n->n//2->n//4->... 注意下负数整除法 -3 // 2 = - 2 而不是 -1
809. Expressive Words, string题 corner case不是很多 注意下不要曲解题意
938. Range Sum of BST, BST post order traversal

July Day 12 ! 加油

先来三题打个卡
Tree Diameter         -> 2个 BFS，先从任意点出发，找到能reach的 最远的点，然后从这个点出发，找最长路径
Battleships in a Board         -》DFS 很直观，但是要求 One Pass + O(1) 需要用一个trick，遇到一个X,差 X-1 是不是 X OR Y-1 是不是 X，如果是的话 就跳过。战舰的开头是不会满足这二个条件的。
Pow(X,N). recursion 写法要好懂一些 Log(N)

打卡13天
07/16
Pow(a, b)       
Minimum Remove to Make Valid Parentheses
Design Browser History
Maximal Rectangle
Remove Invalid Parentheses

7/16/20

1035. Uncross Lines
DP，和Longest Common Subsequence一样

50. Pow(x, n)
Fast power

567. Permutation in String
Sliding window

96. Unique Binary Search Trees
dp[i] = num of unique BST with i values
dp[i] = dp[0] * d[i-1] + dp[1] * d[i-2] + … + dp[i-1] * dp[0]

142. Linked List Cycle II
Slow and fast pointers
Once they meet, move slow to head and move at the same speed
Next time the two pointers meet at the entrance of the cycle

打卡第四天？？有点忘了今天是第几天了。。

7/16
继续图类的题：
LC310 Minimum Height Trees, 自底层向上建树需要用到map<node, adjacencies>, 同时注意树的高度由root到leaf的最长距离决定
LC207/210/269 三道topological sort的题，用记录每个节点的in-degree，一次迭代后in-degree为零的点是下一次迭代的起点。