我的博客

利用位运算查找元素

常用算法与数据结构模板系列（八）

偶数个相同的数字按位异或为零。假如一个集合里有一个数字出现奇数次，其他数字出现偶数次；那么对所有数字取异或操作，重复偶数次的数字都清零，留下来的就是那一个重复奇数次的数。 # 136. Single Number # 找出数组中不重复的元素。其它元素出现两次。 # Input: [4,1,2,1,2] # Output: 4 def single_num(nums): ret...

Posted by John Mactavish on September 18, 2020

图相关算法

常用算法与数据结构模板系列（七）

并查集(Union Find Set) 并查集算法主要用于解决图论中“动态连通性”问题。“连通”即至少可以找到一条从图中一点到另一点的路径， “动态”即图的结点之间的连通关系是一步一步动态增加的。并查集主要需要实现这两个 API：并（合并两个结点，即连通了两个原本不连通的连通分量，用于动态构建连通关系）与查（判断两个结点是否连通）。 trait UnionFindSet { def...

Posted by John Mactavish on September 16, 2020

数学与数字相关算法

常用算法与数据结构模板系列（六）

同余定理同余定理：两个整数同时除以一个整数得到的余数相同，则二整数同余。记作a ≡ b(mod m)。对于同一个除数，两个数之和（或差）与它们的余数之和（或差）同余。对于同一个除数，两个数的乘积与它们余数的乘积同余。对于同一个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。同余定理的...

Posted by John Mactavish on September 13, 2020

统计与概率相关算法

常用算法与数据结构模板系列（五）

用 Rand7() 实现 Rand10() 如果我们有 Rand10N() 的话可以通过对 10 除取余很容易地实现 Rand10()，所以可以自然地想到把 Rand7() 向更大的 rand 映射。一个朴素的想法是进行两次 Rand7() 然后把结果相加或相乘得到 rand of [2,14] 或者 rand of [1,49]，但是仔细想想这样得到的数并不在区间内均匀出现。然后我...

Posted by John Mactavish on September 12, 2020

马拉车算法

常用算法与数据结构模板系列（四）

马拉车算法(Manacher’s Algorithm)用于在 O(N) 时间内提取一个字符串中有关回文串的信息。 “回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串，单个字符，重复的字符同样是回文串。鉴于它的中心对称性，不难想到判断一个字符串是回文串的方法是在循环内依次判断对称位置的字符是否相同。但是如果要找出一个字符串中的最长回文串，或者计数...

Posted by John Mactavish on September 8, 2020

二分搜索

常用算法与数据结构模板系列（三）

几个值得注意的点分别是： 1）区间为左闭右闭，即 [left, right]，循环内部的隐性约束是要搜索的数（如果存在的话）在当前搜索的闭区间内。 2）while 循环的条件是 left < right 而不是 left <= right，这样循环终止时，必有 left == right，使用任意一个都一样，不易出错。 3）区间长度是偶数时涉及到左右中位数的问题...

Posted by John Mactavish on September 5, 2020

动态规划各分类模板

常用算法与数据结构模板系列（二）

线性 DP 一维动态规划是最简单的，但是可以借此了解动态规划的思考方法与注意事项。一维 DP 数组的定义方法也可以推广到更高维上去，作为高维 DP 数组的其中一维。子数组问题给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。请你返回乘积为正数的最长子数组长度。示例 1：输入：num...

Posted by John Mactavish on August 30, 2020

枚举算法

常用算法与数据结构模板系列（一）

2020-09-16 更新今天发现“常用算法与数据结构模板”这个主题的内容写得实在是太多了，以至于放在一篇博文里面显得不太合适。所以今天把这个主题分拆成一系列的文章（话说，这其实应该是我写的第一个系列）。 DFS 模板如下： void dfs(int 当前状态) { if(当前状态为边界状态) { 记录或输出 r...

Posted by John Mactavish on August 26, 2020

Euphonium 语法设计与 parser combinator

Posted by Mactavish on August 18, 2020

Java 让我不爽的地方

Where Java Sucks

Set 不提供获取元素的操作讲老实话，我到今天才知道原来 Set 没有 get 方法：大概是以前确实没有这个需求。咋一看好像没有什么问题，如果你知道要的元素是什么，还要获取 Set 里面相等的元素干什么。但是 Set 通过对象的 equals 方法判断元素是否相等，而 equals 方法可以只选择感兴趣的字段作比较。 Set<Foo> set = ...; ... F...

Posted by John Mactavish on August 13, 2020