刷题+周赛记录

图专题  Day2

新题：2 med 2 hard       

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance: 13min Floyder-Warshell 1个bug 注意无向图 建图时需要两个方向都添加

1192. Critical Connections in a Network (hard): 20min Tarjan；学了1h把Tarjan思路大致搞懂了，对于找图里的桥的问题（关键路径），就是在找环，非环上的edge就是桥；思路：定义一个叫时间戳的概念，每个节点的时间戳是其所有邻居（非父节点）的最小值，这样同一个环内的节点都会公用一个时间戳，也就是等价的关系；结合dfs就是一种自底向上的递归，在这个过程中，原始时间戳的来源是parent给的，如果完成这个dfs后，发现自己的时间戳还是parent给的那个，就说明其非父节点和其父节点非可达（如果可达，那么timestamp至少小于等于父节点），这显然就是个桥，加入答案集。

785. Is Graph Bipartite?: 15min 没做出 问题在于没有考虑森林的情况；二分图判定 染色法 寻找contradiction；也可用Union-Find，假设的关键在于点的邻居都在一个集合

1568. Minimum Number of Days to Disconnect Island (hard): 30min bug是判断当前是否是割点的条件是要分类讨论的：1. 若是root 则其children数大于1就是割点 2. 若不是root则其孩子的timestamp要大于等于自身原timestamp（也就是未更新前的）

Tarjan 也有向图强连通分量算法，也是通过timestamp的回溯来标识的，特殊在需要一个stack保存访问的顶点；leetcode上没找到
算法定义中有dfn low，如果只是求桥可以不用具体的两个数组，像强联通分量算法还是需要dfn、low，因为存在stack，需要跨代访问其low，而且需要具体的时间点定义dfn否则答案节点的编号不唯一。否则dfn low可以用一个数组，dfn直接通过递归传递即可。

图就学到这里了，Kosaraju因为Tarjan更优就不学了，A*启发式一般也用不上。
明天起来打双周赛+周赛

Glossary:

Bipartition – 二分图
Bridge – 桥 （无向图中的概念）
Cut Point/Articulation Point – 割点 （无向图中的概念）
Tarjan – 一系列可以解决求有向图强连通分量、无向图中的桥、割点的算法O(V + E)

Facebook Tag Day 1:

新题: 2 easy 4 med
Biweekly contest: 3题 1488 / 9137

5859. Count Number of Pairs With Absolute Difference K: 5min 一开始绝对值式子拆错了 花了点时间 大佬题解说数据范围不大 直接暴力即可
5860. Find Original Array From Doubled Array: 20min 排序后模拟即可，基于贪心的思想从小开始往hashMap放 一个数如果是是偶数且num/2存在于hash表，则一定要使用它去和num/2抵消，然后更新下并保存答案，最后如果还有剩余的数 说明不成立 O(n)；也可以用queue做

5861. Maximum Earnings From Taxi: 1h 一开始在犹豫是不是要用图论，后面觉得肯定超时；写了第一版dp超时，后面意识到可以反过来考虑目的地是由出发地转移过来的，然后通过了；原因是反向记录目的地由出发地过来，这样确保了每个边只会访问一次且每个节点也是访问一次 时间复杂度O(V + E)

Week Contest: 3题 773 / 11277
5875. Final Value of Variable After Performing Operations: 2min

5876. Sum of Beauty in the Array: 13min  后缀最小值 + 前缀最大值 浪费了5分钟在考虑后缀下标的意义上 最后发现可以直接num + 1去找num后的最小值

5877. Detect Squares: 26min hashMap记录 四个点 模拟

5878. Longest Subsequence Repeated k Times (hard): 没做出 调了很久参数 过了200/300样例 最后还是超时了；没注意到n和k的倍数关系就意味着这个pattern串长度最多为7，这样从长度为1枚举然后算就可以了；从小到大枚举校验可以排除掉长度短的里不成立的，例如“a”不成立则“ab”也不可能成立

Code challenge:
650. 2 Keys Keyboard: 6min 数据范围很小 简单dp就过了

今天除了打周赛就在讨论作业项目。。没有刷额外的题。这两场打得还可以，应该能加70分左右。排名刷新了记录，上次进国内400名左右是4个月前了。

Facebook Tag Day 2:

这两天在写project和做OA，明天应该可以刷点题了顺便继续做OA

新题: 1 hard

632. Smallest Range Covering Elements from K Lists (hard): 22min 其实算没做出来 勉强过了；没想到最大堆可以不需要，因为原始条件的是非递减，所以只会越来越大，维护最大值即可；否则更新最大堆的时间复杂度需要O(n)，因为需要遍历去找到最小的pair；minHeap + 维护最大值即可

