刷题+周赛记录

前缀树 + 树状数组专题Day 2

Contest:
Leetcode秋季杯: 443/8176 (2720人通过第一题) 过了三题
LCP 39. 无人机方阵: 6min greedy
LCP 40. 心算挑战: 33min OA里做到过 细节比较多 greedy
LCP 41. 黑白翻转棋: 50min 暴力模拟 写的繁琐了

Weekly contest：2题  6845/12179 预计掉20分
5867. Reverse Prefix of Word: 5min
5868. Number of Pairs of Interchangeable Rectangles: 这题失误了，由于多种原因没注意到返回值是long，花了1h10min，提交了十多次，就卡在ans溢出问题了。当时2min做出后，最后两个test case没过，考虑double除法精度问题，使用过BigDecimal结果分式除不尽，后用gcd转为分式化简记录，仍然错误。最后想了下使用python过了，这只是因为python弱类型。
其实要相信数据范围和数学，题目中的num范围是1-10^5，两个num相除后的结果肯定在double的16个有效数字内，所以除法精度用double是够的。如果算法都检查不出问题，那么只能出在算法到结果的输出上了，我确实考虑过这点，检查了题面有没有提到答案过大要mode，结果没有，就排除掉这种可能性了。下次要认真看返回类型。

5869. Maximum Product of the Length of Two Palindromic Subsequences: 最后15min没做出
其实是状态压缩后暴力校验可能性得到最大长度就可；要相信数据范围len=12，2^12种state，当dp记录生成后，两层for用&运算校验不重叠的最大值即可。但是卡在了如何生成dp记录上，我用了dfs生成细节没考虑到，而实际上数据范围不大，10^4用O(n)算法生成每个state绰绰有余，也就是递增state，然后双指针左右校验是否palidromic即可。

Code challenge:
678. Valid Parenthesis String: 没做出，暴力dfs失败；题解有dp，栈，贪心；greedy思路是两个变量记录待匹配的左括号可能的最小值，待匹配的左括号可能的最大值。从左向右遍历，当遇到左括号，两者递增1；当遇到右括号，考虑可能性，需要花费一个左括号去匹配它，如果最小值已经为0了，那就不可能再取一个括号，所以保持不变，否则减一，如果最大值减去1后小于0，证明该结构已经不可能平衡了；如果遇到*，最小值逻辑和上面一样，最大值是+1，*作为空串的状态是implicit的，哪里需要就用在哪里。最后校验最小是不是等于0 。

前缀树 + 树状数组专题Day 3:

新题：3 med 4 hard

440. K-th Smallest in Lexicographical Order (hard)： 40min 没做出；原来想preorder遍历，但会超时，只能用log(n)解法；题解是巧妙地计算出了任意前缀下的挂载的节点数，通过上界、前缀起点和后一个前缀起点之差diff，O1算出k是否存在该前缀下。p指针指向当前是第几个数，cur代表当前前缀的数。如果diff + p 大于 k代表，k在该前缀下，那么*10确定该前缀，继续确定后续的前缀，如果不存在，利用算出来的diff，移动到后一个前缀并更新当前指针。

315. Count of Smaller Numbers After Self (hard): 7min没想出 直接看题解了；题解里有BST解法，node节点中维护count，归并解法，树状数组，线段树解法； 学习了如何离散化原来的非单调可重复序列到去重排序序列，保持原有偏序性并记录bucket no和原数的映射关系。这样就转为了单点更新的区间和（前缀和）问题，使用Fenwick Tree 60行左右即可。

493. Reverse Pairs (hard): 50min 树状数组 离散化 + 树状数组 + 倒序更新 对每个i 去找j的个数 j = (int) Math.floor(num / 2.0 - 0.5) 时间花在推上面这个公式了，其实拿笔算下不等式就出来了。。

