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

题目:

输入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;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 剑指offer 面试题32―从1到n整数中1出现的次数

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