刷题+周赛记录

Day 4
这几天刚到学校比较忙，做个这些天的总结
周赛积分出来了: 掉了32分 现在1599。。。进残酷群就是天天垫底。。

Review process: (23/100)
55. Jump Game: 没想出 是一种带着贪心的动态规划

Code challenge:
295. Find Median from Data Stream： 经典 两个priorityQueue即可

797. All Paths From Source to Target:  backtrack 因为acyclic所以不会成环 也无需记录visited

881. Boats to Save People: 简单贪心+双指针模拟

787. Cheapest Flights Within K Stops： 做不出，正解是动态规划 或者 最小生成树算法dijkstra 或者 任意两点最短距离ford算法

忙的差不多了，明天起来继续复习+晚上周赛

Day 5

Review process(27/100)
56. Merge Intervals:  9min bug-free sort后模拟 注意edge case即可
62. Unique Paths: 9min 2个bug 写了个O(n^3)解法。。 然而实际上在顺序更新dp途中 步数是可以隐含的 所以O(n^2)即可
64. Minimum Path Sum: 8min 1个bug 忘记设置边界不可达了 本题代码还算简单 最好交流证明min path sum必然是移动m + n - 2步得到的 （因为none negative）
70. Climbing Stairs: 10min 3个bug

Code challenge:
1588. Sum of All Odd Length Subarrays: 4min bug-free
preSum + brute-force list right boundary + two-pointer moving left boundary

Contest: 2题 3237 / 12937 应该能上10分左右
5854. Minimum Difference Between Highest and Lowest of K Scores: 2min  sliding window bug-free

5855. Find the Kth Largest Integer in the Array: 17min 就是经典的top-k问题 字符串比较的comparator要注意是长度小的小 一样就是比较字典序 调了一会bug

5856. Minimum Number of Work Sessions to Finish the Tasks: 没做出 先用的Greedy 后面数据范围一看 确实应该是偏暴力的解法 写了剪枝回溯 可惜调着调着睡着了。。。
题解用了状态压缩dp，状压基本是hard难度的题。之前做过状压专题，比如464、691、698、638、473但确实自己没看出来是这类题。。。

Day 6

Review process(32/100)
72. Edit Distance: 27min 算法课学过，转移方程已经很熟悉了，要讲清楚还是有点难的，有些小细节没有注意到；另外 top-down 也就是 dfs + memorize 在本题效率更高

75. Sort Colors: 25min 没做出 基本思路正确 类似荷兰国旗问题 定义两个p0，p1，遇到0时再次交换的条件搞错了，应该是p0 < p1，而且不管是否交换p0和p1都要进1。因为p0，p1维护的是下一个填0或1的位置，加入一个0，也意味着1的下个位置向后移动了

76. Minimum Window Substring: 23min 用了两个map 自定义判断函数 sliding windown + greedy ；改了几个bug，错看了题意，是覆盖即可，可以比原串多
每次判断是否covered需要O(52) 时间，算是常数

78. Subsets: 7min 写完发现不对劲 后面仔细看了下两种回溯的写法：他们在记录到res的条件 以及下一层回溯的进入 是不同的

79. Word Search: 13min 1个bug 带回溯的dfs

Day 7
今天打了moderna比较困。。
Review process(36/100)
84. Largest Rectangle in Histogram: 不会 原来是枚举高度 然后左右拓展的时候能用到monoston stack

94. Binary Tree Inorder Traversal: 非递归没写出来

96. Unique Binary Search Trees: 6min 简单dp

98. Validate Binary Search Tree: 7min dfs

Code challenge:
528. Random Pick with Weight: 25min preSum + binary search 调了下binary search 应该找的地方是插入位置

Day 8
Review process: (39/100)
101. Symmetric Tree: 3min bug-free dfs解法; 13min 1个bug 迭代法

102. Binary Tree Level Order Traversal: 5min bfs解法 bug-free; 4min dfs解法 bug-free

104. Maximum Depth of Binary Tree: 4min bug-free

