18.4 Write a method to count the number of 2s between 0 and n.
这道题给了我们一个整数n，让我们求[0,n]区间内所有2出现的个数，比如如果n=20，那么满足题意的是2, 12, 20,那么返回3即可。LeetCode上有一道很类似的题Factorial Trailing Zeroes，但是那道题求5的个数还包括了因子中的5，比如10里面也有5，这是两题的不同之处。那么首先这题可以用brute force来解，我们对区间内的每一个数字都调用一个函数，用来统计该数字中2出现的个数。而统计一个数字各位上而出现的个数很简单，就是平移位，对10取余，如果为2，则计数器自增1，然后此数自除以10，直至为0停止，参见代码如下：
解法一：
int count_number_2(int num) {
int res = ;
while (num > ) {
if (num % == ) ++res;
num /= ;
}
return res;
}
int count_in_range(int num) {
int res = ;
for (int i = ; i <= num; ++i) {
res += count_number_2(i);
}
return res;
}
其实这道题还有更好的办法，我们不是在区间里一个数一个数的找2，而是按位来找，比如我们先来列出一部分序列：
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
...
110 111 112 113 114 115 116 117 118 119
我们发现最低位出现2的频率是每10个数字出现1个，我们大概可以分为三种情况来讨论，digit < 2, digti = 2, 和digit > 2。
当digit < 2时，例如x=61523, d=3, 那么x[d]=1，从低位开始坐标为3的数字是1(从0开始)，那么第三位上的2出现于2000-2999, 12000-12999, 22000-22999, 32000-32999, 42000-42999, 52000-52999, 所以总共有6000个2，在第三位上。怎么跟我们在区间[1,60000]上只计算第三位上的2的个数相同。
当digit > 2时，大于2的情况跟上面的分析方法相同，比如x=63523，那么这跟区间[0,70000]上第三位是2的个数相同，所以我们rounding up一下即可。
当digit = 2时，比如x=62523，我们知道[0,61999]区间的第三位2的个数可以通过上面第一种情况计算出来，那么怎么计算[62000,62523]区间中第三位2的个数呢，共有524个，用62523-62000+1即可。
根据上述分析，我们不难写出代码如下:
解法二：
int count_in_range_as_digit(int num, int d) {
int power_of_10 = pow(, d);
int next_power_of_10 = power_of_10 * ;
int right = num % power_of_10;
int round_down = num - num % next_power_of_10;
int round_up = round_down + next_power_of_10;
int digit = (num / power_of_10) % ;
if (digit < ) return round_down / ;
else if (digit == ) return round_down / + right + ;
else return round_up / ;
}
int count_in_range(int num) {
int res = ;
int len = to_string(num).size();
for (int i = ; i < len; ++i) {
res += count_in_range_as_digit(num, i);
}
return res;
}