国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 剑指offer 面试题32―从1到n整数中1出现的次数

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

来源:程序员人生   发布时间:2015-05-04 09:51:17 阅读次数:3110次

题目:

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

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生