在csdn上面看到一道题目:
对于任意正整数n,f(n)表示从1到n中数字1出现的次数。例如f(3)=1; f(11)=4; f(13)=6;
设计一个算法来计算f(n);
最开始想到的算法是最直接的算法:对1到n的每个数字m,将m转换成字符串,计算该字符串中字符‘1’出现的次数。所有的次数的和就是计算的结果。具体算法如下:
public long countAppearTimes(long n)
{
long appearTimes = 0;
for (long i = 1; i <= n; i++)
{
String strN = String.valueOf(i);
int length = strN.length();
for (int i=0; i< length; i++)
{
if (strN.charAt(i) == ‘1’)
{
appearTimes = appearTimes + 1;
}
}
}
return appearTimes;
}
这个算法比较直接,也比较好理解,但是效率太低下。当n比较小的时候还显示不出来,但是当n比较大的时候,就十分明显了。在我的机器上,当n=999999999时,运行了540047ms,也就是9分钟的时间。
是否有比较简单、高效的算法呢?
我们来做一下转换。假设给出的n是一个m位的数字,可以表示为
a1a2a3a4a5a6......am。那么将从1到n的所有的数字都按m位编写,不足的在左端补0。具体形式如下
0 0 0 0 ...... 0 0 1
0 0 0 0 ...... 0 0 2
......
0 0 0 0 ...... 0 1 0
0 0 0 0 ...... 0 1 1
......
a1 a2 a3 a4 。。。。。。 am-2 am-1 am
我们可以发现以下的规律:
个位上的数字,每10个中就有1个1;
十位上的数字,每100个中有10个1;(10——19)
百位上的数字,每1000个中有100个1;(100——199)
依次类推,在从前向后数的第i位上的数字,每10m-i+1个中就有10m-i个1。
因此,对于n= a1a2a3a4a5a6......am;第i位的数字为ai
1. 如果ai 等于0,那么第i位上有 a1a2a3a4a5a6...... ai-1 * 10 m-i 个1。
也就是说,如果ai 等于0,那么第i位上的1的个数为n/10m-i+1*10m-i个1;
注意,/表示整除,例如132/10 = 13。以下相同。
例如:n=13059;第三位为0。那么第三位上的1共有
13059/105-3+1*105-3=1300个。即
100——199,1100——1199,2100——2199,3100——3199,4100——4199,5100——5199,6100——6199,7100——7199,8100——8199,......,13100——13199。
2. 如果ai等于1,那么从1到a1a2a3a4a5a6... ai-1099...9,第i位上的1的个数可以根据情况1计算出来。从a1a2a3a4a5a6... ai-1100...0到a1a2a3a4a5a6... ai-11 ai+1 ai+2... am 中第i位上的1的个数为 ai+1 ai+2... am+1个,即n%10m-i + 1个。(%表示取余,例如132 %10 = 2。以下相同)所以第i位上共有n/10m-i+1*10m-i + n%10m-i + 1个1。
3. 如果ai位是其他的数字,那么第i位上共有n/10m-i+1*10m-i + 10m-i =(n/10m-i+1+1)* 10m-i个1。具体的推算各位可以自己去验证。
根据这思想,就有以下的算法。
public long countAppearTimes(long n){
long times = 0;
String str = String.valueOf(n);
int length = str.length();
for (int i=0; i<length; i++){
//注意这里i是从0开始的,上面的算法描述中的是从1开始的,因此以下的程序稍有不同。
long exp = Math.round(Math.pow(10, length-i-1));
long mod = n % exp;
long div = n / exp;
long tempTimes = 0;
if (str.charAt(i)=='1'){
tempTimes = mod + 1;
tempTimes = tempTimes + (div -1) * exp / 10;
times = times + tempTimes;
}
else{
if (str.charAt(i) == '0')
tempTimes = tempTimes + div / 10 * exp;
else
tempTimes = tempTimes + (div /10 +1)*exp;
times = times + tempTimes;
}
}
return times;
}
通过验证,这个算法和最原始的算法的结果是完全相同的(验证了从1到99999999)。
这个算法的效率如何呢?当n=999999999时,运行了109ms。
分享到:
相关推荐
《CSDN嵌入式面经全集》花了N长时间,搜集了这么多CSDN上面嵌入式面试题目。希望对大家有帮助,不用一个一个下载了。
今天刚刚通过OCJP考试,感觉题目比较简单,资料里面的题目做完基本上就可以应付了,我把从CSDN还有其他上面搜到的题目全部都放到一起了。里面有一个模拟器,和真实环境里面的差不多,还有就是公认的那本考试指南,...
非常好的课件,对应的有hdu上面的题目推荐,希望大家好好练习,acm,our dream ,fighting!
下面关于“联合”的题目的输出? a) #i nclude <stdio.h><br>union { int i; char x[2]; }a; <br>void main() { a.x[0] = 10; a.x[1] = 1; printf("%d",a.i); } 答案:...
该文详细介绍了使用STM...同时,我本人在CSDN上还上传了对应程序的压缩包。叫:2016年省赛自动循迹小车STM32F103所有程序。欢迎大家下载。也欢迎大家去看我的博客,上面详细记述了用MSP430G2553完成该赛题的详细过程。
初学kettle,教程上的习题,研究好久,csdn上面还没有资料。痛苦的5个小时,终于把自己逼出来了。防止自己忘记了总结的。大神可以指点错误
C++题目有趣的跳跃的测试用例,可以使用lemon测试,也可以使用cena测试。如果有不会使用的同学可以在CSDN上面搜索这两种软件
分析:今天看到csdn博客上面的一题,说是阿里巴巴电面的题目。初看到这道题的时候,就感觉很熟悉,在高中的时候,经常要算这种组合有多少个,当时我们计算的方法顺序是这样的:3+2+1 即 a,b,c,d, ab,bc,cd,...
测绘程序设计是大题目,在测绘工作与科学研究中,很多情况下都可以使用计算机。测绘工程所涉及的数据计算、绘图、数据库管理、数据分析等,都可以使用计算机来完成。从一般含义上说,测绘工作包含计算和绘图两个方面...
上面是毕业论文,代码太乱了,就不献丑了,也不鼓励给位直接抄毕设,还是自己做吧。 ============================================= 毕业设计题目主要包括各种MIS和动态网站,其中包括一个不合格的笨蛋的。 本人的...
这个是我本人在大一下学期期间整理的C++题库,涵盖机考(2018级及以后的南区软件工大一下学期程面向对象程序设计期末考试题库)中几乎所有的题目,并配有解析,方便记忆,考试这个东西……最主要还是自己会,我自己...
前几天在CSDN看到一篇帖子,题目是“如何让自己像打王者一样发了疯,拼了命,石乐志的学习”。这里面讲到了阶段性反馈机制,我觉得蛮有意思的,正好前两天用python写了一个scrawler爬取了某XXXX软件上面的挑战答题并...
所以我们决定,应该好好的将自己做题的思路记录下来,一个知识点,自己能弄懂,写出来让大家都明白,同时能做到举一反三,触类旁通,那么在一定程度上面才算是真的掌握了。 于是就有了现在准备开始的这本书:...
注意如果派生集B的父集是另外的派生集A,那么上面所说的原始父集是集A向前回溯到最终的原始集,其顺序保持不变,并且派生集A的过滤器对派生集B仍然有效。因此,派生集的索引个数是最终原始父集的个数,索引的取值是...
题目:C0编译器的设计与实现(10周) C0语言的语法结构定义如下: <程序>->[<变量定义部分>] {<自定义函数定义部分>} <主函数> <变量定义部分>-> int id {, id}; <自定义函数定义部分>-> ( int id | void id) '...
图书馆管理系统设计报告 一、实习题目:图书馆管理系统 二、实习工具:前台开发工具选择Visual Basic 6.0;后台数据库选择Access;中间层采用ADO数据访问技术,将对数据库的操作以类的 形式封装。 三、实习目的:...
但是,鉴于很多用过mysql的用户,在刚开始使用Oracle的时候都会不知道如何创建数据库,觉得很茫然,然后开始百度、CSDN一通搜索“Oracle如何创建数据库”,所以笔者把本文的题目写成“Navicat for oracle创建数据库...
这里我将下文放到了我CSDN的博客上,可以跳转目录,看起来也方便美观一点—— 这里放一个我学习MapReduce的编程实例项目吧,本来是想把这些分开写成多篇文章的,能够详细叙述我学习过程中感想。但无奈,时间不够,...