刷题+周赛记录

dada9512 发表于 2021-9-14 01:41
lz考虑加入刷题组织吗？ 我们很需要你这样的人才！discord: https://discord.gg/xJzQRCZG 我没打算跳槽所以 ...

请问能再发一下链接吗，invalid了

要不考虑下残酷组织board.cruelcoding.com/rules.html，周赛氛围极其强。

周赛从上次更新打了两场：
一场只做出一题：掉了20分，现在1713
这周的还可以三题，1200/11000，T4写了半天超时
另外参加了一场lucid的hackerrank竞赛，拿了100刀奖金

周赛:
5914. Smallest Index With Equal Value: 1min easy
5915. Find the Minimum and Maximum Number of Nodes Between Critical Points(med): 8min 注意边界条件 WA了一次
5916. Minimum Operations to Convert Number(med): 30min BFS，一开始用的DFS做的，发现有问题再改的，应该一开始就明确好；自己写麻烦了
5917. Check if an Original String Exists Given Two Encoded Strings: 50min超时，我的思路是暴力枚举所有长度的分割法，然后生成对应字符串校对；看了题解是类似编辑距离的dp题，dp[i][j]代表的是可能的长度差集合，然后类似通配符匹配，可以进行状态转移了，如果dp[m][n]存在0则意味着同源

Facebook Tag:
269. Alien Dictionary(hard): 做了两个小时，其实是个build graph + topological sort的题，edge case很多
314. Binary Tree Vertical Order Traversal(med): 12min 节点标记法+BFS，也是一开始用的DFS然后改的，应该一开始就考虑清楚

现在775题，415 med 107 hard，10月份一天一道都没坚持住。继续刷题，面试还在进行中。。

silentstorm 发表于 2021-10-8 13:01
请问能再发一下链接吗，invalid了

新链接 https://discord.gg/dfAhr8T8

上次更新后加了44分，最近一场周赛结果也出来了，加了12分。现在1769分
上周周赛三题 排名2000/12000
做的比较慢，T2卡了很久

2062. Count Vowel Substrings of a String: 11min 是个easy题数据规模很小；但不知道为什么当时用了sliding window，如果直接暴力应该4min能做完

2063. Vowels of All Substrings: 1h这是一道数学题；一开始用的prefixSum但time complexity是O(n^2)超时；最后发现因为统计的是整体的vowel的总数，substring只是个幌子；所以利用combination直接算单个vowel的contribution，然后累计即可

2064. Minimized Maximum of Products Distributed to Any Store: 15min 因为存在条件 minimize the maximum number of products; 是经典的二分答案法

刚面完一个onsite开始赶学校要due的三个project了。。
每日一题和周赛继续坚持，tag题现在因为拿不到大厂面试，从来没考到过我不会的算法（要么是OOD要么是Top100里的经典题要么是逻辑复杂的场景题），当然也不意味面试都过了。。只是边际效用来说，继续刷新题用处不大。如果后面有希望拿到大厂面试再集中刷tag吧

上次周赛结果出来了，现在1788。希望下个月能拿到Knight badge (1860分左右)
这周的周赛正常发挥，40分钟3题完成，1800/12000。可惜T3 WA了两次。。预计加12分

5930. Two Furthest Houses With Different Colors: 3min 暴力即可

5201. Watering Plants: 6min O(n) prefixSum + 模拟

5186. Range Frequency Queries: 27min 一开始没有仔细考虑时间复杂度 用了每个下标+对应所有数字的freq的map，导致out of memor；后面想了下可以从出现元素的角度出发记录出现的下标和次数；也就是二层map，内层map是treeMap这样可以二分得到前缀和

5933. Sum of k-Mirror Numbers (hard): 暴力打表失败 超时；现在知道了应该优先构造k base的回文串 然后去校验base 10的情况；或者可以先算出10的回文串，但要使用更高明的构造法，我是用的暴力法。。

第268场周赛结果出来了，加了17分，现在1805，终于到1800+了！基本秋招上岸了，还没签正式的合同。这周除了做项目就没什么事情了，打算把过去提交过但是没通过的题review一下，大概17道。这周两场竞赛都会参加，开始冲刺Knight了。

