专题 15数学与模拟

15.1数学题与模拟题考什么

先把这两类题分清楚，因为对策完全不同：

为什么学生容易在这类题翻车？因为没有模板可以背。前面专题里你背了双指针、二分、BFS 的骨架，遇到题先套再调； 数学与模拟题没有骨架，考的是从零搭。所以这一章的重点不是题本身，而是两个可复现的思考切入点：观察小例子找规律（数学），列出状态变量再直译（模拟）。

15.2罗马数字转整数（简单，力扣 13）

简单 核心：观察字符间的位置关系

题意。罗马数字用 7 个符号表示数：I=1、V=5、X=10、L=50、C=100、D=500、M=1000。通常大符号在左、小符号在右，直接加起来； 但恰好有 6 种「小在大左」的减法组合：IV=4、IX=9、XL=40、XC=90、CD=400、CM=900。给你一个罗马数字字符串，转成整数。

思路推导。暴力想法是把 6 种减法组合单独写 if——能做，但啰嗦。停一下，观察减法组合的共同点：

它们都是「小符号出现在大符号的左边」。也就是说，逐位扫描时：

• 当前符号值 ≥ 右边符号值 → 正常，加上它；
• 当前符号值 < 右边符号值 → 它是减法组合的前半截，减去它。

一个判断就覆盖了全部 6 种情况——这就是从「枚举特例」到「观察共性」的典型过程。小例子验证：MCMXCIV = 1000 − 100 + 1000 − 10 + 100 − 1 + 5 = 1994 ✓

class Solution {
    public int romanToInt(String s) {
        // 符号 -> 值 的映射表
        java.util.Map<Character, Integer> map = java.util.Map.of(
            'I', 1, 'V', 5, 'X', 10, 'L', 50,
            'C', 100, 'D', 500, 'M', 1000);

        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int cur = map.get(s.charAt(i));
            // 关键判断：如果当前符号比右边的小，说明它是 IV / IX 这类减法前缀
            if (i + 1 < n && cur < map.get(s.charAt(i + 1))) {
                ans -= cur;   // 减掉它，下一轮循环右边那个大符号会被正常加上
            } else {
                ans += cur;   // 正常累加
            }
        }
        return ans;
    }
}

复杂度。时间 O(n)，每个字符看一次；空间 O(1)，映射表是固定 7 项。

15.3快乐数（简单，力扣 202）

简单 核心：把「循环检测」迁移到数字上

题意。对一个数反复做「各位平方和」变换：比如 19 → 1²+9²=82 → 64+4=68 → 36+64=100 → 1。若最终变到 1，就是快乐数； 若永远变不到 1（陷入一个不含 1 的循环），就不是。判断给定数字是否为快乐数。

思路推导。先想暴力：不断变换，那循环到什么时候停？题面没说步数上限。直觉上变换结果不会无限增大（位数多了平方和会被压回去， 比如 999...9 的平方和远小于自身），所以要么到 1，要么陷入循环。「判断一个过程是否陷入循环」——你在链表专题见过完全同构的问题： 环形链表判断。链表里节点用 next 连接，这里「下一个数」就是 next。

于是两种现成武器都能搬过来：

• 哈希集合：把每次变换的结果存进 HashSet，重复出现即死循环；
• 快慢指针：slow 每次变换一次，fast 变换两次，相遇时若值是 1 就是快乐数——省掉 O(循环长度) 的空间。

class Solution {
    // 计算「各位平方和」，相当于链表的 next 指针
    private int next(int n) {
        int sum = 0;
        while (n > 0) {
            int d = n % 10;   // 取出个位
            sum += d * d;     // 累加平方
            n /= 10;          // 去掉个位
        }
        return sum;
    }

    public boolean isHappy(int n) {
        // 快慢指针：slow 一步，fast 两步
        int slow = n, fast = next(n);
        // 只要 fast 还没到 1 且两者没相遇，就继续追
        while (fast != 1 && slow != fast) {
            slow = next(slow);        // 慢指针走一步
            fast = next(next(fast));  // 快指针走两步
        }
        // 循环退出只有两种可能：fast 到了 1（快乐），或 slow==fast 相遇（死循环）
        return fast == 1;
    }
}

复杂度。时间 O(log n) 每次变换，循环长度经验上很短；空间 O(1)（快慢指针版）。

15.4计数质数：埃氏筛（中等，力扣 204）

中等 核心：筛法的「排除」视角

题意。统计小于 n 的质数个数。比如 n=10 时，质数有 2、3、5、7，答案是 4。

