剑指offer 面试题32―从1到n整数中1出现的次数
发布时间：2020-12-13 20:08:02 所属栏目：PHP教程 来源：网络整理
导读：题目： 输入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 i
|
题目： 输入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;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
