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 则可以保存在常量池中。这些都是典型应用。 使用享元模式的一个条件是，对象是可共享的，例如对于 Integer、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. …
Java 集合框架
2019-04-17
Collection 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 中哈希表分配桶就有所运用。 容易想到的一个实现是将 2 的幂一个个拿来比较，不过看起来不够优雅。 Java 源码给出了位运算的实现： …
通配符匹配 Wildcard Matching
2018-06-12
通配符匹配问题： https://leetcode.com/problems/wildcard-matching/ Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’. ‘?’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ? or *. 待匹配字串 s 中只有字母，模式串中 p 只含有字母和 ?、*，? 匹配任意单个字符，* 匹配任意多个字符（包括空字串），判断字串是否完全匹配。 使用递归算法会超时。 …
数组中首个缺失的正整数 First Missing Positive
2018-06-08
找出数组中首个缺失的正整数： https://leetcode.com/problems/first-missing-positive/ Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your algorithm should run in O(n) time and uses constant extra space. 看起来很简单，首先想到排序的方法，时间复杂度为 $O(n\log(n))$。 也可以用最小堆/优先队列，在平均情况下也只要 $O(n)$，最坏情况下为 $O(n\log(n))$，空间复杂度为 $O(n)$。 以上两种方法均能 AC。然而题目要求时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 …