在职跳槽刷题打卡及适时分享感悟--计划明年2月面试

11.5

518. Coin Change 2  (Medium)
一维DP，计算顺序很重要，outer loop是coin，inner loop才是dp array，complexity O(len(coins) * amount)

312. Burst Balloons (Hard)
一道挺有代表性的DP题，complexity是O(n^3)

11.6
64 Minimum Path Sum (Medium)
标准的DP

11.7
706. Design HashMap (Easy)
Hashfunction 用modulo，array store的size最好是prime，collision handling的strategy 用separate chaining 最好写

131. Palindrome Partitioning （Medium)
标准的back tracking，答案上approach2说可以用DP来优化下算palindrome，应该找时间写一下

92. Reverse Linked List II （Medium）
reverse list的延伸，容易写错，我没能在30分钟内过AC，说明自己在短时间内implement好的能力还需提

楼主好毅力！地理大家一起来监督

11.8

300. Longest Increasing Subsequence. (Medium)
用1dim DP的方法来做，对于每一个新的index i，需要check所有小于i的index，所以run time 需要O（n^2)
看到答案有一种更好解法是DP + binary search，
dp array "tails" storing the smallest tail of all increasing subsequences with length i+1 in tails
"We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update."
这样优化后，run time 变成了 O(n logn)


1428. Leftmost Column with at Least a One (Medium)
拿到这道题，先相想出的解法是每个row做bianry search，找出最左边的1的col index，然后再从所有row 中去最小的 col index
time complexity 是 O( (log n) * m)

后来看到答案有一个O（m+n）的解法，从matrix的top right开始寻找01的边际，碰到0向下，碰到1向右，最终current_col + 1就是要找column index，没有1的matrix是个special case要小处理一下，  这是最优解了。

1197. Minimum Knight Moves （Medium）
开始写了BFS的level by level traversal 会有TLE
后来加了visited set来避免重复visit，勉强过了AC
在答案中看到了DFS的解法，简洁又快速, knight 有8个方向的走法，但都是对称的，DFS解法中现将x y取了绝对值, 从（x，y ) 往回move， 只有两种move  (x -1, y -2) and (x-2, y-1), 因为取了绝对值 base case 有点tricky 会有这几个点 (0,0) , （1,1),  (2,0), (0,2), 后三点需要跨越quadrant 而且base moves 数是2
这道题的time complexity是多少？我还有点疑问

68. Text Justification (Hard)
这道题想法不难，关键在于如何写对和写的clean，这题我做得还行，一次过得AC，值得坚持的地方那个在于自己写完后，心理run了几个test case，找出了bug
下面这个代码，从别的答案看到的，值得借鉴，不我最开始写的while loop 简洁得多了

1.                     for j in range(space_total):
   
2.                         row[j % (len(row) -1)] += " "

复制代码

加油！！！

11.9

128. Longest Consecutive Sequence （Hard)
很快的写出了 sorting + sweep的解法，run time 是O(n log n)，第一次submit发现没有考虑到重复元素的情况。
题目的follow up要求 run time为O(n)
每个number 只可能出现在一个consecutive sequence中， 所以一个sequence 一个sequenced地找就好了，我想出的解法是从一个num上下扩展（+1 -1) 来找sequence，官方答案中用了一个小trick，如果num-1不在input list中，那么num就是某一个sequence的起点，这样一来做递增拓展就好

45. Jump Game II （Hard)
55. Jump Game (Medium)
这两道是LeetCode老题了，可惜我一上来还都只想到了O(n^2)的解法，O(n)的解法是通过greedy来判断需不需要jump，希望以后再碰到能想起来最优解吧。

lz加油！！！

11.10

124. Binary Tree Maximum Path Sum （Hard）
虽然是hard题，但是套路和其他的bianry tree的题目差不多，通过post order traversal来寻找max sum path，选取max sum path具体要breakdown这4个cases：左子树的path + node， 右子树的path + node，左子树path + node + 右子树path，只有node。这里左右子树的path并不是子树的max sum path，而是一个能链接node的max sum path。在implementation时候，官方答案用了个小trick：如果子树path sum小于0，则不用考虑。

140. Word Break II （Hard）
写了一个bottom up的DP approach，但是会TLE，看到官方答案里说，这个approach 需要加个condition来bypass。不知道为啥top down dp approach就不用加condition，明天写一下

11.11
今晚本来想做做basic calculator系列，可惜没想出来解法，觉得脑子有些懵，就做了三道easy题划个水啦

412. Fizz Buzz
680. Valid Palindrome II
70. Climbing Stairs