亲爱的HR:   这个博客网站主要是满足我对互联网的好奇心部置的，购买vps部署服务顺带部署的博客网站。在这里,我用于记录算法学习过程，原先也打算记录更多学习或者生活事情，在准备考研期间也无心经营网站，就仅仅记录算法学习，当个收藏夹一样记录笔记。通过玩耍服务器，我也学习到了web开发，git版本管理，经常游逛github也让我对…

倍增（也叫二分倍增）通常被叫做“树上倍增”，是因为这种方法最初用于树形结构中，特别是在树的上升路径查询、LCA（最近公共祖先）问题等场景中非常有效。在树上倍增的过程中，树的结构天然适合这种操作，因为树是无环的，且每个节点的父节点可以通过倍增逐步上升，直到找到需要的节点或信息。 对于树上的倍增，最常见的应用是处理树中节点到根节点的路径，或者查询某个节…

单调栈我的痛点，不像模板类那样直接套用即可，更多地像贪心一样捉摸不定。 求最短 https://leetcode.cn/problems/next-greater-element-i/description/ class Solution: def nextGreaterElement(self, nums1: List[int], nums2: …

http://blog.csdn.net/ac_gibson/article/details/41624623 一. 巴什博奕（Bash Game）： A和B一块报数，每人每次报最少1个，最多报4个，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。 其实如果知道原理，这游戏一点运气成分都没有，只和先手后手有关，比如第一次报数，A报k个数，那…

MOD = 1_000_000_007 # a @ b，其中 @ 是矩阵乘法 def mul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]: return [[sum(x * y for x, y in zip(row, col)) % MOD for col in zi…

O(n)时间处理查询回文串问题 # 将 dfsStr 改造为 t，这样就不需要讨论 n 的奇偶性，因为新串 t 的每个回文子串都是奇回文串（都有回文中心） # dfsStr 和 t 的下标转换关系： # (dfsStr_i+1)*2 = ti # ti/2-1 = dfsStr_i # ti 为偶数，对应奇回文串（从 2 开始） # ti 为奇数，…

https://leetcode.cn/problems/construct-string-with-minimum-cost/solutions/2833949/hou-zhui-shu-zu-by-endlesscheng-32h9/ class Node: __slots__ = 'son', 'fail…

字符串哈希, 一般都是写困难题的, 学会上大分. 同类型的AC自动机,后缀数组都是较难的知识点 哈希分单模双模哈希: 单模哈希 根据生日攻击，设 M 为模数，仅仅计算大约 1.18⋅ sqrt(M)​个不同字符串的哈希值，就有 50% 的概率会发生哈希碰撞，也就是有两个不同的字符串，哈希值是一样的。 双模哈希 设 M1和 M2为模数，此时要计算大约…

曼哈顿距离应该是我们熟知的距离计算方式,两个单元格 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。但他的绝对值经常干扰我们计算,我们可以把它转换成切比雪夫距离,具体原理可以看曼哈顿距离与切比雪夫距离的相互转化,结论就是：曼哈顿距离在坐标轴旋转 45 度后与切比雪夫距离等价。其中通过转轴公式,…

天天写惯了记忆化搜索,来个递推DP就老实了(已老实, 求放过) 这类问题用递推很简单, 但是记忆化就不行了, 主要是这类题目需要存取两个字符, 很容易爆内存, 但是用递推就很容易想,容易通过. 数组中最长的方波 1480 最长定差子序列 1597 最长等差数列 1759 找出有效子序列的最大长度 II ~1850 最长的斐波那契子序列的长度 191…