刷题+周赛记录

更新下，终于拿到Knight了，多谢这几次周赛不是很难
竞赛分:1868
题数807: 259 easy 436 med 112 hard
晚上准备打周赛

上次说的鸽了，打了上周的周赛。3000多名，估计掉10分，接下来继续保持每天三道新题+分类复习。
Code challenge:
825. Friends Of Appropriate Ages: 30min没做出 排序后binary search；也可以利用年龄的范围较小，通过bucket降低复杂度，将内层循环改为遍历该年龄的bucket，所以O(n)；也可以排序后双指针来做

272场周赛
2110. Number of Smooth Descent Periods of a Stock: 5min sliding window或者dp 可以直接优化为O(1)时间复杂度

274场周赛
2127. Maximum Employees to Be Invited to a Meeting(hard): 没做出 核心在于分析出两种情况可以产生最大答案；greedy + dfs + dp；1. 找到最大的环 2. 找到所有二元环 并计算出其左右的最长链，最后每个环求和（必然不会重合，因为每个人只能喜欢一个）；有向图找环用的dfs和dp进行缓存，dp记录的是相对于一个固定点，该联通图内上的点记录它的位置，其中利用了timestamp来标记是不是访问过的，如果next本次被访问过了，dp记录时要减去next，同时意味着一个cycle形成了；O(n)时间复杂度

1/4/2022 - 1/7/2022
结果出来了，掉了13分，现在1855。这周的双周赛和周赛都打。

Code challenge:

71. Simplify Path: 12min deque 模拟即可

1614. Maximum Nesting Depth of the Parentheses: 15min 写复杂了；因为字符串必然合法，直接统计最大的balance factor即可

846. Hand of Straights(med): 15min greedy + 模拟

1576. Replace All ?'s to Avoid Consecutive Repeating Characters: 30min 写复杂了；greedy得考虑可以直接一边遍历一遍修改，只用三个变量记录即可

913. Cat and Mouse (hard): 不会做；看了一遍题解，是graph + 记忆化dfs博弈问题，先将同步的追逐拆分成回合制，然后将最优策略体现出来：从当前位置考虑  1. 要么能到达必胜状态 2. 要么到达不了，但是能到达必和状态 3.否则这是个必败状态；可以不区分猫和老鼠；dp[mouse][cat][turns] 三维dp记忆化

1/8/2022
双周赛还可以(700/15000)，估计能加30分左右。周赛正常发挥吧(1500/16000)，估计加10分，T2卡了很久也没做出来，是系列题的第二题，其实可以去看下第一题是怎么做的。

Biweekly Contest:
5960. Capitalize the Title: 6min 花的时间长了点

5961. Maximum Twin Sum of a Linked List(med): 5min 暴力

5962. Longest Palindrome by Concatenating Two Letter Words(med): 10min Greedy+hash table统计

5931. Stamping the Grid(hard): 70min 没做出；一开始就想到了prefixSum 但是如何记录合法点没想通 必然会超时；看了题解发现，可以记录邮票的点，这样再次使用prefixSum就能解决问题了，时间复杂度O(mn)

Weekly Contest:

5976. Check if Every Row and Column Contains All Numbers: 4min

5977. Minimum Swaps to Group All 1's Together II(med): 没做出 关键步骤是如何计算将所有1聚集到一起的cost；Greedy 维护定长sliding window，size为所有1的个数，然后找到滑窗内最少的0的数量;O(n)

5978. Count Words Obtained After Adding a Letter(med): 10min 我的思路是直接枚举所有可能的生成，然后每个target在hashset找下存不存在；其他的更好的方法是二进制枚举，或者枚举所有target消除一位的结果反向找start

5979. Earliest Possible Day of Full Bloom(hard): 15min Greedy 最大堆模拟 注意细节

2021/1/9

Code challenge:
306. Additive Number(med): 35min dfs + backtrack即可；花的时间有点久

新题:
945. Minimum Increment to Make Array Unique(med): 20min 提示下做出来了 O(nlogn)排序+greedy；存在O(n)解，计数排序法

1031. Maximum Sum of Two Non-Overlapping Subarrays: 20min 前缀和+暴力枚举 O(n^2) 因为区间长度大于等于1 实际计算量不大

256. Paint House(med): 经典的dp题 没想出来 看了题解

1/10-1/15
双周赛加了43分，周赛加了20分。现在1918，终于上了1900分。继续保持，早日上2000分！打了这周的周赛，明天总结下。


Code challenge:
1036. Escape a Large Maze: 40min  思路: 只有当blocked和边界导致source或者target被包围 则他们互相到达不了;如何检查被包围：对两个点进行bfs去检查是否从该点出发最终一定到达边界或者到达blocked;特殊情况：两者在同一个包围圈 则返回true;还有双端bfs法