327. Count of Range Sum (hard): 30min 暴力枚举前缀和+树状数组  超时；问题是对于lower<a[j] – a[i] < upper没进行优化，如果当前的是a[j]可以转换为a[i] – upper < a[j] < a[i] – lower，求这样的i的个数通过树状数组是可以O(logN)得到的。难点在于要提前进行离散化，提前将需要统计的值保存下来，即presum – upper, presum – lower and presum，然后离散化后它们的偏序关系保留了。最后遍历前缀和，边计算，边update当前的presum到树状数组，这样i，j就不会重复了。

Code challenge:
447. Number of Boomerangs: 前缀和+暴力枚举+组合数

Mock 面试:

1219. Path with Maximum Gold: 12min 简单dfs + backtrack

1834. Single-Threaded CPU: 35min 超时；后面又想了下30min做出来了，先sort再用堆记录available的任务，模拟时的细节较为复杂，总结为一直添加小于等于时间线的任务，若时间线未到时快进到第一个任务时间，否则执行一个任务

lz考虑加入刷题组织吗？ 我们很需要你这样的人才！discord: https://discord.gg/xJzQRCZG 我没打算跳槽所以每天会发一道题在群里，其他时间来学OOD和System Design。

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

嘿嘿 谢谢 加了 多多交流

前缀树 + 树状数组专题Day 4:

周赛出来了: 1598 掉了22分

新题: 1 med 2 hard

673. Number of Longest Increasing Subsequence (hard): 30min 超时；题解有dp法O(n^2)和树状数组法O(nlogn)；dp法比较特殊，维护两个一维dp；树状数组也是有一定技巧的，简单记录前面有多少个数比当前小是不行的，区间的数抽象为一个tuple，合并区间时的逻辑其实和dp法是一样的，所以也需要两个维度的信息：最长长度 和 出现次数，然后对前缀和的后序节点都更新

6. ZigZag Conversion(med): 30min 找规律 内部错误 看不到具体test case 公式应该没问题。。

699. Falling Squares (hard): 20min 做到一半不知道线段树区间更新的模板了，用了307题的模板最后提交出错了，原理已经掌握，懒加载后面再看吧

前缀树 + 树状数组专题刷完了
接下来做facebook tag下没做过的题 或者 其他专题

采样专题  Day 1

新题: 5 med

528. Random Pick with Weight: 10min Weight Sampling: prefixSum + binary search找的插入位置下标即是按权值采样得到的值

497. Random Point in Non-overlapping Rectangles: 15min Weight Sampling错误解答；看了题解后发现，问题在于前缀和维护的增量应该是rect内包含的点的数量，也就是说delta = (h + 1) * (w + 1)，然后再在该rect内随机选择

382. Linked List Random Node: 9min bug-free O(1)时间 O(1)空间 每次选取大样本的等大小子集 进行random选择即可 如果不够划分需要返回头部继续；题解的Reservoir Sampling是通过每次用1/N（n为当前遍历数的个数）概率保留当前数，使得概率均摊到了每次random选择上。这里隐含的是保留的过程中，如果capacity满了就是替换。就像水满了就会溢出，继续加水，新水分子有概率替换旧水分子。蓄水池抽样更为通用。

398. Random Pick Index: 7min map统计法 O(n)空间 O(1)时间 ；2min Reservoir Sampling O(1)空间 O(n)时间

470. Implement Rand10() Using Rand7() Rejection Sampling 首先有一个结论：对于任意的randX(), randY() 生成[1, Z]的值，那么由填表法可以得到randXY() = (randX() - 1) * X + randY()；本题我们知道Rand7，也就能实现Rand49，然后对于10来说40是一个49以内的最大倍数，所以我们可以每次随机生成后拒绝掉大于40的数，然后(x - 1) % 10 + 1就能等价于Rand10了

478. Generate Random Point in a Circle: 10min Rejection Sampling 生成外接正方形 然后拒绝出界的