Code challenge:
58. Length of Last Word: 6min 一个bug 问题在于前后有空格的处理 可以通过trim api来去掉这种情况

今天做了codesignal的一场practice一场正式
Practice 780+，而正式拿了848分。。T4难度差异过大，很碰运气

Practice T4是一道binary search的题，但是hidden testcase一直过不了。现在想想应该是计算精度的问题，如果我使用乘法 而非sqrt后的结果去找二分插入位置，估计就能对了。
正式的T4就是一个sliding window，需要一些策略去优化它

堆 + 计算几何专题 Day 1

现在做的题类型比较杂

593. Valid Square: 10min 2个bug  我的想法就是计算任意两条边看看是否都相等；忘了边长相等的条件；又加个了p1的三条边一定有一对是相等的条件；忘了四个点是相同的情况；加了判定distance非0的条件

630. Course Schedule III (hard): 没做出；题解是贪心+堆，贪心体现在两处，一处是肯定是越早ddl的越紧急但即使早ddl也可能耗时很长，这个留着后面再解决；堆这里用处是O(1)时间提供如果当前时间不够，失败，可以贪心地用现在的课去替换一个以前完成地课，也就是提供被替换的课，这样贪心就能将课程安排得更紧凑；所以是最大堆，存的是课时，然后总时间加上delta 即节约的时间

类似亚麻最近OA的一道题:求全部subarray的max-min的总和，最优解法是hard难度
树状数组记录二维信息max和min 然后统计时累积和 肯定能做 但是复杂度是O(nlogn)。实际存在O(n)解法，参考907题；

907. Sum of Subarray Minimums: 10min 写了暴力的单调队列优化超时；很难理解的一道题 如果模拟是做不到最优复杂度的 需要对每个元素为单位考虑 其自身作为最小元素在子数组中出现的次数。类似计算矩形图。
子数组又是连续的，意味着对一个元素a来说是找到一个left、right使得min(arr[x]) = a, x 属于(left, right)。arr[left]和right显然是比a小的。当顺序计算这个边界时，发现一种不可逆的转变关系。边界可以成为计算元素a。而元素a计算完后，a的边界是比a小或者等于的，而且边界比a更左或者更右，所以a不能成为新边界，也就是说a对后续该问题毫无贡献，可以丢掉。发现这个关系后，就能使用单调性的解法：如单调栈、单调队列。时间复杂度O(n)

Code challenge:
725. Split Linked List in Parts: 12min 模拟

做了Twitter OA算法题很简单，设计题花了30分钟都没写完。。估计没了

堆 + 计算几何专题 Day 2

周赛出来了，加了105分。现在1703。打了半年周赛终于突破1700了，这是一个好的开始，希望能继续保持。

223. Rectangle Area: 想了会没做出；其实可以不用考虑很多复杂情况，直接计算重叠的长、宽然后减去它就行了；使用投影，映射到坐标轴，成为一维区间求重叠问题了；具体来说就是计算区间最大左边界和最小右边界差值

149. Max Points on a Line: 没什么想法；看了题解是用的枚举两个点，将斜率放入hashMap中统计；注意因为除法精度问题，需要使用gcd化简分式存String作为key；写的时候gcd有点问题gcd (a, b) {return b == 0? a : gcd(a, a % b)}

335. Self Crossing: 做不出，计算几何中的分类讨论题，发现了要么一直内卷，要么一直外卷，但情况太多了；参考第一名的题解，直接分成三类处理：1. 持续外卷 2. 外卷后内卷（开始内卷的时候宽度不够，导致两者不会相交，所以直接继续处理内卷内部就可）3.外卷后内卷但是宽度足够碰到外卷的部分，这就要将外卷边界纳入考虑范围了。题解使用了调整的技巧，缩短了外到内的那条边的长度，等价于考虑了外卷的边，然后继续处理

在忙着做OA和project。做了TuSimple OA抽到了很简单的题，20分钟不到就写完了，希望能给个电面。最近也在忙着写文书，尝试申请校内的co-op增加工作经历。

堆 + 计算几何专题 Day 3

新题: 3 hard

587. Erect the Fence: 没有思路，学会了Graham二维凸包算法时间O(nlogn)，先找到最下最左的base，以base点作为基准点比较两个点谁与base点的逆时针极角更小，更小的说明更突出，如果一样需要按照到base的距离排序；特殊情况是当最后一笔连上base时，应该是共线的距离base最远的点优先，所以还需要检查并逆序这些点。然后用栈，对于栈的元素是当前的凸包上的点，随着加入新的点，在新的点、上一个点和上上一个点之间存在类似base排序的基本基本情况，若新的点更优，就会不断pop，淘汰上一个点继续计算，最终栈内的就是凸包上的点。

