# README
面试题 17.06.2出现的次数
1. 题目描述
编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。
示例:
输入: 25
输出: 9
解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)
提示：
n <= 10^9
标签
递归 数学 动态规划
2. 解题
-
暴力法(超时)
-
统计法
算法核心思想是分别统计每位（个、十、百、千位等等）出现待查数（比如这道题的2）的次数，然后求和，实现O(n)复杂度
比如我们要统计下面三个数百位上出现2的次数，无非就三种情况，大于2，小于2，等于2
- 情况1（百位大于2），如：12313
要想百位出现2，由于当前百位是3，那么最终的次数只依赖于更高位
00200-00299 100个数
01200-01299 100个数
...
12200-12299 100个数
所有百位出现2的总个数为从0到12 共13个100，即13*100=1300
即百位3的左侧那部分12加上1共13个百位为1的总数，从0到12共13个数，从200到299共100个数
结论1：当前位大于2=（当前位的左边部分+1）*10**当前位的右半部分的长度 ，这里就是（12+1）*10**len('13') 那要是左半边为空即开头呢，如345百位是3也大于2，左边为空呢，为空就是0，直接就是(0+1)*10**len('45')， 也就是200-299
- 情况2（百位小于2），如12113
要想百位出现2，由于当前位是1，那么最终的次数同样依赖于更高位，只不过会比上面的情况少最后一种
00200-00299 100个数
01200-01299 100个数
...
11200-11299 100个数
那么加起来就是（12）*10**len('13')
结论2：当前位小于2=（当前位的左边部分）*10**当前位的右半部分的长度，这里就是 12*10**len('13')
- 情况3（百位2等于2），如12213
这种情况稍微复杂那么一丢丢，百位出现2的情况不仅依赖于左半边，还依赖于右半边，不过想通了也就不难了
我们可以将这个数分成两部分：
首先我们取前三位不大于121的所有情况，就是上面的结论2
00200-00299 100个数
01200-01299 100个数
...
11200-11299 100个数，还是12*100个数，（12咋来的？从0到11共12个数哇，100咋来的？从0到99共100个数哇）
其次我们取前三位是122的情况，
12200-12213 这一共是14个数，总的加起来就是百位是2的所有情况了
结论三：当前位等于2=（当前位的左边部分）*10**当前位的右半部分的长度+当前位的右半部分+1 ，这里就是 12*10**len('13')+13+1 13+1就是从0到13共几个数