1的数目

这是题目：

给定一个十进制正整数 N，写下从1 开始，到 N的所有整数，然后数一下其中出现的所有“1”的个数

其实这个问题，我们可以暴力的去实现它，不过时间效率会是一个很大的问题

public int sum1(int n)
	{

		int iNum = 0;

		int count = 0;
		
		for (int i = 1; i <= n; i++)
		{
			iNum = 0;
			
			int t = i;
			while (t != 0)
			{
				iNum += (t % 10 == 1) ? 1 : 0;
				t /= 10;
			}
			count += iNum;
		}
		
		return count;
	}

当然，这个问题也可以用巧妙的方法解决，一个数的位数上的1的个数总是和这个数的高位和地位有关的，如34232，百位2的高位为34，低位为32，这可判断这个是百位中1的个数肯定是（34+1）*100，由于每个都是100-199中这100个数出现100，同理可推到其他位数

请看代码实现

public int sum(int n)
	{
		//低位
		int lowNum = 0;
		//高位
		int hightNum = 0;
		//当前位
		int currNum = 0;
		//为权重，1，10，100...
		int factor = 1;

		int count = 0;

		while (n / factor != 0)
		{
			lowNum = n - (n / factor) * factor;
			hightNum = n / (factor * 10);
			currNum = (n / factor) % 10;

			switch (currNum)
			{
			case 0:
				count += hightNum * factor;
				break;

			case 1:
				count += hightNum * factor + (lowNum + 1);
				break;

			default:
				count += (hightNum + 1) * factor;
				break;

			}

			factor *= 10;
		}

		return count;

	}

可见，对时间效率的提升的多么明显