面试题43：1到n整数中1出现的次数

先以逐数拆位建立正确基线，再按最高位、其余位和后缀递归分解十进制区间，并推导等价的high/cur/low逐位公式。

学习目标

  • 能按最高位、其余位和后缀递归分解十进制区间，统计 1 出现次数
  • 能解释"其余位为何均匀出现"的数学原理
  • 能推导等价的 high/cur/low 逐位公式

从“逐个数”转向“逐个位置”开始

先预测：1到12中，1、10、11、12分别贡献1、1、2、1个数字1，合计5。逐个整数拆十进制位能得到答案，却在n很大时重复做大量工作。更快的方向是一次统计某个位置在整个区间里有多少次等于1。

题目“1到n整数中1出现的次数”统计十进制表示里的字符1，不是二进制置位数。作者先给出逐数基线，再把n写成字符串，做。

作者解法一：逐数拆位基线

外层从1枚举到n，内层不断取模10并除以10。每个十进制位恰检查一次，因此结果直接正确；时间是O(n乘十进制位数)，空间O(1)。

int NumberOf1(unsigned int n) {
    int number = 0;
    while (n) {
        if (n % 10 == 1) {
            ++number;
        }
        n /= 10;
    }
    return number;
}
 
int NumberOf1Between1AndN_Solution1(
    unsigned int n) {
    int number = 0;
    for (unsigned int i = 1; i <= n; ++i) {
        number += NumberOf1(i);
    }
    return number;
}

它很适合作为短输入参考实现，能与优化解随机对拍。接口参数是unsigned int，而测试包装接收int；若新增负数测试，负n会转换成很大的无符号数，不会得到第二解“非正返回0”的语义。n等于无符号最大值时，i递增后回绕到0，i <= n 永远成立，还会形成无限循环。

作者解法二：最高位三部分递归

把当前十进制字符串记为s，首位数字为f，总长度为m，去掉首位的后缀为tail。作者把答案分成：最高位为1的数量H、除最高位外其他位置为1的数量O，以及后缀区间的递归数量F(tail)。

F(s)=H(s)+O(s)+F(tail)F(s)=H(s)+O(s)+F(tail)

这个每层减少一个字符，直到一位数：0返回0，1到9都返回1。

按最高位拆解：F(n) = 最高位贡献 + 其余位贡献 + F(后缀)n = 21345首位 2、长度 5，拆为三部分最高位为 110000～1999910000 次其余位为 12 × 4 × 10008000 次递归后缀 F(1345)去掉首位再算821 次10000 + 8000 + 821 = 18821后缀同样拆解：21345 → 1345 → 345 → 45 → 5（基例返回 1）首位>1 贡献整块 10^(len-1)；首位=1 贡献 后缀+1；其余位 = 首位×(len-1)×10^(len-2)。等价按位视角（high/cur/low）逐位累加也得 18821；把对 n 个数的枚举降为对十进制位的处理。
作者每层把答案拆成最高位贡献、其余位贡献和去掉首字符后的递归贡献。

贡献的三种情况

若首位大于1，区间完整覆盖从10的m减1次幂到2乘该幂之前的全部数字，最高位1恰出现一个完整块。若首位等于1，最高位1只从该幂持续到n，数量由后缀值决定。首位等于0只会出现在递归后缀，不产生当前最高位1。

