1/24~3/24 60天刷题全力冲冲冲

在12月末的时候就开始重操刷题了，上周开始全力刷，身边很多人也都上岸了，哭。这个贴子的目的最终不是找得到工作（当然找到最好啦~），只是享受60天的刷题过程~ 尽人事，听天命，平和心态。

欢迎大家互相监督学习 -> https://github.com/Haixiang6123/lintcode-python

补充内容 (2020-1-23 09:50):
打卡 2020/1/22，开始刷 VMWare 的题 + Follow Up

补充内容 (2020-1-24 14:14):
打一波卡，皮肤过敏搞得昨天晚上都没睡好，3点就起床不知道要干嘛了

补充内容 (2020-1-25 05:57):
今天快点搞完了，晚上吃火锅过年啦

补充内容 (2020-1-27 08:44):
昨天去 SD 和同学过生日了，今天继续~ 还有，疫情越来越严重了，希望大家都平平安安~

补充内容 (2020-1-28 11:57):
过敏真的太难受了，睡也睡不好

补充内容 (2020-1-29 07:18):
今天做的基本是 hard 题，Sliding Window 认真学了一下

补充内容 (2020-1-30 06:03):
今天主要是复习以前的题+follow up 和 related questions

补充内容 (2020-1-31 10:08):
把 databricks 的题和 follow up 写了，还搞了一下午的报税，结果还是没搞好

补充内容 (2020-2-1 07:26):
还是没有 VMWare 的回信，就先找 FB 的题来写写~

补充内容 (2020-2-2 10:21):
今天继续写 FB 的题，明天奖励自己休息一天！

补充内容 (2020-2-4 07:45):
还有3天就 Karat 面试了，所以这三天基本就是复习+leetcode 里 databricks 的题

补充内容 (2020-2-5 10:11):
继续刚 databricks 的题。最近发现过敏好像快没了，刷题的时候总算不会抓耳挠腮了，哈哈哈哈

补充内容 (2020-2-6 11:53):
明天面试，加油！

补充内容 (2020-2-7 10:00):
面试第三题还是没写完，希望可以大哥可以高抬贵手，让我过了吧

补充内容 (2020-2-8 07:21):
今天吧 FB 春招 OA 的 ladder 写完，明天休息，之后打算开展各个专题的训练

补充内容 (2020-2-9 02:31):
今天是休息天，在等车保养的时候复习了两个题

补充内容 (2020-2-10 09:25):
今天开始 DFS 的专题训练，除去 hard 题就剩下 75 题

补充内容 (2020-2-11 11:20):
Databricks 过了第一面，DFS 专题训练要放一放了，明天开始复习 databricks

补充内容 (2020-2-12 12:17):
今天复习了一下 Databricks 的题库

补充内容 (2020-2-13 09:45):
复习一遍 DataBricks 的题库，再总结了前面几题，终于解决了 Skyline Problem

补充内容 (2020-2-14 08:03):
可算把 Databricks 的题总结完了，每个题基本都看了不同的解法，下午有点不想再写题了，要歇歇，明天 Hiking 去！

补充内容 (2020-2-16 08:39):
昨天去爬了 Powells ，巨累，但是今天也要继续写题呀

补充内容 (2020-2-18 03:55):
今天还是写 Databricks 的题，虽然已经写吐了。。。Anyway，明天面试加油！

补充内容 (2020-2-19 11:57):
终于面完了，希望可以给个机会吧~~~

补充内容 (2020-2-20 08:02):
今天把 dfs 的新题都写完了，嘿嘿

补充内容 (2020-2-21 12:21):
收到拒信，还是有点小失落的

补充内容 (2020-2-22 07:13):
虽然收到了拒信，但是微软又来找，真是人生大起大落，希望这次可以上个岸吧~今天开始转向刷微软

补充内容 (2020-2-23 15:39):
今天继续刷题，顺便清理了一下github，新地址：https://github.com/Haixiang6123/leetcode-python

补充内容 (2020-2-24 08:48):
继续写题~明天要不休息一下吧

补充内容 (2020-2-26 12:04):
今天刷了5题~

补充内容 (2020-2-27 08:05):
最近沉迷刺客信条了，haha

补充内容 (2020-2-28 05:44):
今天就写三道吧

补充内容 (2020-2-29 01:54):
打卡

补充内容 (2020-3-1 02:07):
6 题，在家憋得慌，明天想去玩了

补充内容 (2020-3-2 03:26):
三月啦！

补充内容 (2020-3-4 01:43):
早早打一波卡

补充内容 (2020-3-5 03:21):
现在也不知道刷题的意义是什么了，但是也要坚持下去~

补充内容 (2020-3-6 08:35):
美国疫情也越来越严重了。。。加油呀

