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

jerryzzf 发表于 2020-7-5 07:16
连续第 3 天打卡，完成 5 道 Backtracking, DP, Heap 题：(3/5)
1. Next Permutation
2. Permutation Seq ...

好奇Ugly number II怎么用dijkstra algorithm做啊？？请大神解释哈

今天三题：482/929388

day 4kth largetst element
method 1: quick sort, get kth element
method 2: quick select
# method 3: min-heap

打卡 7.4 Day 4
今天完成recursion II 的后半部分，一共7题，
其中比较难的题有
Largest rectangle in histogram, 这题用了O(n^2) 的brute force法，O(nlogn)的divide and conquer法 都TLE了，最后看了答案学到了用 stack 比较巧妙的方法，只用O(n)
skyline problem 花了很长时间才看明白答案细节。。下次遇到应该还是不能ace，但总体思路已经掌握
以及July chanllenge
Ugly number II
看了hint后 用3个pointer 以及三个list 使得 l_i[p_i]*i > current_ugly_num, 这样就能保证下一个ugly number一定是 l_i[p_i]*i 中最小的数。

07/04/2020
263. Ugly Numbers 注意负数直接return false;
264. Ugly Numbers II 三指针， 分别2，3，5。取此指针位置*此指针数 最小，该指针后移
441. Arrange Coins 二分法注意乘法溢出，需用long而非int
107. Binary Tree Level Order Traversal II 可以用DFS递归；也可以用BFS，两个queue，当前层一个，下一层一个。最后reverse一下结果。

7.4 day3

7.4 day3
zszszszszszs

今天做了Minimize Max Distance to Gas Station, Capacity To Ship Packages Within D Days, 重新做了下Koko Eating Bananas，其中gap station这道题参考了下solution，依然是找max distance的上界和下界，然后二分查找。需要注意的是distance是double，所以退出条件变成了left+1e-6>right，还有计算小区间能加几个station时，用Math.ceil()-1的原因是当4/2=2这种整除时，相当于只能放1个station。

打卡第三天
07/04
Wildcard Matching
Regular Expression Matching
Longest Valid Parentheses
Largest Rectangle Of 1s (和Largest Rectangle in Histogram 想法类似, 都用DP)
Largest Square Of 1s

07/04 打卡第四天

264. Ugly Number II
Daily challenge. Maintain three sorted list and choose the min to add to the new list.

1104. Path In Zigzag Labelled Binary Tree
数学题，考的是二叉树每一层之间序号的关系。

971. Flip Binary Tree To Match Preorder Traversal
dfs