1～n 整数中 1 出现的次数

1. 题目描述

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

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

2. 示例

输入：n = 12
输出：5

输入：n = 13
输出：6

3. 解题

根据@Krahets大佬的解答： 设数组n是个$x$位数，设$n$的第$i$位为$n_i$, 则可将$n$写为$n_x n_{x-1} ··· n_2 n_1$

• 称$n_i$为当前位，记为cur
• 将$n_{i-1} ··· n_2 n_1$称为低位，记为low
• 将$n_x n_{x-1} ··· n_{i+2} n_{i+1}$称为高位，记为high
• 将$10^i$记为位因子，记为digit 则某位中1出现次数的计算方法为： 根据当前位cur的不同，分为以下三种情况
  1. 当cur = 0 ，此时1的出现次数仅由高位决定，计算公式为：$$high * digit $$
  2. 当cur = 1 ，此时1的出现次数由高位和低位一起决定，计算公式为$$high * digit + low + 1$$
  3. 当cur = 2, 3, ···, 9时，此时1的出现次数只由高位high决定，计算公式为$$(high + 1) * digit$$

{T_T}群除我佬