刷题+周赛记录

开这个贴主要是为了准备秋招督促刷题同时记录周赛情况。
现在个人情况是按照分类刷了650道左右，但是没有及时复习很多题已经忘了解法，而且之前一直是看的中文题面，为了招聘感觉有必要重新刷一遍。
同时周赛已经进入了瓶颈期，打了4个月一直在1650上下来回，需要巩固。

对自己的要求
1. 用英文题面，开模拟面试刷题
2. 英文默念思路
2. 限制时间: easy 5min; med 15-20min; hard 25-30min
3. 超时做不出的题：除了中文题解，英文题解也要看
4. 周赛每周参加，双周似乎容易上分，最好也参加了

Day 3
两场打下来 双周1题 周赛2题；估计要掉10分

双周赛
5834. Minimum Time to Type Word Using Special Typewriter 距离没想出怎么表示 卡了半小时
现在想明白了，就是26+两个方向之差 再mod

5835. Maximum Matrix Sum 想用backtrack没做出，应该greedy来做。
因为操作次数不限，我们只在乎终态。任意相邻置为相反数可以把负数位置任意移动，最终导致要么全为正，要么将绝对值最小的那个数变为负数。
Time complexity: O(mn)

周赛:
5851. Find Unique Binary String (med): 17min WA2次
转set后 枚举数 再转为补零二进制字符串 后面发现输入规模很小，直接暴力就可以
正解是构造法: Implement cantor's diagonal argument to construct a unique string by setting its character in a position diff with an input string (in any order but cannot use one of the input strings twice)
利用康拓对角线构造(OS、Alogrithm证明学过)

5852. Minimize the Difference Between Target and Chosen Elements (med): 做了1h没过
先用的sort + n-pointer用堆贪心移动min Delta，后面发现小的数走过了后，不能凑上去。过了2/3样例。O(mlogn + nlogm)
转用backtrack，超时只能过1/3 test case, time complexity O(mlogn + n^m)
试图两者结合进行branch and bound，很难定义上下界，没过。。
正解: knapsack dp 相当于暴力枚举 数据范围和空间 70 * 70 * 800, time complexity O(m*n*target)
数据范围的暗示很明显了，但没想到用knapsack dp

Review process: Top100(22/100)
46. Permutations: 4min backtrack 用了set记录used num 但不是最优
Optimal solution: based on swap, at each invoke it products n possibilities, which represents what num after A will be swapped with A (if A swap itself, it means no change).
Time complexity: O(n * n!), O(n!) for backtrack, and O(n) for a copy of the collection
Space complexity: O(n)

53. Maximum Subarray: 10min 没做出来，尝试了sliding window失败，区间dp复杂度过高
是经典一维dp题，follow up的divide and conquer还没看

Code challenge:
789. Escape The Ghosts: 18min greedy 基本时间花在读题和举例子上
Firstly, the data set is 10^4, making it impossible to implement BFS to simulate the game. Secondly, when considering the policy of ghosts, the optimal approach is to get as close as possible to the target point and catch the player.
Only when any ghost's cost to get to the target is larger than player's, the player might win.
As for cost here, it is the sum of abs diff of x and y coordinates between target and ghost or player, called Manhattan Distance.

另外做了美团的一道笔试题: 1h类似856. Score of Parentheses
Evaluate the parentheses expression value. Eg. “()” = 1, “(())” = 2, “((()))(())” = 6
也就是同一层乘 不同层加
Divide and conquer: built left and right to record the freq of parentheses, when reached a balanced point, that is left == right. We are sure that the expression looks like “(x)”, “x” can be anything. So, the subproblem is the value of “x”.
The core code is ans *= 1 + dfs(s, i – left * 2 + 1, i), which divided the problem into subproblem and combine the return value of subproblem.
Time complexity: O(n^2)

Glossary:
Knapsack dp – 背包动态规划
branch and bound - 分支定界
divide and conquer - 分治法
Manhattan Distance - 曼哈顿距离
Euclidean distance – 欧式距离
cantor's diagonal argument - 康拓对角线证明
sliding window – 滑动窗口