Code challenge:
1109. Corporate Flight Bookings: 没做出 题解说是difference array 差分数组法
差分的目的是利用前缀和prefix Sum来求出一系列区间操作后，某一个位置数的值；
差分记录的是当前数和前一个数的变化量，这样区间操作如[1,3]统一加3可以在O(1)时间内记录。最后通过前缀和来计算出该数的真实值。

165. Compare Version Numbers: 11min 模拟即可 1个bug

Day 9
Review process(40/100)
85. Maximal Rectangle: 10min 暴力二维dp 枚举端点；看题解后，知道了可以降维成柱形中的最大矩形，用单调栈解

面经题/新题:
1375. Bulb Switcher III：没做出 超时；原来是脑筋急转弯，全蓝 是等价于亮着的灯的最大编号 和 遍历到的灯数 相等

768. Max Chunks To Make Sorted II: 没有思路；是不太明显的greedy + monotone stack

Code challenge:
剑指 Offer 22. 链表中倒数第k个节点: 经典fast slow pointer 1个bug

今天还做了DRW的三道OA题，大致在mid，optimal solution会麻烦点

Day 10:

周赛积分+21，现在1620

Review process(48/100)
105. Construct Binary Tree from Preorder and Inorder Traversal: 12min bug-free 主要时间花在口算下标上

114. Flatten Binary Tree to Linked List: 9min 1个bug

121. Best Time to Buy and Sell Stock: 3min bug-free greedy 类似jump game 也可以说是dp

124. Binary Tree Maximum Path Sum: 15min 三个bug 用了树状数组 空间效率比较低；Tree相关的optimal solution很多都是一个函数集成了很多功能 记录当前 利用返回值又能提供给上层

128. Longest Consecutive Sequence: 8min 1个bug 为空的edge case没考虑到 用了HashSet + 中心拓展法 O(n)

136. Single Number: 2min XOR

139. Word Break: 20min 写了半天剪枝 + backtrack 结果超时 substring的API不熟。。老是算下标会出错；正解是dp，以要分割的字符串为主体，枚举分割点，用set去检查是否存在该word，整体表现为dp

141. Linked List Cycle: 5min 写了几个bug

OA:
做了Citadel的OA，25min解决，一道差分数组 一道背包dp。

还做了codesignal的practice拿了844，感觉还可以。T4感觉是hard难度的类似lc395但是数组里不是字符而是10^4以内的数，暴力枚举+计数器优化了下过掉了，前三题25m内解决了，T4花了35分钟左右。

Day 11

Review process(56/100)

142. Linked List Cycle II: 14min bug-free 想了会怎么找到环的起点 其实就是倒数k个节点

146. LRU Cache: 30min 改了10分钟bug

148. Sort List: 20min 2个bug recusive merge sort; follow up是O(1) space, 需要自底向上用iteration，sublen初始为1，两两合并，然后sublen*2继续两两合并

152. Maximum Product Subarray: 19min 写了个2d dp; optimal是一维+滚动数组优化 O(n) time O(1) space

155. Min Stack: 10min没想到怎么做; 原来是维护一个动态的最小值列表即可

160. Intersection of Two Linked Lists: 12min 1个bug ; 没想到直接把两个节点末尾指向对方头节点。。

169. Majority Element: 2min Boyer–Moore majority vote algorithm

198. House Robber: 4min 简单一维dp

做了codesignal的practice这次是848。。然后又做了正式的exam只有774 两家公司白给了
T4比较难，我倒序后构建了Trie树，但是重复字符串的情况没考虑好。。只拿了70/300

Glossary:
Boyer–Moore majority vote algorithm – 摩尔投票法

Day 12:
昨天偷懒了 玩了一天。。周赛也没打

Review process(70/100)