补充内容 (2020-3-7 07:02):
继续继续

补充内容 (2020-3-8 10:18):
下单了一个 HHKB，太激动了！！

补充内容 (2020-3-10 07:56):
写题啊

补充内容 (2020-3-13 06:41):
等我的 HHKB 等好久呀

补充内容 (2020-3-14 14:49):
到现在为止从12月开始刷题快60多天了，虽然没能完成到3月24号的约定，但是也算完成了60天的挑战了吧。春招快结束了，目前比较大可能去腾讯了，所以我现在希望在前端方面精进一些吧。在此就停了这个帖子了。

加油。集中刷效果好

# 2020/1/22

436. Maximal Square
二维 dp，dp[i][j] -> 正方形边，dp[i][j] = min(top, left, top_left) + 1，注意边界情况 i == 1 or j === 1 return 1

122. Largest Rectangle in Histogram
单调栈，一直保持递增。遇到递减的: heights[stack[-1]] >= heights[i]，就一直弹出一个 prev_height，找到左边界，更新 rectangle -> (i - heights[stack[-1]] - 1 | i) * heights[i]，注意最后要加上 -1，在最后一次将所有都弹出

510. Maximal Rectangle
设置 heights 数组，统计每一列的高度，就可以转换成 122. Largest Rectangle in Histogram 的问题。每一行都做一次 122 的求解，对比最大 rectangle

697. Sum of Square Numbers
判断是否 < 0，判断是否可以开根号，将 sprt(num) 作为 upperbound，从 j = 1 -> upperbound 去找是否存在 i * i + j * j == num，j = int(sprt(num - i * i))

64. Merge Sorted Array
设置 position 指针，两个数组从后往前判断哪个大，哪个大就加入到对应在的 position 位置

6. Merge Two Sorted Arrays
先处理 i < m and i < n 再处理 i < m 和 i < n 的情况，指针一起往前

839. Merge Two Sorted Interval Lists
还是和 Merge Two Sorted Arrays 一样，这次的判断条件是 l1[i1].start < l2[i2].start，然后 push_back。push_back 里要针对当前结果最后一个 interval 的 end 来处理: last.end < start -> 直接 append，否则 last.end = max(last.end, curt.end)

212. Space Replacement
计算 true length = length + 2 * space_counts，调协双指针：index = true_length - 1, i - length - 1，从后往前修改 string

56. Two Sum
Super easssssy，用 dictionary 和双指针（比较麻烦）都能做

608. Two Sum II - Input array is sorted
双指针，nums[left] + nums[right] < target -> left += 1 else right -= 1， == target -> return [left + 1, right + 1]

607. Two Sum III - Data structure design
这里用一个 dictionary 去存 { num : count }，每次要分是否 target - num == num 去判断。和 Two Sum 有点类似，但是这里多了去重的操作，其实大可以将他们变成数组，每次都用 Two Sum 去做，但是这样 worse case 可能复杂度变高了，例如 [2, 2, 2, 2...]

689. Two Sum IV - Input is a BST
中序遍历，遍历左节点的时候加入 target - left_root.val，在遍历到右节点的时候就判断 right_root.val 是否在 node_set 里即可

1797. optimalUtilization
双指针，left 在 A，right 在 B，初始 optimal 是 A[0] + B[0]，每次 A[left] + B[right] 都和 optimal 对比，前提是 A[left] + B[right] <= K and > optimal，如果  > K 或者 right 有重复，就 right -= 1

609. Two Sum - Less than or equal to target
先 sorted 数组，在 A[left] + A[right] <= target 的时候 counts += right - left，left += 1，否则 right -= 1

443. Two Sum - Greater than target
和上题同理，取反即可

610. Two Sum - Difference equals to target
nums -> pairs (nums, i), 排序 lambda x: x[0]，abs(target)，固定 i, j = i + 1 -> n - 1，如果 diff < target，j += 1， > target 就 break，相等就返回结果

587. Two Sum - Unique pairs
注意去重

382. Triangle Count
i: n - 1 -> 0，nums[i] 作为 target，然后变成了 443. Greater than target

57. 3Sum
two sum 基础上包一层 i: 0 -> n - 3，其中 target = -numbers[i], left = i + 1, right = length - 1

58. 4Sum
3Sum 基础上包一层 i: 0 -> n - 4

59. 3Sum Closest
3Sum 基础上每次都判断是否更 closer

doc1. Find Parent
统计每个节点的入度，再去看入度是 0 或者 1，然后加入 results 即可，这里要注意的是 parent 有可能也能成为 child

doc2. Has Common
递归找 Parents，将 parents 都找出来遍历判断是否有相同节点（Parents）

