劍指offer 面試題32―從1到n整數(shù)中1出現(xiàn)的次數(shù)
來源：程序員人生 發(fā)布時(shí)間：2015-05-04 09:51:17 閱讀次數(shù)：3291次
題目：
輸入1個(gè)整數(shù)n，求從1到n這n個(gè)整數(shù)的10進(jìn)制表示中1出現(xiàn)的次數(shù)。
例如輸入12，從1到12這些整數(shù)中包括1的數(shù)字有1,10,11,12。所以11共出現(xiàn)了5次。
解法1：O(nlogn)
基本思想：
累加1到n每一個(gè)整數(shù)中1出現(xiàn)的次數(shù)。n個(gè)數(shù)，每一個(gè)數(shù)有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)位。
基本思想：數(shù)字規(guī)律
#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;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
