面试题：计算0到n的数中有多少个2

例如给出n=100，那么就是计算0到100这么多个数中有多少个2.

首先要搞清楚2是怎么来的（这话怎么听起来不对劲？）：

有2个来源：

1 个位来源：12,32,42,82,92,22等，其中的22可以先计算个位的2，然后十位的2留待第二个情况处理

2 十位来源：20,21,22,23,24,25,26,27,28,29共10个

举例1000，

1 个位2出现在,2,12,22,32,42,52,62,72,82,92共10个；也出现在102,112,122,132,142,152,162,172,182,192；202,212,...992等共100个

2 十位2出现在:20,21,22,23,24,25,26,27,28,29; 120,121,122,123,124,125,126,127,128,129;,220,221,222,223,...共100个

3 还有百位的：201,202,203,204,205,206,207,208,209,210,211,212...299共一百 个。

所以总共是300个。

但是100为的情况可以当做是10位的情况考虑，需要一点窍门。分三种情况计算。

这点窍门还是直接上程序比较好学会吧，如果解说，我觉得真是太啰嗦了，好像本书作者那样，老实说我真不知道他说啥，后来是直接看他的代码看懂的。

而且本题的难点还真不在这个思路上面，还是把思想优雅地转换成为代码这一步是最难的，就跟数字发音的题目那样。

还是那句话：会思路，和把思路转换程序差不多是两种能力来的。所以某些人老是强调思路是最重要的，但是这句话最多对了一半，因为那得看什么题目。

下面给出暴力法，和上面例子那么计算的方法：

//暴力法
int numOf2s(int i)
{
	int count = 0;
	while (i>0)
	{
		if (i%10 == 2) count++;
		i /= 10;
	}
	return count;
}
int numOf2sInRange(int n)
{
	int count = 0;
	for (int i = 2; i <= n; i++)
	{
		count += numOf2s(i);
	}
	return count;
}

//分块计算法
int count2sInRangeAtDigit(int num, int d)
{
	int powOf10 = (int) pow(10, d);
	int nextPowOf10 = 10 * powOf10;
	int right = num % powOf10;

	int roundDown = num - num % nextPowOf10;
	int roundUp = roundDown + nextPowOf10; 

	int digit = (num / powOf10) %10;

	//相当于计算个位的2，如：每十位就有一个2
	if (digit < 2)
	{
		return roundDown / 10;
	}
	//相当于计算10位的2，如：有多少个20,21,22,23的十位里面有3+1个2
	else if (digit == 2)
	{
		return roundDown / 10 + right +1;
	}
	//超过了2，那么10位的2肯定有10个，如30以下的：20,21,22,23,...,29有十个2
	else
	{
		return roundUp / 10;
	}
}

int count2sInRange(int num)
{
	int c = 0;
	ostringstream ss;
	ss<<num;
	int len = ss.str().length();
	for (int digit = 0; digit < len; digit++)
	{
		c += count2sInRangeAtDigit(num, digit);
	}
	return c;
}

int main() 
{
	int tar = 7;
	int cand[] = {1,2,3,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,8};
	cout<<numOf2sInRange(1000)<<endl;
	cout<<count2sInRange(1000)<<endl;

	system("pause"); 
	return 0;
}

运行结果：

上面是暴力法，下面是分块计算的方法，结果是一样的。不过好像暴力法超过9位数就无法计算出来了。

注意：计算INT_MAX的时候还有可能溢出处理方法是改成long long保存结果就可以了。很简单，本文就不给出了。O(∩_∩)O~