Coding Notes

分享我的代码练习（主要是为了方便自己以后参考），以下只列举一些个人觉得比较好的题目，会不定期增删。

算法 Algorithm

1. 深度优先搜索 Depth-First-Search
   • LI0408 First Common Ancestor：用递归写 DFS 的简洁性。
   • L0322 Coin Change：同样是动态规划，要因地制宜的考虑状态转移的方式。DFS 可以更快的接近目标。
   • L0563 Binary Tree Tilt：后序遍历。
2. 广度优先搜索 Breadth-First-Search
   • L1162 As Far from Land as Possible：一个层序遍历的样例。
   • L1036 Escape a Large Maze：层序遍历+找短板剪枝。
   • L1345 Jump Game IV：遍历后不需要再遍历的备选项及时删掉，可能可以把时间复杂度降低一个幂次。
   • L2045 Second Minimum Time to Reach Destination：改变 BFS 的记忆方式，可以实现同时检索最短路径、次短路径以至第N短路径。
3. 动态规划 Dynamic Programming
   • M210114 Complicate Probability：三维的动态规划，计算复杂的概率问题。
   • M210122 Chocolate Game: 二维动态规划，模拟机票、酒店的最优定价模型，计算最大期望收益。
   • L0638 Shopping Offers：1）用 cache 的装饰器来简化 DP 的编写；2）更重要的是体现了合理剪枝的威力。
   • L0132 Palindrome Partitioning II：两次动态规划，第一次用来做预处理。
   • L1815 Maximum Number of Groups Getting Fresh Donuts：状态压缩的动态规划（DFS、位运算、状态压缩）。
   • L1994 The Number of Good Subsets：位运算、状态压缩动态规划、大整数。
4. 回溯法 Backtracking
   • L0044 Wildcard Matching：体现了回溯法在正确的剪枝思路下的简洁和效率。
   • L0115 Distinct Subsequences：优化递归的效率可以从转成循环+数组开始考虑。
   • L1219 Path with Maximum Gold：回溯的时候调用变量是拷贝而非引用，可以利用这一特性巧妙地记录回溯路径（此外此题还有关于搜索路径的剪枝）。
5. 线性规划 Linear Programming
   • M210211 Filatoi Riuniti：线性规划及敏感性分析的经典例题。
6. 二分查找 Binary Search
   • L1760 Minimum Limit of Balls in a Bag：二分查找的实际应用。查找的逻辑不一定是简单的数值比较。只要有目标函数、序列有单调性，都可以二分查找（其他相关：L0354）。
7. 滑窗 Sliding Window
   • L0995 Minimum Number of K Consecutive Bit Flips：数组长度 N，窗口长度 K。纯模拟操作 O(NK)，优化成滑窗则变为 O(N)。
8. 双指针 Two Pointers
   • L0011 Container with Most Water：双指针重要的是想清楚指针移动的规则，有时并不会很直观，需要一点推导。

数据结构 Data Structure

1. 数组/矩阵 Array/Matrix

   • M210116 Monte Carlo：通过矩阵运算极大的加速大规模模拟（要求运算逻辑可向量化）。
   • L1774 Closest Dessert Cost：快速且占用小地枚举所有子集。
   • L0303 Range Sum Query Immutable：通过对数组的预处理（前缀和）来简化需要大量重复的调用。
   • L0304：二维前缀和。

2. 链表 ListNode

3. 并查集 UnionFindSet

   • L1971 Find if Path Exists in Graph：并查集的基本思想是构建/压缩树，使得只需检查两个节点是否在一个树中，就可以判断两点是否连通。

4. 图 Graph

   • L1761 Minimum Degree of a Connected Trio in a Graph：1）用矩阵存储图的信息可能可以高效（但要看情况，反例见L1766）；2）一个好用的排序+剪枝的思路和写法。
   • Uniswap V3 Core：用 Bitmap 来存储一个序列中各个元素的状态，最终用一个大整数即可表示。

