将正整数表示为若干平方数之和 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 亿）中的所有素数，并在此范围内验证哥德巴赫猜想。 …
CSAPP 信息的表示和处理
2018-12-25
2.1 信息存储 2.1.1 十六进制表示法 十六进制转换窍门：记住 A、C 和 F 对应的值，B、D 和 E 可通过计算它们与前三个值的相对关系来完成。 对于 2 的非负整数 n 次幂 x，即 $x = 2^n$，一个转换为十六进制的技巧：x 的二进制形式就是 1 后面跟 n 个 0，把 n 表示成 $i + 4j$，其中 $0 \le i \le 3$，当 i 为 0、1、2、3 时，x 的十六进制开头数字分别为 1、2、4、8，后面跟着 j 个十六进制的 0。如 $2048 = 2 ^ {11}$，有 $n = 11 = 3 + 4 \cdot 2$，从而得到十六进制 0x800。 …
CSAPP 计算机系统漫游
2018-12-24
1.1 信息就是二进制位+上下文 例如 C 语言源码： hello.c #include <stdio.h> int main() { printf("hello, world\n"); return 0; } 用 vim 以二进制方式打开 vim -b hello.c，由于是纯 ASCII 码写成的，所以和以文本方式打开没有区别，然后使用 :%!xxd 转换为 16 进制 ASCII 码： …
幂运算 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 中哈希表分配桶就有所运用。 …
通配符匹配 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 *. …