剑指offer 面试题32—从1到n整数中一出现的次数

剑指offer 面试题32—从1到n整数中1出现的次数

题目：

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12，从1到12这些整数中包含1的数字有1,10,11,12。所以1一共出现了5次。

解法一：O(nlogn)

基本思想：

累加1到n每个整数中1出现的次数。n个数，每个数有O(logn)位。

#include <iostream>
using namespace std;

int numberof1(int n)
{
	int ret=0;
	while(n)
	{
		if(n%10==1)
			ret++;
		n/=10;
	}
	return ret;
}

int foo(int n)
{
	int count=0;
	for(int i=1;i<=n;i++)
		count+=numberof1(i);
	return count;
}

int main()
{
	int n;
	while(cin>>n)
	{
		cout<<foo(n)<<endl;
	}

	return 0;
}

解法二：O(logn)

输入n有O(logn)位。

基本思想：数字规律

#include <iostream>
using namespace std;

int foo(int n)
{
	int icount=0;
	int iflag=1;
	int ilow=0;
	int icurr=0;
	int ihigh=0;

	while(n/iflag!=0)
	{
		ilow=n-(n/iflag)*iflag;
		icurr=(n/iflag)%10;
		ihigh=n/(iflag*10);

		switch(icurr)
		{
		case 0:
			icount+=ihigh*iflag;
			break;
		case 1:
			icount+=ihigh*iflag+ilow+1;
			break;
		default:
			icount+=(ihigh+1)*iflag;
			break;
		}
		iflag*=10;
	}

	return icount;
}

int main()
{
	int n;
	while(cin>>n)
	{
		cout<<foo(n)<<endl;
	}

	return 0;
}