剑指offer 面试题32―从1到n整数中1出现的次数
栏目：php教程时间：2015-05-04 09:51:17
题目：
输入1个整数n，求从1到n这n个整数的10进制表示中1出现的次数。
例如输入12，从1到12这些整数中包括1的数字有1,10,11,12。所以11共出现了5次。
解法1：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;
}
解法2：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;
}
------分隔线----------------------------
------分隔线----------------------------