劍指offer 面試題32―從1到n整數中1出現的次數
來源：程序員人生 發布時間：2015-05-04 09:51:17 閱讀次數：3286次
題目：
輸入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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