H(s)={0,f=0value(tail)+1,f=110m−1,f>1H(s)= \begin{cases} 0, & f=0 \\ value(tail)+1, & f=1 \\ 10^{m-1}, & f>1 \end{cases}

这里的对21345为10000，因为10000到19999共有10000个数字，万位都是1。对1345则是345加1，即346，范围从1000到1345。

首位条件贡献区间解释示例
first等于00最高位范围尚未进入1区间递归处理后缀
first等于1suffix + 1从10的幂到n，后缀从0走到suffix21345的千位递归层
first大于110的length-1次方完整覆盖首位为1的一整块21345贡献10000
其余位置first × (length-1) × 10的length-2次方每个非首位在完整前缀块中均匀轮换21345贡献8000
首位是否越过1决定最高位贡献是零、部分区间还是完整一块。

为何均匀出现

考虑首位从0到f减1形成的f个完整前缀块。每个块里，其余m减1个位置中的任意一个，都有10的m减2次幂种后缀组合让该位置为1。因此：

O(s)=f(m−1)10m−2O(s)=f(m-1)10^{m-2}

这个对21345是2乘4乘1000，得到8000。最后递归统计1到1345的821个1，三部分合计18821。

递归后缀可能有前导0，例如处理1000时tail是字符串000。作者保留字符串长度逐层递归，首位0的H和O都为0，直到一位0基例返回0；不能先用atoi丢掉长度再套同一层公式。

忠实还原字符串实现

作者先拒绝非正n，用固定50字符数组和sprintf写十进制文本。递归函数以strlen取长度，以atoi读取首位为1时的后缀值，以PowerBase10循环计算10的幂。

#include <cstdio>
#include <cstdlib>
#include <cstring>
 
int PowerBase10(unsigned int n) {
    int result = 1;
    for (unsigned int i = 0; i < n; ++i) {
        result *= 10;
    }
    return result;
}
 
int NumberOf1(const char* strN) {
    if (!strN ||
        *strN < '0' ||
        *strN > '9' ||
        *strN == '\0') {
        return 0;
    }
 
    const int first = *strN - '0';
    const unsigned int length =
        static_cast<unsigned int>(
            std::strlen(strN));
 
    if (length == 1 && first == 0) {
        return 0;
    }
    if (length == 1 && first > 0) {
        return 1;
    }
 
    int numFirstDigit = 0;
    if (first > 1) {
        numFirstDigit =
            PowerBase10(length - 1);
    } else if (first == 1) {
        numFirstDigit =
            std::atoi(strN + 1) + 1;
    }
 
    const int numOtherDigits =
        first * (length - 1) *
        PowerBase10(length - 2);
    const int numRecursive =
        NumberOf1(strN + 1);
 
    return numFirstDigit +
           numOtherDigits +
           numRecursive;
}
 
int NumberOf1Between1AndN_Solution2(int n) {
    if (n <= 0) {
        return 0;
    }
    char strN[50];
    std::sprintf(strN, "%d", n);
    return NumberOf1(strN);
}

作者int输入最多10位，递归深度有界。按渐近分析，源码每层重新strlen剩余字符串并循环求10的幂，d层总工作约O(d²)，d是位数；若预计算幂或携带长度可到O(d)。这不改变它相对逐数O(n乘d)的巨大改进，但应准确区分源码与理想化算法。

方法身份时间空间说明
逐数拆位作者解法一O(n × 位数)O(1)简单参考实现
字符串递归作者解法二源码约O(位数²)O(位数)栈每层strlen和幂循环
high/cur/low迭代等价扩展O(位数)O(1)逐十进制位统计
预计算幂的递归优化作者结构O(位数)O(位数)栈避免每层重复求幂
数学分解把对n个整数的枚举降为对十进制位的处理；源码常数虽小，仍应区分原实现与优化版。

三部分为何不重不漏

把不足m位的数字在左侧补0，不会增加数字1，却能把0到n统一看成m位字符串。先按最左字符把范围分成first个完整块和一个最终不完整块，每个完整块包含10的m减1次幂个后缀。

最高位贡献只统计位置0：首位为1的完整块或最终部分块。其余位贡献只统计前first个完整块中的位置1到m减1；这些位置与最高位不同，所以不会重叠。最终不完整块的非最高位置，恰对应后缀从0到tail的所有表示，由F(tail)递归统计。

于是每一个数字1都由“所在数属于完整块还是最终块”和“所在位置是否为最高位”唯一归入H、O或递归项；三类两两不交，合并又覆盖0到n的全部数字。数字0本身不含1，因此把范围从1到n扩成0到n不改变答案。

这个划分也解释了为什么不能删除递归后缀的前导0：补零是保持每层位置身份的工具。虽然前导0不计作1，但它决定后续字符当前属于百位、十位还是个位，从而决定完整块大小。

等价扩展：按十进制位统计

旧页只写了high、cur、low迭代法。它是正确且更直接的工程扩展，但不是作者源码。对位权p，把n分成高位high、当前位cur和低位low。当前位置为1的数量按cur分三种：

C(p)={high⋅p,cur=0high⋅p+low+1,cur=1(high+1)⋅p,cur>1C(p)= \begin{cases} high\cdot p, & cur=0 \\ high\cdot p+low+1, & cur=1 \\ (high+1)\cdot p, & cur>1 \end{cases}

这个与作者最高位块计数是同一组合事实。递归法按最高位拆一层，逐位法固定一个位置观察所有前缀周期。

对21345，个位到万位贡献依次为2135、2140、2200、2346、10000，总和18821。千位cur等于1，必须加入low 345和端点，得到2346；这是最容易少一的分支。

#include <cstdint>
 
std::uint64_t countDigitOne(
    std::uint32_t n) {
    std::uint64_t answer = 0;
 
    for (std::uint64_t factor = 1;
         factor <= n;) {
        const std::uint64_t quotient =
            n / factor;
        const std::uint64_t high =
            quotient / 10;
        const std::uint64_t current =
            quotient % 10;
        const std::uint64_t low =
            n - quotient * factor;
 
        if (current == 0) {
            answer += high * factor;
        } else if (current == 1) {
            answer +=
                high * factor + low + 1;
        } else {
            answer +=
                (high + 1) * factor;
        }
 
        if (factor > n / 10) {
            break;
        }
        factor *= 10;
    }
    return answer;
}

uint64中间值覆盖作者正int输入的计数范围，并避免int结果对较大n溢出。循环在乘10前检查边界，防止位权回绕。若把输入扩展到完整uint64，答案本身也可能超过uint64，需要更宽整数或显式上限。

作者八组测试的准确覆盖

Test对同一n分别调用两个解法并与expected比较：

  1. n等于1，期望1。
  2. n等于5，期望1。
  3. n等于10，期望2。
  4. n等于55，期望16。
  5. n等于99，期望20。
  6. n等于10000，期望4001。
  7. n等于21345，期望18821。
  8. n等于0，期望0。

99覆盖两个位置完整0到9周期；10000覆盖整十幂边界和端点新增的一个最高位1；21345覆盖首位大于1、后缀首位等于1和多层递归。源码没有负数、int最大值、随机值或溢出检查。

由于解法一本身简单，可以对可承受的随机短n作为参考。还可枚举从0到9999的全部n，比较字符串递归与逐位公式；对10的幂前后各取一个值，专门检查边界增量。

#include <cassert>
#include <cstdint>
 
std::uint64_t bruteCount(std::uint32_t n) {
    std::uint64_t result = 0;
    for (std::uint32_t value = 1;
         value <= n; ++value) {
        std::uint32_t current = value;
        while (current != 0) {
            result += current % 10 == 1;
            current /= 10;
        }
    }
    return result;
}
 
void testCountDigitOne() {
    assert(countDigitOne(0) == 0);
    assert(countDigitOne(1) == 1);
    assert(countDigitOne(10) == 2);
    assert(countDigitOne(55) == 16);
    assert(countDigitOne(99) == 20);
    assert(countDigitOne(10000) == 4001);
    assert(countDigitOne(21345) == 18821);
 
    for (std::uint32_t n = 0; n <= 9999; ++n) {
        assert(countDigitOne(n) == bruteCount(n));
    }
}

bruteCount的循环同样不适合无符号最大值，因为value会回绕；这里测试上限明确为9999。测试工具也要遵守自身输入域，不能拿有回绕缺陷的参考去证明大范围实现。

计数范围与泛化边界

作者返回int。随着n增大，累计出现次数可超过int最大值，即使n本身仍是合法int；工程接口应先估算最大结果并选择64位或更宽类型。sprintf固定50字节对int足够，但通用大整数应直接操作字符串，避免先解析进有限整数。

若统计数字0，公式不能直接把1替换为0，因为普通十进制表示没有前导0；最高位块要扣除未开始的那些周期。统计1到9中的其他非零数字可以平移公式，统计任意数字集合则可按位置贡献相加。

若范围是L到R，可用F(R)减F(L减1)，但L为最小整数时要避免下溢。若输入包含负数，还要先定义是否统计负号、是否取绝对值以及0本身怎样表示；作者只定义正整数1到n。

递归字符串版本天然适合超长n，但计数结果也会非常大，需要大整数。此时PowerBase10和atoi都应换成十进制大整数运算，后缀值加1也不能落回机器int。

本章练习

练习

问题 1： 递归分解的三部分是什么？

问题 2： 为什么其余位是均匀出现的？

问题 3： 逐位公式 high/cur/low 如何理解？

概念说明

本章核心概念包括：按十进制位统计。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

  1. 逐数拆位正确但时间O(n乘位数)，适合作为短输入参考。
  2. 作者递归把答案拆成最高位贡献、其余位贡献和后缀贡献。
  3. 首位大于1给一个完整块，等于1由后缀加1决定。
  4. 其余m减1位在f个完整前缀块中均匀轮换。
  5. 21345递归得到10000加8000加821，合计18821。
  6. high、cur、low逐位公式是等价扩展，不是作者源码。
  7. 作者源码因每层strlen和求幂约为O(位数²)，可优化到O(位数)。
  8. 无符号回绕、int结果溢出与数字0的前导位语义必须单独处理。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

递归分解
把 n 按十进制最高位拆成三部分递归统计。
最高位
十进制表示中最左边的数字，决定区间划分。
均匀分布
其余位在完整区间内各数字出现的对称性。
复习本章（5 题）

讨论

评论区加载中…