[LeetCode]Number of Digit One

给定N，让我们求[1, N]这个区间里的所有数出现了几次1。这道题我们按每一位每一位统计，个十百千万按顺序求即可。比如对于310：

1. 我们首先统计个位，首先个位至少出现了1 * 31次，[1, 11, 21... 301]，对于311，因为其只到310，所以我们不需要统计这一个。所以个位总共出现了31次1。
2. 十位同理，至少有10 * 3次，[10-19, 110-119, 210-219]，对于31x，因为最大值只到310，所以只有1个。总共十位出现了30 + 1 = 31次1。
3. 对于百位，出现了100 * 1次，也就是[100-199]。总共百位出现了100次。
4. 所以总共1出现了31 + 31 + 100 = 162次。

我们按照这个思路统计即可，假设输入数字大小为n，时间复杂度O(log10(n))，常数空间，代码如下：

	class Solution {
	public:
	int countDigitOne(int n) {
	if(n < 1)return 0;
	int res = 0;
	long lo = 1;
	//count digit by digt
	while(n / lo)
	{
	res += lo * (n / (lo * 10));
	int count = max(min(lo, n % (10 * lo) - lo + 1), 0L);
	res += count;
	lo *= 10;
	}
	return res;
	}
	};

view raw Number of Digit One.cpp hosted with ❤ by GitHub