最近就做了这道题:
423. Reconstruct Original Digits from English: 23min 超时；看了题解明白了需要用高斯消元法，也就是识别出特殊字母然后统计后直接解方程就可以得到了；为了让code更易implement可以构造一个合法序列依次处理0-9的英文

周赛:
双周赛睡过了半小时，没参加。。
周赛4题都做出来了，T4难度不大，排名1000/1100，预计加30分。

5938. Find Target Indices After Sorting Array: 2min

5939. K Radius Subarray Averages: 20min 失误了 5min写完 WA了三次；滑动窗口即可，一开始写完后过了样例就没有仔细过一遍例子，结果下标映射找错了，还没发现越界问题。。一定要过边遍例子

5940. Removing Minimum and Maximum From Array: 20 min 四种情况都枚举下；代码写得比较冗长，花了点时间

5941. Find All People With Secret: 28min 按时间排序后，按同一时间建图dfs即可；没有用union-find是因为写起来麻烦+算了下稀疏图dfs时间复杂度也没太差；dijkstra最短路也可以，greedy维护一个heap queue，dist记录每个点的最早知道秘密的时间，随后将该时间点或者晚于该时间点的后的点入优先队列；最后被访问过的就是答案

新题: 3 hard
2081. Sum of k-Mirror Numbers (hard): 折半搜索法，通过构造10进制回文串，然后校验k-base的情况；难点在于回文存在奇偶，所以要选选定一个固定范围，先生成奇数的回文串，全生成完了然后再生成偶数回文串，再move on下一个固定范围。这样保证了序列生成的严格升序

458. Poor Pigs (hard): 想不出；其实是一道信息论的题目。类似的有一道二进制老鼠题，区别在于本题可能可以继续实验。从信息论的角度来说，原来的问题，对于N个bucket需要确认ceiling[log2(N)] bit的信息（十进制编号转二进制），而每个动物因为test的结果是死/生，二种可能。也就是说每个动物可以提供1 bit的信息。所以答案就是需要ceiling[log2(N)]个动物。

而本题存在多次实验的可能，也就是每个动物提供的信息不再是1 bit，而是大于1 bit，这是因为如果一个动物没死还能继续test。根据复杂的证明，存在n次测试，则每个动物提供的是(n+1)进制的一个基本单位（就像bit对于二进制），那么也就是说，求X * log2(n) = ceiling[log2(N)]（log2(n)将n进制基本单位转为二进制信息；一个码元可取m种离散值，则该码元能携带log2(m)位二进制信息)。
最终得到公式X = ceiling[log2(N) / log2(n)]

786. K-th Smallest Prime Fraction(hard): 10min 直接暴力做就行；题解更优的做法是用多路归并来做，或者二分+双指针

Daily challenge:
400. Nth Digit: 25min 暴力过了；看来题解发现可以用数学法避免枚举，利用除数和余数

尝试过没通过的题:
2048. Next Greater Numerically Balanced Number: 之前某次周赛的题，当时dfs构造花了很久；现在重新看发现数据范围很小10^6，初始化时打表或者直接暴力枚举算都是可以的

2029. Stone Game IX: 之前某次周赛的题，博弈论分类讨论，不是博弈dp而是找规律题，需要认识到这是在构造序列；而且只有两种合法序列的可能；所以题目转为讨论合法序列的长度是否是奇数；optimal 策略体现在先手的人可以选两种开头方案

上周结果出来了，加了39分，现在1844，还差十几分到Knight。

等会准备下打周赛。

400. Nth Digit: 25min 暴力过了；看来题解发现可以用数学法避免枚举，利用除数和余数

之前尝试过的题:
2048. Next Greater Numerically Balanced Number: 之前某次周赛的题，当时dfs构造花了很久；现在重新看发现数据范围很小10^6，初始化时打表或者直接暴力枚举算都是可以的

2029. Stone Game IX: 之前某次周赛的题，博弈论分类讨论，不是博弈dp而是找规律题，需要认识到这是在构造序列；而且只有两种合法序列的可能；所以题目转为讨论合法序列的长度是否是奇数；optimal 策略体现在先手的人可以选两种开头方案