KMP 算法中的 next 数组
2021-03-18
对于字符串匹配，即在字符串 s 中寻找 p 子串的位置，如果使用暴力匹配，则时间复杂度为 $O(mn)$。而 KMP 算法在字符串重复率较高时可以获得更好的性能，时间复杂度为 $O(m + n)$。 …
CSAPP Data Lab
2020-07-02
Data Lab 的题1，第一眼觉得不难，仔细一看发现限制非常严格，比如只允许部分位运算符等，难度一下子就上去了，所以花了不少时间。 dlc 是 64 位 Linux 程序，使用 ./dlc bits.c 来检查是否符合限制条件。但 Makefile 里却指定了 -m32，可能是考虑到 C 标准只规定 int 至少为 16 位，一些环境可能会生成非 32 位的 int。 …
享元模式 Flyweight Pattern
2020-03-08
享元模式与其说是一种设计模式，不如说是一种算法思想。将可以共享的对象存储在一个表中以节省内存，而不是每次都重新创建。 例如，Java 中的 Integer 类型对 -128 到 127 的值做了缓存，java.lang.Integer#valueOf(int) 会直接返回缓存的对象。String 则可以保存在常量池中。这些都是典型应用。 …
将正整数表示为若干平方数之和 Perfect Squares
2019-05-08
https://leetcode.com/problems/perfect-squares/ Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n. Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. 动态规划 $$ f(i) = \min\{f(i - s)\} + 1, 其中 s 为平方数且 1 \le s \le i$$ …
Java 集合框架
2019-04-17
Collection Collection 接口基本可分为三种，List、Set 和 Queue。这些接口有对应实现的抽象类，实体类只需要继承抽象类即可，免去不必要的重复编码。 为什么实体类继承了对应的抽象类，还要实现接口呢？例如： …
素数筛法和哥德巴赫猜想
2019-01-03
起因是看到了这个帖子如果高中生能证明哥德巴赫猜想，会被清华北大数学系保送吗？ - 知乎，emmm… 本文的目标是筛选 32 位无符号整数（约 40 亿）中的所有素数，并在此范围内验证哥德巴赫猜想。 …
幂运算 pow(x, n) 的一个迭代实现
2018-08-24
求一个浮点数的整数次幂： https://leetcode.com/problems/powx-n/ Implement pow(x, n), which calculates x raised to the power n (i.e. xn). Example 1: Input: x = 2.00000, n = 10 Output: 1024.00000 Example 2: Input: x = 2.10000, n = 3 Output: 9.26100 Example 3: Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Constraints: -100.0 < x < 100.0 -231 <= n <= 231-1 -104 <= xn <= 104 基本就是分治思想，用递归就能很方便地实现，也可以把递归改写成迭代，但我在 Discuss 区看见了一个精奇的迭代思路1。 …
第一个大于等于某个正整数的 2 的幂
2018-07-13
在计算机中，2 的幂是神奇的数，很多运算可以用位操作来完成。 求第一个大于等于某个正整数的 2 的幂，例如 1023 则返回 1024，这个算法在 Java 中哈希表分配桶就有所运用。 …