519. Random Flip Matrix: 25min Rejection Sampling并不是本题最优解； 最优解是用一个no表示当前未用的节点数 用一个Map维护交换映射关系 每次生成后 把这个节点交换到当前末尾 这样就一定能找到合适位置；算法最多调用O(mn)次random 并且时间复杂度也是O(1)

至此抽样专题完成

总结下，Weight Sampling的通用解法是prefixSum，记录总和Sum然后每次randNum后binarySearch插入位置即可，这里的值不一定是简单意义的数，也可能是形状内的点的数量等；缺点对于double\long都会溢出的数，不可采用prefixSum，需要使用其他方法
Reservoir Sampling需要每次都使用random决定是否保留替换当前数据流的数，适用于内存小但数据量很大情况下的sampling，缺点需要需要读完整个流，每步都需要random
Rejection Sampling是一种将大的随机分布空间缩小的技巧，这样就能简化问题了，缺点random次数更多

接下来复习除开DFS, BFS, backtrack外的图算法，近期有OA估计是考图论的
Glossary:
Weight Sampling - 按权值采样
Reservoir Sampling - 蓄水池采样
Rejection Sampling - 拒绝采样

图专题 Day 1

1584. Min Cost to Connect All Points: 30min Kruskal 算法也就是避圈法 需要用UnionFind判断两点是否已经可达；UnionFind的实现细节要注意；Prime也可以，扫描线 适用dense；堆优化 二叉堆、 fabonacci堆 适用于sparse

1901. Find a Peak Element II: 15min 搞明白162. Find Peak Element就不难了；二分法的理解要透彻，二分体现在每次判断后能知道，要么一个区间一定存在ans 然后保留它；要么一个区间一定不存在ans或者可能存在（但另一个区间一定存在）然后排除掉它。不仅仅是单调性，更可以是和左右邻居的关系，还可以是0、1的一种性质，也称之为二段性。

743. Network Delay Time: 16min 复习了dijistra后就不难了 1个bug 节点编号忘记-1了；这题是dense graph用扫描法得当前最近点更快

787. Cheapest Flights Within K Stops:  15min 写了个Bellman-Ford的优化版SPFA算法，但调了1小时；bug是入队记录每次都要清空，否则当前层还未更新到的点下次再次被更新的情况会记录不到；Bellman ford是动态规划的思路 求解单源最短路的算法 时间O(VE) 空间O(V) 但视情况可以做以下的优化: 1. 如果没有k的限制，可以在原cost上直接继续计算，不用prev，直到两者相同就可以退出了； 2. 通用优化即SPFA：用队列保存上次更新cost变小的点 这样就不用对所有边扫描

Insert(index, val) at(index) delete(index) 都小于O(n)的高级数据结构:
1.        Block List - 块状链表 O(sqrt(N)): 基于暴力分块降复杂度的思想，需要实现裂解与合并操作
2.        Rope – 节（内部是avl）O(logN) 也是块状链表 但是内部是AVL更快了
G++<ext/rope> stl库中有块状链表的模板
以后有空想写个java版的block list 现在太忙了
3.        skipList blocklist是弱化版的skipList
4.        zipList Redis用的一种结构 可以压缩空间

Std:deque可以支持上述操作 但是insert、delete只能在头尾实现O(1)，它的内部实现是分块vector

Glossary:
MST – Minimal Spinning Tree 最小生成树
Kruskal - 克鲁斯卡尔算法/避圈法 (MST 算法 适用sparse)
Prime – MST 算法（堆优化适用sparse，扫描是dense）
Dijkstra – 最短路算法（positive weighted适用带非负权的图；堆优化适用sparse，否则dense）
Bellmen-Ford – 最短路算法（非负环即可）
Shortest Path Faster Algorithm – SPFA (Bellmen-Ford 优化)
Block List - 块状链表
Rope – 节（C++模板 块状AVL树）
Skip List – 跳表
Zip List – 压缩链表

明天继续学Floyd warshall、Tarjan/Kosaraju、A*（看看再说 不知道有没有必要）

图专题  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，需要一些策略去优化它