学步园

实现一个方法，计算0~n之间2的出现次数。

思路：

有个类似题在编程之美和剑指offer上都出现过，是求1的个数。以12306这个数为例，首先我们看千位，千位上2的出现次数有：2000~2999、12000~12306，一共是1 * 1000 + 307；百位上2的出现次数有：200~299、1200~1299、2200~2299、...、12200~12299，一共是13 * 100；十位上2的出现次数有：20~29、120~129、...、12220~12229，一共是123
* 10。

总结规律如下：

1、当前位的数字等于2时，该位2出现的次数为：高位数字 * 当前位数 + 低位数字 + 1；

2、当前位的数字大于2时，该位2出现的次数为：（高位数字 + 1）* 当前位数；

3、当前位的数字小于2时，该位2出现的次数为：高位数字 * 当前位数。

#include <iostream>
#include <vector>
using namespace std;

int NumOfTwo(int n)
{
	int res = 0;
	int base = 1;
	int cur = 0, high = 0, low = 0;
	while (base <= n)
	{
		cur = n / base % 10;
		high = n / base / 10;
		low = n - n / base * base;
		if (cur == 2)
			res += high * base + low + 1;
		else if (cur > 2)
			res += (high + 1) * base;
		else
			res += high * base;
		base *= 10;
	}
	return res;
}

int main()
{
	int n;
	while (cin >> n)
		cout << NumOfTwo(n) << endl;
	return 0;
}

这个思路可以扩展到其他的值（0 ~ 9），当求0的次数时，要考虑最高位不能为0的特殊情况。