391. Perfect Rectangle: 没有考虑完全；题解找到了一个规律，如果是完美重叠的，那么四个角上的点只会出现1次，而其他的内部点只会出现2次，因此用一个set来记录这个pair，出现第二次就删掉，最后剩下四个点且构成的矩形面积和小的那些和相等就是完美覆盖，否则不是

164. Maximum Gap: 知道是分块，但没想明白具体怎么做；实际上是利用了数只会在max-min之间的性质，并且我们知道总数为N，所以如果平均分的话，连续的两个数的diff是最小的，为L = ceil((max - min) / (N - 1))。这就意味着在长度比L小的区间即L’=(max - min) / (N - 1)内的差值不会是最大的，这样分别统计区块内的最大、最小。用相邻区块的后者小-前者大就能统计出最大的diff。分块可以降时间复杂度，成为sublinear复杂度。最坏情况下，(max - min) / d 和 N – 1接近，O(n)复杂度。

计算几何专题完成

常用技巧专题 Day 1

新题: 1 med 2 hard

330. Patching Array: 没有想法；倍增法，题解基于贪心维护一个x，[1, x - 1]范围内的数都是可以formed的，如果x也存在于候选数，那么边界可以更新为[1, 2x - 1]，x *= 2；然后在while循环内如果下一个num<=x那就意味着可以纳入考虑，而边界拓展为[1, x + num - 1], 即x +=num，否则就加入x，x*=2

365. Water and Jug Problem: 拓展欧几里得法 找到规律是水的增量是x\y\-x\-y 所以就是在校验z==ax + by能否成立，由拓展欧几里得算法知道ax+by=gcd(a, b)因此如果z是gcd的倍数那么就存在解法

384. Shuffle an Array: Fisher-Yates洗牌算法：遍历每个数，当前下标为i，则随机选取[i, end - 1]之间的一个数和当前数进行交换；这样就能均等产生n!种排列之一了

明天开始集中做project了

本周做个汇报，完成project后周一去打了moderna第二针，休息到周三差不多好了。完成了4个OA，其中2个OA后给了电面。接下来有Robinhood, Palantir, Stripe的电面。明天Rh的karat电面，还在准备中。我发现最好还是做个记录，不然复习效率很低。。

上次周赛只做出一题，排名大致是5000/10000的样子，T1做慢了还WA了，T2漏看了2行的条件，贪心也失败，后来才知道prefixSum+暴力枚举。LC战队赛也打了，一个人做的，只做出了T1…

LC的题本周基本没刷，就把每日一题完成了。

等会打双周赛+周赛+复习Rh的karat面经。

上次周赛掉25分，现在1678

本次双周赛完成了3题，第四题读错了题意，写了个假题，本来是有希望做出来的。排名2000/10000，应该能加20分。
5871. Convert 1D Array Into 2D Array: 3min

2023. Number of Pairs of Strings With Concatenation Equal to Target: 3min 就暴力一个个试

2024. Maximize the Confusion of an Exam: 30min 还WA了一次 滑窗；我的问题是使用了一个数组先分割处理再sliding window的，然而其实不需要预处理，直接统计就行了，导致代码冗长。

周赛13min完成了两题，排名1325/11700应该能涨25分。
5890. Minimum Moves to Convert String: 8min 也就是个sliding window

2028. Find Missing Observations: 7min 模拟一下就可以了 最近做OA有遇到过类似的

2029. Stone Game IX: 写了50min，最后超时还剩1/3样例过不了；我是当成了game theory dp来做的，取模计数，编写了策略再用memo + dfs 模拟，在10^4输入下效率还是不够；题解用的是构造法，本质上是只考虑12来构造最长序列再加0，edge case是如果用来开头的序列到最后还有剩余还可以再用一次

Code challenge:
405. Convert a Number to Hexadecimal: 虽然是easy，难点在于这个数可以是负数，也就是two’s complement形式的，所以一般进制转换用的mod法是有问题的。题解思路是类似digital logic那样4bit一个hex，32位的int分块8块，每块&上0xf即可，要append所以从左到右来执行。

Robinhood面得一般，coding花了半小时才做了一道中等题（没上手做面经题。。有点吃亏），八股回答得还行吧

竞赛分出来了现在 1736 涨了58分

今天完成了palantir的karat，通知过了。但其实题做的并不是太好。。Robinhood ghost了，估计应该二题才能move on。感觉这段时间虽然开始有面试了，但是做题能力还是没有提高反而下降了。主要原因还是最近没有坚持刷题，看面经的时候也没有动手去写。接下来继续做Facebook Tag。大公司也都投了，可以冲刺了。