刷题+周赛记录

Day 14:

Review process(90/100)
394. Decode String: 30min 最近mock面试被问过 当时用的divide & conquer O(n^2); 这次用的双stack 还是有些bug O(n)

399. Evaluate Division: 写了1h 没有过全部样例  UnionFind + weight + path compression顺利写出来了，但问题在于union操作的权值更新方程有误 当已经建立数个关系时 不具有一般性的更新公式是有问题的；通用的更新方程是建立在union(x, y)中的x、y已经各自具有与其他变量的关系上得出的公式weight[rootX] = weight[y] * value / weight[x] ；合并两个node，也就是求两个各自对应的root，rootX指向rootY的weight，图像为一个平行四边形，建立在除法等式基础上，利用y到rootY的路径乘积除以x的weight既是两者root之间的权值。

406. Queue Reconstruction by Height: 没做出 需要排序后 利用链表模拟空位 思路是divide and conquer + greedy +脑筋急转弯，如果height不重复，按高度排序后，遍历每个people把他放置在左边有k个空位的地方即可，因为每个people高度都比之前的大，所以放置后必然这些k个空位被更高的人填满了，然后继续分解为子问题，这里体现了divide and conquer 。如果height可以重复，他们的k必然不同，思考是优先放高k的还是低k的，可以想到高k的会依赖于低k，优先低k会有后效性，并且高k的空位更难满足，所以应该优先考虑放高k，这里体现了greedy。最终，按上述规则排序模拟即可；optimal solution 使用线段树log(n)找到插入位置

416. Partition Equal Subset Sum: 6min 2 bug, 0-1 knapsack 特殊情况没考虑好 并且 一开始dp转移错了 倒着枚举weight才能无后效性

437. Path Sum III: 30min 知道是前缀和 但是想了很久 主要思路是在preorder遍历中动态维护从root出发到该节点前的路径大小和次数，把sum路径记录，然后用当前sum去找sum – target的前缀和的路径数量，记录后，进行左右子树递归，递归完成后关键点在于回溯去删除sum路径的记录，这样就确保路径永远是从上到下过来的。

438. Find All Anagrams in a String: 12min 1 bug, sliding window

448. Find All Numbers Disappeared in an Array: 6min 原地交换 或者 利用原数组进行hash都可以

461. Hamming Distance: 3min 可以异或后 不断取最左的1 统计次数即可

494. Target Sum: 12min 1 bug 写完0-1 knapsack后发现有后效性问题 使用滚动数组解决

538. Convert BST to Greater Tree: 6min prefixSum + inorder traversal

Code challenge:
1221. Split a String in Balanced Strings: 2min analyze balance factor即可

Day 15:

543. Diameter of Binary Tree: 12min 转换为最大深度即可

560. Subarray Sum Equals K: 7min 1 bug 应该在计算可能的次数后 再记录当前前缀和 否则结果中会包含空串

581. Shortest Unsorted Continuous Subarray: 没做出；正解 无序子数组中其最小元素可以确定left，最大元素可以确定right；先对每个逆序结构记录最大最小，最后左右双指针找到left，right边界

617. Merge Two Binary Trees: 8min 写繁琐了 任意为空直接返回给上层即可

621. Task Scheduler: 15min 没做出 差几个样例 知道是贪心构造(maxExec−1)(n+1)+maxCount 最后看了答案当贪心填表失效时 总能存在一种没有间隙的填法 所以答案取贪心和任务数最大即可max((maxExec - 1) * (n + 1) + maxCount, tasks.length)

647. Palindromic Substrings: 8min 中心拓展法 1 bug

739. Daily Temperatures: 11min 单调栈 1 bug , stack的api用错了

到这里 Hot100 复习完成，将近20天
按照manicTime的记录，从20号开始到今天，leetcode全部网页花了 60h，写总结花了7h，估计总共花了50h复习这些题。
接下来继续刷之前的分类专题，应该快到前缀树、segment tree、采样之类的题了，面经看到过，还没学过先学下。

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

昨天在做project，已经完成。接下来几天也没有要紧的作业。

新题:  5 med 3 hard
386. Lexicographical Numbers: 一开始自己建了Trie，看了题解知道可以直接preorder途中构造

677. Map Sum Pairs: 10min 要注意的是如果出现过 需要计算delta再去更新

421. Maximum XOR of Two Numbers in an Array: 25min Trie 这里犯了个小错误 一直没debug出；移位运算超过类型长度后会自动取余，移动到取余后的位置。。。

472. Concatenated Words(hard): 30min 最后两个test case超时；看题解发现对每个查询可以记忆化失败的位置 这样就能剪枝了

212. Word Search II (hard): 24min 因为查询操作10^5量级 而单词长度最多10 预先建立Trie树 再搜索

307. Range Sum Query – Mutable: 超时没做出，原来用了差分，后来想想确实没法用；本题第一次学了树状数组binary indexed tree / fenwick tree和线段树segment tree。感觉理解后代码还是可以背并写出来模板的

336. Palindrome Pairs (hard): 47min 做出来了；建立字典树后 对每个word倒序去检查；“abcd” + "xxxbcda" 一种是后者多 多的话需要check剩余部分是不是回文串；"abb" + “a" 一种是后者少 少的话需要遍历字段树从结束部分找任意回文串；空串要特殊处理

Glossary:
Binary indexed tree/Fenwick tree -  树状数组
Segment Tree – 线段树

前缀树 + 树状数组专题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*（看看再说 不知道有没有必要）