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

lanlanblue11 发表于 2020-7-3 13:57
连续三天打卡

今天克服昨天解很久的Ｍicrosoft高频题skyline题，顺便解两题design ...

要面巨硬么？加油～！

慕容清 发表于 2020-07-02 06:29:20
7.2 打卡第一天

其中543. diameter of binary, 感觉很tricky的一个点就是这个diameter，不一定是要通过根节点的，完全可以是通过subtree的根节点。所以需要在

打卡第二天

1. Subset：还是加入新的subset时 需要new arraylist<>(subset) 否则返回是空集，因为是copy the bits,在每一次的add，remove操作下，最后返回的地址存储的是空，所以每次操作都需要一个新的address来存储当前subset。
2. subsetii: 有重复元素时，首先需要sort，让重复元素相邻，这样再进行backtracking时，相同元素的子集在该元素出现的第一次的时候，就已经全部被返回，所以只要有相同元素，就直接跳过即可。自己本身的想法是如果用重复的subset，就直接不加了，但是判断代价比较高。
而且subset需要有一个start指针，来说明之前访问过的就不再加入。
Permution 不同的是，元素都是重复的，只是排序不同，所以不需要start指针来限制，之前访问过的可以，但是排序得是新的，不能重复。
3. Permutation : permutation 没有start指针，所有for都是从0开始，但是需要有contains来判断是否已经有过这个元素，如果有就直接continue；
4. Permutation ii：有重复元素，那么就需要跳过重复元素，而且之前用过的元素不能再次出现，重复元素和之前用过的元素是两个概念。很巧妙的一个点是引入了boolean[] used，之后之前访问的元素我们就令used[i] = true; continue；如果有重复元素也是，和之前的相同，但是这里加入了！used[i - 1] 这里要注意都是同一层次的for循环里面才能够比较是不是有重复的元素，而且再同层进入下一个i时，之前的used[i -1] 已经变回了false；所以需要取！。

D1:  新手 打卡第一天 (UTC: 03/07/2020)

Learner: 主要学习divide and conquer. 很羡慕一天可以刷很多到题（5+）的TX。现在办不到。

1：Binary Tree Maximum Path Sum.
     三种情况：左子树，右子树，过ROOT.  ResultType 的辅助 和 对于负数值的考虑。
2:   Binary Tree Maximum Path Sum II
     标准的divide conquer; 节点值是负数的考虑（小坑）
3:  Longest univalue path
    设置一个全局变量。对每一个节点，计算最长路径，跟新全局变量。也可以考虑 ResultType.

July day1

7月打卡第二天
backtracking continue - 5题
主要用于求解排列组合问题
需要注意对元素的标记问题：
  在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素
  但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

day3 # sql 3题
1. 自联结相减注意条件
2. 子查询--多表联查
3. 中位数--row_number_asc落在 (row_number_desc-1, row_number_desc+1)区间

补一下昨天下午刷的题（睡太早忘记打卡了！）
打卡刷题第二天：

Binary Tree Right Side View:
很intuitive的level order traversal (BFS) 打印每一层最后一个node，运行结果出来space上却不是很很好。
想了一下DFS也可以做，只要存一个max depth seen，然后dfs的时候一直先visit right child，就可以确定我们看到一个新depth的时候必然是在rightmost child。
DFS和BFS时间上都是O(n)，空间上一个是O(height)一个是O(width)，感觉在比较平衡的树上还是DFS更好。果然提交以后发现space improve了不少。

Diameter of Binary Tree:
recursive call 返回left和right child的max depth和max path,
recursive step用
  max_depth = max (left_max_depth, right_max_depth) + 1
  max_path = max(left_max_path, right_max_path, left_max_depth + right_max_depth + 1) 其中最后一项是考虑经过node自己的最长path

Lowest Common Ancestor
经典题，重新做感受一下。最直接的做法就是dfs找到两个node记录path，然后对比path的prefix就可以。
更elegant的做法是recursive call ：
如果两个node都在subtree，return LCA node
如果只有一个node在subtree， return该node
如果都不在，return None

给楼上几位都加了米 大家一起加油！

好久不刷题，准备重新捡起来。今天三题。
valid parenthesis 用stack 快速解决了。题目本身可以follow up求所有可能方案。晚上再想。
alien dictionary，一开始以为是拓扑排序。结果比那简单。但有个corner case bug了好几次。

Day 11, solved 6 problems.

Tips:
1. When running a large number of operations on an enough small computation domain, a cycle is a very likely result: e.g., LC 957;
2. String manipulations are situation to apply StringBuilder: e.g., LC 405;
3. Sometimes sorting is a good option to solve seemingly complicated problem: e.g., LC 1268.

7.3 打卡第三天

1. Binary Search。关于greatest common divisor 和 least common multiple 的写法一定要烂熟于心。
2. HashMap。问题核心在于要用map把状态记录下来以便取余数加快运算。
3. Greedy + DFS. 每个节点要想被cover只有三种状态，dfs就是要返回这个状态，父节点根据这个状态greedy选取自己的状态。