doc3. Highest Parent
递归找 Parents，每次都打擂台去更新结果即可

doc4. Calculator
很简单的 Calculator，在开始之前要加 '+' 来完成最后一次的计算

doc5. Basic Calculator
在前一题的基础上加一个 stack，遇到 '(' 将 result 和 sign 加入，result = 0, sign = 1 相当于重新算 result。遇到 ')' 计算当前的 result，然后算前一次的 sign 和与前一次的 result 相加，再 pop 掉两次

doc6. Variable Calculator
在前一题的基础上加一个 var，遇到字母就 var += char，再加一个 flag 判断当前应该是 number 还是 self.map[var]

doc7. Friend List
用边生成无向图

doc8. Get Department Stat
直接写即可，只要判断存在有不同部门的人就 break

doc9. Friends In One Place
BFS

doc10. Task Order
[0, 1] 先修完 1 再修 0，图里应该是 1 的 neighbors 是 0， 1 -> 0 应该表示 1 的下一步是 0，而不是关系。还有初始化的时候要将入度为 0 的加到 queue 里。

doc11. Enter Exit
enter: 1, exit: -1，每次都计算状态，如果不是 0 就是 mismatch

doc12. Find 3 Times
用 heap 来存时间，再次遍历的时候找 time + 60 的 index，看 index - i >= 3 ? -> 找到，break

doc13. Domain Click
简单的计数，注意要从后往前连接即可

doc14. Longest Continuous Common History
使用 dp，dp[i][j] 表示 user[i] 和 user[j] 前最长的 continuous common history，如果 user1[i - 1] == user2[j - 1]，dp[i][j] = dp[i - 1][j - 1] + 1，这个是长度，更新长度的时候也要更新 right = i - 1，最后 right -> right - i 去 append(user[i]) 即可

doc15. Meeting Room
先以 interval.start 来排序，lambda x: x.start，再比较 intervals[i].end > intervals[i + 1].start ? -> return False

咱俩的时间线和计划一毛一样呀兄弟😆 加油了
全职刷感觉有点慢

lz一天刷这么多?

dejavoilavu 发表于 2020/01/23 13:39:16
lz一天刷这么多?

就是说啊。一天刷二三十道。真的不会吐吗

楼主你是怎么个刷题顺序呀 ？

# 2020/1/22

657. Insert Delete GetRandom O(1)
插入和删除都要判断 corner case，删除是将最后元素提到 index 那，再 pop

954. Insert Delete GetRandom O(1) - Duplicates allowed
不同的是，self.positions = { val: set }，删除的时候每次要 pop index，然后 self.nums[index] = None

426. Restore IP Addresses
dfs，分成 4 个 part，当 part == 4 和 s == '' 的时候加入到结果，每次要判断 int(s[:i]) <= 255

17. Subsets
注意要先排序，每次 start -> len(nums)

1048. Longest String Chain
按 word 长度排序，对每个 word 都做 bfs，其中要用 memo 记录当前 word 的 Longest Chain

1209. Remove All Adjacent Duplicates in String II
使用 stack 去存 {char: counts}，如果 stack and char in stack[-1].keys() and stack[-1][char] + 1 == k 就 pop，< k 就增加 counts。最后 result += char * counts 即可

1047. Remove All Adjacent Duplicates In String
也使用 stack 去 [char]，如果 char == stack[-1] 则 pop，否则 append(char)

102. Linked List Cycle
快慢指针同时走，如果相遇则有 cycle

103. Linked List Cycle II
快慢指针同时走， slow = fast = head，相遇后，slow = head，然后快慢指针继续走，直到 slow == fast，return

380. Intersection of Two Linked Lists
获取两个链表的长度，然后逐次递减，然后双指针同时走，直到 node1 == node2 出现，就是 intersection

384. Longest Substring Without Repeating Characters
dict 记录每个 char 最左边的 index，每次 left = max(left, cache[char] + 1)，这里要 +1 因为cache[char]还是相同的，要过去一个位置，然后对比 right - left + 1

codeyy 发表于 2020-1-23 15:23
就是说啊。一天刷二三十道。真的不会吐吗

其实我大部分以复习为主，有些之前写过了，有一些就是一个题不断follow up 所以解起来比较快

ml3749963 发表于 2020-1-23 16:43
楼主你是怎么个刷题顺序呀 ？

先定个10到20道题，刷完之后每个题不断follow up 就是做里面的 related question，做到没有为止，目前我是这个阶段

dejavoilavu 发表于 2020-1-23 13:39
lz一天刷这么多?

因为基本以复杂和 follow up 为主，大部分都有想法就可以解，当然碰到hard的也会想好久，即使看了答案。如果累了就打一把红警 哈哈