剑指offer-43

剑指 Offer 43. 1～n 整数中 1 出现的次数

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例

输入：n = 12
输出：5

输入：n = 13
输出：6

官方题解

解体思路：

将$1 \sim n$的个位、十位、百位、$\dots$的 $1$ 出现次数相加，既为 $1$ 出现的总次数。

设数字 $n$ 是个 $x$ 位数，记 $n$ 的第 $i$ 位为 $n_i$，则可将 $n$ 写为 $n _ { x } n _ { x - 1 } \cdots n 2 n 1$：

• 称 “$n_i$” 为当前位，记为 $cur$，
• 称 “$n_{i-1}n_{i-2}\cdots n_2 n_1$”称为低位，记为 $low$，
• 称 “$n_x n_{x-1}\cdots n_{i+2}n_{i+1}$”称为高位，记为$high$，
• 将 $10^i$ 称为位因子，记为 $digit$。

某位中 1 出现次数的计算方法：

根据当前位 $cur$ 值的不同，分为以下三种情况：

1. 当$cur=0$时：此位 $1$ 的出现次数只由高位 $high$ 决定，计算公式为：
   $$
   high \times digit
   $$
   如下图所示：以 $n=2304$ 为例，求 $digit = 10$ （既十位）的$1$ 出现次数。

   

   这里如果是100，十位上的1，会出现10次，是因为

2. 当 $cur = 1$ 时：此时1的出现次数由高位 $high$ 和 低位 $low$ 决定，计算公式为：
   $$
   high \times digit + low +1
   $$

   如下图所示，以 $n = 2314$ 为例，求 $digit = 10$ （既十位）的 $1$ 出现次数。

   

   千位和百位可以选00 01 02....22  十位可以取到1 个位可以选0-9  共有 23 * 10 中排列
   当千位和百位取23,十位取1，个位可以去0-4 即 2310-2314共5个
   即 23 *10 + 4 +1

3. 当 $cur=2,3,\cdots,9$ 时：此位 1 的出现次数只由 高位 $high$ 决定，计算公式为：
   $$
   (high + 1) \times digit
   $$

   如下图所示，以 $n=2324$ 为例，求 $digit=10$（既十位）的 1 出现次数。

   

   千位和百位可以选00 01 02....22  十位可以取到1(形如 [00|01...|22]1[0-9] 都是<2324) 个位可以选0-9   共有 23 * 10 中排列
   
   当千位和百位取23,十位取1，个位可以去0-9 即 2310-2319共10个 （其中2311，被计算了两次，分别是从个位和十位分析得到的1次）
   即 23 *10 + 10

变量递推公式：

设计按照 “个位、十位、…” 的顺序计算，则 $high/cur/low/digit$应初始化为：

high = n // 10
cur = n % 10
low = 0
digit = 1 # 个位

因此，从个位到最高位的变量递推公式为：

while high != 0 or cur != 0: # 当 high 和 cur 同时为0时，说明已经越过最高位，因此跳出
    low += cur * digit # 将 cur 加入 low ，组成下轮 low
    cur = high % 10 # 下轮 cur 是本轮 high 的最低位
    high //= 10 # 将本轮 high 最低位删除，得到下轮 high
    digit *= 10 # 位因子每轮 × 10

借鉴楼主思路思考

• 以数字2304为例，若当前位为十位（base = 10），则当前位数0，高位数23，低位数4
• 当前位等于0情况，则可理解有两部分组成02299和23002304；若固定当前位位1，则前半段组合为[022]1[09]，次数为230=2310（highbase）；后半部组合十位只能取0，无法满足固定为1计算前提，次数为0
• 同理，若数字为2314，当前位等于1情况，优先拆分为02299和23002314；若固定当前位位1，则前半段组合为[022]1[09]，次数为230=2310（highbase）；后半部组合231[0~4]，次数为5（low+1）
• 同理，若数字为2324，当前位大于1情况，优先拆分为02299和23002324；若固定当前位位1，则前半段组合为[022]1[09]，次数为230=2310（highbase）；后半部组合231[0~9]，次数为10（base）

将数据拆分为两部分理解，计数前提当前位可以拨动到1