review progress: top100 (15/100)
11. Container With Most Water: 20min 前15min花在Monotone stack，最后5min发现单调性切换成two pointer解决
15. 3Sum: 17min two-pointer 10min写完 没有用set去重 使用了while跳过 花了一些时间修bug
17. Letter Combinations of a Phone Number: 8min backtrack 没bug-free 出了3个bug
19. Remove Nth Node From End of List: 9min 写完后发现nth是倒着数的 出了2个bug
20. Valid Parentheses: 6min 写了2个bug。。忘记考虑最后的栈为空也是必要条件
21. Merge Two Sorted Lists: 5min 1个bug 应该return sentinle.next
22. Generate Parentheses: 12min 击败27% 没写出最优解 回溯里有多余步骤还使用了set  应该每层最多回溯2次 一个生成left 一个生成right
23. Merge k Sorted Lists: 7min 忘记考虑输入head为null的情况了
31. Next Permutation: 23min 代码冗余了 忘记了Arrays.sort(nums[], start, end)的signature
思路：从后向前寻找递减结构 则必然对调该结构起点 和 后面大于它的极小值 最后sort结构后面的subarray

newly-finished:
1053. Previous Permutation With One Swap: 调了1h+没做出 看了题解 和Next Premutation思路类似 因为SWAP一次 不用排序
211. Design Add and Search Words Data Structure (med): 15min Trie+DFS bug-free 一开始没注意到’.’ 可以匹配任意
648. Replace Words (med): 14min Trie+OOP beat 70% 1个bug

1. 感觉基本思路还是有的，不过好几题漏看了或者看错了题意，应该注意
2. 发现除了字母外的盲打准确率很低，最好练习下

glossary：
parentheses - 括号
lexicographically - 字典序
Monotone stack - 单调栈
Trie - 字典树

该阶段计划: 继续复习top100 后续按情况刷公司tag 或者 按分类复习
现在题量：easy 230, med 344, hard 81 近期题数应该不太会涨了 除了每日一题和周赛
top100复习进度: 10/100contest: 1631

哇 楼主好棒 很有structure 想楼主学习
有机会可以多交流

Catherine_C1990 发表于 2021-8-21 06:15
哇 楼主好棒 很有structure 想楼主学习
有机会可以多交流

好呀 多多交流 话说这个版居然加不了米。。

Day 2
Review process: Top100 (20/100)

32. Longest Valid Parentheses: 30min 没过
前15min在用left right性质来做，这样O(n) 就行，但只过了60%
后面以为方法错了，转向考虑区间dp。虽然我知道时间复杂写出来和暴力一样都是O(n^3)，但常数稍微低点，所以还是继续写了，最后超时。。
复盘后发现，用left right性质做是可行的。而我漏掉考虑的情况，题解里使用了计数规则相反的reverse order traverse，很妙地覆盖了这个情况。而dp法需要用技巧转为一维dp来做。涉及到下标运算，暂时没细看。

33. Search in Rotated Sorted Array: 25min 没做出
二分本质是利用一种自身或者与邻居的特性，包括单调性或者题意里的特征，根据中点的这个特征去排除掉一定不符合的区间。系统复习需要参考二分的三种模板。后面再专门刷专题吧。这次的问题是没找到一定不符合的区间，因为单调性的区间找得太大了，可能会把正确答案排除掉。

34. Find First and Last Position of Element in Sorted Array: 12min 7min写完 但改了4个bug
基本思路就是写个findInsertLoc，调用两次找num – 1和num。需要注意的是在main要对返回值做各种edge cases的检验逻辑。

39. Combination Sum: 17min 改了2个bug beat 10% 看了题解发现我的回溯思路不太对。应该转为子问题去考虑，也就是直接遍历candidates ，每步都backtrack，target变为remaining sum。这样不会重复是因为每个num是unique的而且我们遍历的顺序是固定的。也就是画出一个搜索树，每条路径都是不一样的。
时间复杂度：上界O(n * 2^n)  n为路径最大长度(target = n, nums = [1]), 2^n是所有组合的可能
Optimize: sort后pruning

42. Trapping Rain Water: 30min 用monostone stack没做出，思路是错误的，应该横向划分积水。做的时候和two pointer法混在一起了。
主要思路：从左到右，找三个高度，来确定一个矩形积水。Monotone stack在这里的作用是快速找到curHeight左边最近的比它低的heightA和heightA左边至少比heightA要高的heightB，然后这个积水就是(I – locB - 1) * (Math.min(heightB, curHeight) - heightA)
而且monotone stack里的数只会进入一次，所以for里套了while循环 time complexity还是ON

Code Challenge
443. String Compression: 9min 1个bug 忘记考虑1不显示了

今天惨遭毒打。。没做新题
接下来准备这周双周赛了