200. Number of Islands: 5min bug-free
206. Reverse Linked List: 5min recursion; 3min iteration head insert
207. Course Schedule: 11min topological sort, 1 bug
208. Implement Trie (Prefix Tree): 6min 打字题 1 bug
215. Kth Largest Element in an Array: 3min heap；30min 没写出quickSelect 花了1h复习原理
221. Maximal Square: 20min prefix + dp; 20min 正解 dp[j]为该点为right-bottom的正方形边长，没想到可以记录边长
226. Invert Binary Tree:  3min 3 bug
236. Lowest Common Ancestor of a Binary Tree: 30min 时间花在如何保存路径上了; 正解 O(1) space即可 20min 自底部向上；经典LCA问题
238. Product of Array Except Self: 6min bug-free; the optimal solution is O(1) space  
239. Sliding Window Maximum: 21min 最近看过, 还记得是monotone queue, 1 bug
240. Search a 2D Matrix II: 4min bug-free
253. Meeting Rooms II: 17min 之前没做过，排序后模拟过了；10min 尝试差分数组+prefixSum 也能过；optimal solution 对结束时间排序 可以用最小堆代替
279. Perfect Squares: 10min 一开始以为是greedy 后面发现是complete knapsack dp，2 bug
283. Move Zeroes: 15min  没做出 双指针没用好

Mock interview: 最近mock了两场，互相都出的medium题

被问的：
394. Decode String: 45min O(n^2) divider and conquer；也可以用stack
5847. Find All Groups of Farmland，本周双周赛T2（我没打。。）dfs 但犯了个小错误，debug了很久没看出来
823. Binary Trees With Factors: 简单树型dp 但是选择了枚举factor 而不是遍历存在元素检查是否是factor time complexity差了些， 时间复杂度没分析好，应该是O(n^2)
optimal solutio: 因为直接在树型数组（hashMap）上dp会很慢，应该按照下标位置和值进行映射，在一维数组（array）上计算
反馈是解题前可以给出dp转移方程，也就是把解法写到注释里，这样方便interviewer看；还有就是自己感觉自己写题时的交流比较少

我问的：
560. Subarray Sum Equals K:  prefix sum + hashMap
769. Max Chunks To Make Sorted: greedy + 脑筋急转弯
(follow up) 768. Max Chunks To Make Sorted II: 元素范围条件去掉了 并且允许重复元素 需要使用monotone stack
128. Longest Consecutive Sequence: HashSet + 中心拓展（双指针）
421. Maximum XOR of Two Numbers in an Array: Trie 或者 HashSet

Glossary:
单调队列 – monotone queue
字典树 – Trie
拓扑排序 - topological sort

Day 13:

Review process(80/100):

287. Find the Duplicate Number: 10min 没做出; 正解 二分答案法 O(n) 时间检测是否是重复数字 并且能排除掉一半的区间；正解 O(n) 建图 图论 -> 链表找环的入口

300. Longest Increasing Subsequence: 9min O(n^2) dp法; optimal soltuion O(nlogn) greedy + dp 没想起来 关键在于维护各长度的序列结尾的最小元素 这样就能每次加入一个新数 都能尽可能利用它，而且这是递增的，可以二分寻找

301. Remove Invalid Parentheses: 37min 过了，但其实不是最优解，先计算出最小删除次数，然后暴力删除校验去重；optimal solution动态维护left，right和应该删除的left right数量，反过来生成valid的串，这样就不需要做合法性校验了

309. Best Time to Buy and Sell Stock with Cooldown: 18min 一个bug，转移方程并不是最优的，每次计算当天的需要昨天和前天的数据；optimal solution是将冷冻期的计算推后，也就是状态的定义中的处于冷冻期是指的明天是冷冻期，今天的sell导致明天的冷冻，这样的话只需要昨天的数据即可，转移方程更加简便。

297. Serialize and Deserialize Binary Tree: 11min 2 bug 利用preorder traversal + “#”代表null node + “,” as separator

312. Burst Balloons: 两个月前做过 还是不会; optimal solution: 脑筋急转弯 + divide conquer + dp，反过来考虑放入气球，并且是第一个放入的气球，枚举放入的气球，放入后区间变成两个子区间，也就是后续问题继续divide求解，倒序维护dp，确保是区间内最大的积分，最优子结构的条件下选择最大的，这样就能确保整体最优了。

322. Coin Change: 8min knapsack dp, 3 bug，没考虑到0的时候直接返回0，开始的初始条件忘记设了

337. House Robber III: 15min tree-shaped dp, 1 bug 忘记没rob root的最优情况其左右子树也可能没rob root

338. Counting Bits: 没想出来 其实就是简单的数位dp

347. Top K Frequent Elements: 8min 新题 可以转为topK quickSelect是最优解