334. Increasing Triplet Subsequence: 没做出来，看了题解知道是LIS问题的特解； 通用解是dp+二分；而本题3个元素可以线性扫描

1/16
276th周赛1300/20000 预计加20分；T4没做出思考方向错了

Weekly contest：
2138. Divide a String Into Groups of Size k: 5min 模拟

2139. Minimum Moves to Reach Target Score: 7min Greedy；从target出发到1，O(logn)复杂度

2140. Solving Questions With Brainpower: 11min surfixSum or dp

新题:
1690. Stone Game VII：做不出 个人觉得非常难的一道博弈区间dp；dp[i][j]代表alice先手获得最大的point，问题关键在于如何把bob的选择体现出来；通过往下思考一层即可，即本层模拟alice的2种决策，取left，取right下bob如何minimize diff；反向思考也就是分类讨论bob在(i + 1, j)和(i, j - 1)情况下minimize diff的最大值就是alice最优解；而对于(I + 1, j)一个情况来说，他可以选消去left或right，则想到和上次层比较，这个diff就是消去石头的值+对应子问题；至此极小值最大化的问题解决了；这道应该是最后一道stone game，官方说对这道题不满的人太多了，以后没有这个系列了

1220. Count Vowels Permutation: 30min 动态规划 一开始想复杂了 以为要用bitmap；思路：反向考虑aeiou分别能从哪些字符生成 利用上次结果计算本次；每个数组存储的是以当前元音结尾的不同字符串个数 所以最终答案是要求和；注意运算过程中会溢出 必须取余 用long

161. One Edit Distance: 15min 分类讨论 edge case很多；提交了5次才过

147. Insertion Sort List: 35min 没有想到题解的那种方法 做的复杂了；应该记录有序的末端，然后每次直接比较cur和末端，必要的时候才从头找插入位置

今天继续复盘T4

1/17 – 1/21

276th周赛加了25，现在1943

Code chanllenge:
539. Minimum Time Difference(med): 排序后遍历 注意substring的参数含义 (表示index，1个参数时代表右边界，两个参数时，第一个是左边界，左边右开)

新题
219. Contains Duplicate II(med): 10min sliding window一下

1716. Calculate Money in Leetcode Bank(easy): 模拟 也可以数学

2132. Stamping the Grid(hard): 30min 半个月前周赛的T4 自己做了一遍做出来了；朴素思路是2D prefix sum 然后记录可以放邮票的left-up corner 对该map 再做一次2D prefix sum最后遍历检测即可；进阶思路是使用2D difference(二位差分数组) + 2D prefix sum，也就是先通过差分数组记录区域性的数字增加，然后通过prefix sum还原出原来的计数数组（差分记录的是变化的情况，需要还原出原数组才能使用）

1332. Remove Palindromic Subsequences (easy): 10min 没想出；脑筋急转弯 因为只有a, b两种字符 所以最优解就是先检验是否palindromic 然后统计s里a，b字符出现与否 因为每次都可以直接删除全部的a或者b的subsequence 最多两步

等下打今天晚上的周赛

1/22 -1/23

276th 周赛 前三题花了15分钟 这个时候已经2000名了 然后T4最后也没做出 最终3000/17000；预计掉10分

5989. Count Elements With Strictly Smaller and Greater Elements(esay): 5min 写慢了 其实很简单 我的解法细节比较多

2149. Rearrange Array Elements by Sign(med): 6min queue模拟 一开始想用构造法 多花了点时间

2150. Find All Lonely Numbers in the Array(med): 4min 简单统计

T4 明天复盘

新题：
2017. Grid Game(med): 25min O(n^2)超时；看了题解可以优化到O(N)，最大值极小化，枚举状态；思路和优化关键点： 对于first bot枚举转折点 则second bot无需枚举 取一开始就向下 和 最后再向下 两种的最大值即可

1959. Minimum Total Space Wasted With K Resizing Operations (med): 30min 做不出 很难想的一道区间dp；dfs法超时；原理是dp[i][k]记录[0, …, i]上k个分段时的最小cost；可以预计算cost矩阵 整体O(n^2 * k)

2045. Second Minimum Time to Reach Destination(hard): 50min 没做出 一开始用了dijistra 然后去找次优解；发现path的weight是1，可以用BFS解单源最短路问题；BFS超时 没想到合适的优化方式；看了题解，可以通过在queue的tuple存储dist，外部记录两个消息一个是最优解，一个是严格次优解，这样依此更新他们，第二次遇到target时就可以退出了，只有两种情况才会把重复访问过的点加入，而且因为只继续遍历会比之前dist结果小的path，说明不会一直无限循环；这样的话时间复杂度是O(V + E)，空间复杂度O(V)，每个V最多进入2次queue；或者采用visited和log来记录最多两次的条件也可以

一个多月没怎么刷了，2月中旬打了一次周赛，结果还可以，加了10分，现在1940。继续刷题！