统计 1 ~ n 整数中出现 1 的次数

[MY729]

题目来源

题目

统计 1 ~ n 整数中出现 1 的次数

例如：
n为 10，则输出 2
n为11，则输出4
n为100, 则输出21

分析

我们先观察给出n的每个位数出现1的次数, 比如：
n = 100‘
个位数为1的数字：00 '1'， 01 '1'， 02 '1'，03 '1'，04 '1'，05 '1'，06 '1'，07 '1'，08 '1'，09 '1'，共10个
十位数为1的数字：0 '1' 0，0 '1' 1，0 '1' 2，0 '1' 3，0 '1' 4，0 '1' 5，0 '1' 6，0 '1' 7，0 '1' 8，0 '1' 9，共10个
百位数为1的数字：'1' 00， 共1个
我们可以看到像11这样的数字，分别在个位数和十位数都被统计了一次，
所以最终，n为100时，出现的1的次数是 10 + 10 + 1 = 21次

通过上面的例子n = 100分析规律：

• 个位数为1的数，那么只看剩余的位数（百位和十位数）10，可以看出个位数为1的个数是从 00 到 10 - 1（10+ '1' 大于100, 所以是10 -1），共10个
• 十位数为1的数，那么只看剩余的位数（百位和个位数）10，可以看出十位数为1的个数是从 00 到 10 - 1（1 + '1' + 0 大于100, 所以是10 -1），共10个
• 百位数为1的数, 那么只看剩余的位数（十位和个位数）00，可以看出十位数为1的个数是只有 00，1个

我们再分析一个n = 111：

• 个位数为1的数，那么只看剩余的位数（百位和十位数）11，可以看出个位数为1的个数是从 00 到 11，共12个
• 十位数为1的数，那么只看剩余的位数（百位和个位数）11，可以看出十位数为1的个数是从 00 到 11，共12个
• 百位数为1数, 那么只看剩余的位数（十位和个位数）11，可以看出十位数为1的个数是 00 到 11，共12个
  所以n = 111时，1出现的次数为12 + 12 + 12 = 36

我们再分析一个n = 127：

• 个位数为1的数，那么只看剩余的位数（百位和十位数）12，可以看出个位数为1的个数是从 00 到 12，共13个
• 十位数为1的数，那么只看剩余的位数（百位和个位数）17，可以看出十位数为1的个数是从 00 到 19（1 + '1' + 8, 1 + '1' + 9都小于127，所以是19），共20个
• 百位数为1数, 那么只看剩余的位数（十位和个位数）27，可以看出十位数为1的个数是 00 到 27，共28个
  所以n = 127时，1出现的次数为13 + 20 + 28 = 61