5. 堆 Heap

   • L0703 Kth Largest Element in a Stream：一道基础的堆队列题目。
   • L1675 Minimize Deviation in Array ：1）体现了复杂问题的优化首先应从数学本质的角度思考；2）体现了堆队列处理最大最小值问题的时间效率性。
   • L1792 Maximum Average Pass Ratio：Python 内置的 heapq.heapify 可以直接用于多维数组，按数组的第一个元素排序。所以可以轻松维护 [sort_key, value1, value2...] 这样的结构，能够完成更复杂的任务。
     • L1801类似，在仅需要按顺序索引，不需要按键值索引时，可以直接维护一个堆，而不需要另外再维护一个字典。

6. 栈 Stack

   • L1766 Tree of Coprimes：1）栈 + DFS 的样例，也涉及了树的存储问题；2）重要思路：根据数据量选择突破口。
   • L1776 Car Fleet II：一个单调栈的好例子，为以下问题提供了参考：1）什么时候可以用栈？2）怎么从问题中提炼出栈的维护规则？3）栈在 Python 中的正确使用姿势。（其他相关：L0496）
   • L0224 Basic Calculator：用栈以更高的效率实现等价于递归的操作（而且写起来比递归简单）。
   • L1996 The Number of Weak Characters in the Game：列表套列表 + 单调栈 + 空间复杂度优化。
   • L0146 LRU Cache：LRU 缓存机制可以视为一种特殊的栈。

7. 字典树 Trie

   • L0208 Implement Trie Prefix Tree：前缀字典树的基础实现。
   • L1803 Count Pairs with XOR in a Range：字典树思想解决计算问题。

8. 哈希表 HashMap

   • L0705 Design HashSet：哈希集的基本实现。
   • L0706 Design HashMap：哈希表的基本实现。
   • L2287 Rearrange Characters to Make Target String：在 Python 中，collections.Counter 是一个 collections.defaultdict，即可以查询字典中不存在的 key，并返回默认值（对于 collections.Counter 而言是 0）

数学 Math

1. 抽样 Sampling
   • M210216 Poker Probabilities：在做模拟的时候要关注概率分布及动态变化。扑克牌的玩法中多数为不放回抽样，如果直接用均匀分布或正态分布去模拟，就会算出错误的结果。
2. 非线性规划 Non-linear Programming
   • M210223 Portfolio Management：用 scipy.optimize 模块求解非线性的规划问题。需要考虑可行边界。
3. 离散规划 Discrete Optimization
   • M210323 Dellmar Supply Chain：将逻辑运算（非线性的）转为线性问题的范式，从而能够使用线性规划。
   • M210410 Discrete Optimization Assignment：非线性约束转换为线性约束，其实就是把边界画出来，用直线去拼出这个边界。通常需要涉及创建一些中间的线性变量。
     • 此外，只要不涉及决策变量，都可以先做一些预处理。恰当的预处理可以显著减小后面约束的复杂度。
4. 因数 Divisor
   • L1819 Number of Different Subsequences GCDs：一个数组可以表示 nums[i] = gcd * rel_prime[i]，gcd 是数组 nums 的最大公约数，rel_prime 是一个最大公约数为1的数组。
5. 等差数列
   • L0390 Elimination Game：数学的角度思考问题，并不一定是解析解，也可以是数学简化问题（抽象）+模拟的思路。
6. 博弈问题
   • L0390 Cat and Mouse：动态规划解决博弈问题，清晰的逻辑思考是关键，准确全面的识别出边界状态和结束条件。
   • L2029 Stone Game IX：博弈问题往往可以通过归纳变成极其简单的问题。虽然实际情况是复杂的，但规则是简单的，所以往往可以将实际情况化简讨论。
7. 贪心
   • L0334 Increasing Triplet Subsequence：贪心算法的一个迷你样例。
8. 概率
   • M220325 Conditional Distribution：可视化的呈现条件期望和条件方差的影响。

数据处理

• 用 Pandas 构建平衡的面板：M210712-balanced-panel
• 用 Pandas 构建不平衡的面板：M220806-unbalanced-panel
• 在 Pandas 中将列表元素分配至多列（Link）
• 在 Pandas 选择多个范围的列（Link）
• 滚动匹配序列特征：M211123-rolling-match-pattern
• Numpy 加速运算：M220411_accelerate_numpy
• 迭代替换字符串：M220814_finditer
• 异步：M220827_asyncio

其他参考

• 拉不拉东算法与数据结构全教程（Link）