思路推导。逐个数判断是不是质数：对每个 i 试除到 √i，整体 O(n√n)。n=10⁷ 时约 3×10¹⁰ 次操作——必超时。 优化点在哪？观察：判断 4、6、8 时我们在重复排除 2 的倍数。换个视角——与其「逐个判断谁质数」，不如「一次性排除所有合数」：

从 2 开始，把 2 的所有倍数标记成合数；遇到下一个没被标记的数（3），它必然是质数（因为它的所有更小因子都被筛过了）， 再把 3 的倍数全标记……这样每个合数只被它的质因子碰到一次，整体约 O(n log log n)。

还有一个细节：筛 2 的倍数时从 4 开始还是从 2×2=4 开始？从 i*i 开始——小于 i² 的 i 的倍数（如 2i、3i…(i−1)·i）已经被更小的质数筛过了，再筛一遍是重复劳动。

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        // isComposite[i] = true 表示 i 是合数（被筛掉的）
        boolean[] isComposite = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isComposite[i]) continue;  // 已被更小的质数筛掉，跳过
            count++;                       // 没被筛掉 => i 是质数
            // 从 i*i 开始筛 i 的倍数：更小的倍数已被筛过
            // 用 long 防止 i*i 溢出 int
            for (long j = (long) i * i; j < n; j += i) {
                isComposite[(int) j] = true;
            }
        }
        return count;
    }
}

复杂度。时间 O(n log log n)——每个合数被 Σ(1/p) 覆盖，p 取遍质数，这个级数增长极慢；空间 O(n) 的标记数组。

15.5阶乘后的零（中等，力扣 172）

中等 核心：把问题翻译成因子计数

题意。给定整数 n，返回 n! 结果末尾 0 的个数。比如 5! = 120，末尾 1 个零。

思路推导。直接算 n! 再数零？n=30 时阶乘就超出 long 范围，不可行。观察末尾零是怎么来的：每个末尾零对应一个因子 10， 而 10 = 2 × 5。所以问题等价于：n! 的质因子分解里，2 和 5 各出现多少次，取较小值。

谁更少？在阶乘里，每隔 2 个数就有个偶数（贡献 2），每隔 5 个数才有 5 的倍数（贡献 5）——2 的因子远多于 5。所以答案 = 5 的因子总数。

那 5 的因子怎么数？n/5 数出「至少含一个 5」的数（5, 10, 15, …）；但 25 含两个 5，只数一次不够——再除：n/25 数「至少含两个 5」的， 再 n/125……直到商为 0。每一层都给答案贡献 1（对每个被数到的数）。小例子：n=100 → 100/5=20，100/25=4，100/125=0 → 20+4=24 个零 ✓

class Solution {
    public int trailingZeroes(int n) {
        int ans = 0;
        long p = 5;              // 用 long 防止 p*5 溢出
        while (p <= n) {
            ans += n / p;        // 「至少含 p 一个因子 5」的数的个数
            p *= 5;              // 下一轮数 25、125……每个这样的数额外贡献一个 5
        }
        return ans;
    }
}

复杂度。时间 O(log₅ n)，循环次数约 13 次就到 10⁹ 以上；空间 O(1)。

15.6螺旋矩阵：模拟题怎么写（中等，力扣 54）

中等 核心：边界收缩的四指针法

题意。给定 m×n 矩阵，按顺时针螺旋顺序返回所有元素。比如：

输入:            螺旋顺序:
 1  2  3        1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> 5
 4  5  6
 7  8  9

思路推导。这是模拟题的标准样本。按题意直译：「顺时针转圈」= 依次走上边（左→右）、右边（上→下）、下边（右→左）、左边（下→上）， 每走完一条边就把对应边界往里收缩一格。用四个变量维护当前未走区域的边界：top / bottom / left / right。

每条边走之前先判断边界还有没有剩余（防止在只剩一行/一列时重复走），这是本题唯一的坑点：

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) ans.add(matrix[top][j]);    // 上边：左 -> 右
            top++;                                                          // 上边界收缩
            for (int i = top; i <= bottom; i++) ans.add(matrix[i][right]);  // 右边：上 -> 下
            right--;                                                        // 右边界收缩

            // 剩余不止一行时才走下边，否则 top 收缩后可能越界重复
            if (top <= bottom) {
                for (int j = right; j >= left; j--) ans.add(matrix[bottom][j]); // 下边：右 -> 左
                bottom--;
            }
            // 剩余不止一列时才走左边
            if (left <= right) {
                for (int i = bottom; i >= top; i--) ans.add(matrix[i][left]);   // 左边：下 -> 上
                left++;
            }
        }
        return ans;
    }
}

复杂度。时间 O(m·n)，每个元素恰好访问一次；空间 O(1)（不算返回列表）。

15.7本专题常见坑

15.8自测题