文档章节

【九度OJ1373】|【剑指offer32】整数中1出现的次数(从1到n整数中1出现的次数)

aqia358
 aqia358
发布于 2013/10/25 11:20
字数 1946
阅读 237
收藏 1
点赞 0
评论 0

题目描述:

亲们!!我们的外国友人YZ这几天总是睡不好,初中奥数里有一个题目一直困扰着他,特此他向JOBDU发来求助信,希望亲们能帮帮他。问题是:求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有110111213因此共出现6,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

输入:

输入有多组数据,每组测试数据为一行。

每一行有两个整数a,b(0<=a,b<=1,000,000,000)

输出:

对应每个测试案例,输出ab之间1出现的次数。

样例输入:
0 5
1 13
21 55
31 99
样例输出:
1
6
4
7
分析:

次题为编程之美上的经典例题从0开始到某个数N有多少个1的变形;

方法一:
遍历0到N的每个数统计每个数中1出现的个数,但是这个算法的致命问题是效率,它的时间复杂度是O(N)*计算一个整数数字里面“1”的个数的复杂度=O(N*logN)

方法二:(参考:http://blog.csdn.net/zcsylj/article/details/6393315)

  仔细分析这个问题,给定了N,似乎就可以通过分析“小于N的数在每一位上可能出现1的次数”之和来得到这个结果。让我们来分析一下对于一个特定的N,如何得到一个规律来分析在每一位上所有出现1的可能性,并求和得到最后的f(N)。

先从一些简单的情况开始观察,看能不能总结出什么规律。

     先看1位数的情况。

      如果N=3,那么从1到3的所有数字:1、2、3,只有个位数字上可能出现1,而且只出现1次,进一步可以发现如果N是个位数,如果N>=1,那么f(N)都等于1,如果N=0,则f(N)为0。

     再看2位数的情况。

     如果N=13,那么从1到13的所有数字:1、2、3、4、5、6、7、8、9、10、11、12、13,个位和十位的数字上都可能有1,我们可以将它们 分开考虑,个位出现1的次数有两次:1和11,十位出现1的次数有4次:10、11、12和13,所以f(N)=2+4=6。要注意的是11这个数在十位和个位都出现了1,但是11恰好在个位为1和十位为1中被计算了两次,所以不用特殊处理,是对的。再 考虑N=23的情况,它和N=13有点不同,十位出现1的次数为10次,从10到19,个位出现1的次数1、11、21,所以f(N)=3+10=13。 通过对两位数进行分析,我们发现,个位出现1的次数不仅和个位数字有关,还和十位数有关:如果N的个位数大于等于1,则个位出现1的次数为十位数的数字加 1;如果N的个位数为0,则个位出现1的次数等于十位数的数字。而十位数字上出现1的次数不仅和十位数有关,还和个位数有关:如果十位数字等于1,则十位 数上出现1的次数为个位数的数字加1;如果十位数大于1,则十位数上出现1的次数为10。

     例如:

            f(13)=个位出现1的个数+十位出现1的个数=2+4=6;

            f(23)=个位出现1的个数+十位出现1的个数=3+10=13;

            f(33)=个位出现1的个数+十位出现1的个数=4+10=14;

              ……

            f(93)=个位出现1的个数+十位出现1的个数=10+10=20;

 

     接着分析3位数。

      如果N=123:

     个位出现1的个数为13:1,11,21,…,91,101,111,121

     十位出现1的个数为20:10~19,110~119

      百位出现1的个数为24:100~123

     f(123)=个位出现1的个数+十位出现1的个数+百位出现1的次数=13+20+24=57;

     同理我们可以再分析4位数、5位数。

    读者朋友们可以写一写,总结一下各种情况有什么不同。

 

     根据上面的一些尝试,下面我们推导出一般情况下,从N得到f(N) 的计算方法:

     假设N=abcde,这里a、b、c、d、e分别是十进制数N的各个位数上的数字。如果要计算百位上出现1的次数,它将会受到三个因素的影响:百位上的数字,百位以下(低位)的数字,百位(更高位)以上的数字。

     如果百位上的数字为0,则可以知道,百位上可能出现1的次数由更高位决定,比如12013,则可以知道百位出现1的情况可能是100~199,1 100~1 199,2 100~2 199,…,11 100~11 199,一共有1200个。也就是由更高位数字(12)决定,并且等于更高位数字(12)*当前位数(100)。

      如果百位上的数字为1,则可以知道,百位上可能出现1的次数不仅受更高位影响,还受低位影响,也就是由更高位和低位共同决定。例如对于12113,受更高位影响,百位出现1的情况是100~199,1 100~1 199,2 100~2 199,…,11 100~11 199,一共有1200个,和上面第一种情况一样,等于更高位数字(12)*当前位数(100)。它还受低位影响,百位出现1的情况是12 100~12 113,一共114个,等于低位数字(113)+1。

     如果百位上数字大于1(即为2~9),则百位上可能出现1的次数也仅由更高位决定,比如12 213,则百位出现1的可能性为100~199,1 100~1 199,2 100~2 199,…,11 100~11 199,12 100~12 199,一共有1300个,并且等于更高位数字+1(12+1)*当前位数(100)。

      通过上面的归纳和总结,我们可以写出如下的更高效算法来计算f(N):

   ‍其算法思路是:通过对数字进行有规律的总结,发现从1到N,中出现的所有的1的总数。可以从N这个数总结出来的。

      那么出现1的总数应该等于,个位上出现1的次数+十位上出现1的次数+百位上出现1的次数+。。。。。。

     所以对于一个数abcde,取百位上的c来计算,

              假若c是"1",那么百位上1的个数是由他的高位和低位来决定的。等于ab*100+cde+1;

              假若c是"0",那么百位上1的个数是ab*100;

               假如c是大于1,那么 百位上1的个数是(ab+1)*100;

Java实现:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {

	public static int sum(int n){
		if(n < 1)return 0;
		int count = 0;
		int Factor = 1;
		int LowerNum = 0;
		int CurrNum = 0;
		int HigherNum = 0;
		while(n/Factor != 0){
			LowerNum = n - (int)Math.floor(n/Factor)*Factor;
			CurrNum = (n/Factor)%10;
			HigherNum = n/(Factor*10);
			switch(CurrNum){
				case 0:
					count += HigherNum*Factor;
					break;
				case 1:
					count += HigherNum*Factor + LowerNum + 1;
					break;
				default:
					count += (HigherNum + 1) * Factor;
					break;
			}
			Factor *= 10;
		}
		return count;
	}
	public static void main(String[] args) throws IOException {
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		while(st.nextToken() != StreamTokenizer.TT_EOF){
			int a = (int) st.nval;
			st.nextToken();
			int b = (int) st.nval;
			if(a < b)
				System.out.println(sum(b) - sum(a-1));
			else
				System.out.println(sum(a) - sum(b-1));
		}
		
	}

}






© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 81
码字总数 30297
作品 0
海淀
程序员
海量数据处理之面试题

给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? 方案1:可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G。所以不可能将...

huangqjduter ⋅ 2017/03/02 ⋅ 0

python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905 ⋅ 06/03 ⋅ 0

编程题——31~40

三十一、连续子数组的最大和 输入一个整数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 三十二、从1到n整数中...

thanatos_y ⋅ 2016/07/26 ⋅ 0

在从 1 到 n 的正数中 1 出现的次数

题目: 输入一个整数 n,求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。 例如输入 12,从 1 到 12 这些整数中包含 1 的数字有 1, 10, 1 1 和 12, 1 一共出现了 5 次 代码实现(G...

Zhang_H ⋅ 2014/05/18 ⋅ 2

海量数据处理:十道面试题与十个海量数据处理方法总结

1、海量日志数据,提取出某日访问百度次数最多的那个IP。 首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射...

ahucsxl ⋅ 2015/10/08 ⋅ 0

高效的算法求解一个序列的主元素

题目描述: 已知一个整数序列A={a0,a1,a2,...an-1} 其中0<=ai<n(0<=i<n).若存在 ap1=ap2=...=apm=x且m>n/2(0<=pk<n,1<=k<=m),则称x为A的主元素。如 A={0,5,5,3,5,7,5,5},则5为主元素,又如A={......

XJ_hello ⋅ 2016/12/19 ⋅ 0

十道海量数据处理面试题与十个方法大总结

海量数据处理:十道面试题与十个海量数据处理方法总结 本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。 出处:http://blog.csdn.net/vJULYv。 第一部分、十道海量数据处理面试题...

吟啸_徐行 ⋅ 2014/04/02 ⋅ 2

UVA ~ 11235 ~ Frequent values (RMQ + 游程编码)

题意:给出一个非降序排列的整数数组a1,a2,...,an,你的任务是对于一系列询问(i,j),回答ai,ai+1,...,aj中出现次数最多的值出现的次数。 【输入格式】 输入包含多组数据。每组数据每一...

zscdst ⋅ 05/04 ⋅ 0

海量数据题

1、海量日志数据,提取出某日访问百度次数最多的那个IP。 首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射...

GM_LV ⋅ 2012/10/22 ⋅ 0

C语言编程练习——出现次数最多的数

/问题描述:出现次数最多的数   给定n个正整数,找出它们中出现次数最多的数。如果这样的数有多个,请输出其中最小的一个。 输入格式   输入的第一行只有一个正整数n(1 ≤ n ≤ 1000),表...

风一样的程序媛 ⋅ 2016/03/29 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

RabbitMQ学习以及与Spring的集成(三)

本文介绍RabbitMQ与Spring的简单集成以及消息的发送和接收。 在RabbitMQ的Spring配置文件中,首先需要增加命名空间。 xmlns:rabbit="http://www.springframework.org/schema/rabbit" 其次是模...

onedotdot ⋅ 27分钟前 ⋅ 0

JAVA实现仿微信红包分配规则

最近过年发红包拜年成为一种新的潮流,作为程序猿对算法的好奇远远要大于对红包的好奇,这里介绍一种自己想到的一种随机红包分配策略,还请大家多多指教。 算法介绍 一、红包金额限制 对于微...

小致dad ⋅ 39分钟前 ⋅ 0

Python 数电表格格式化 xlutils xlwt xlrd的使用

需要安装 xlutils xlwt xlrd 格式化前 格式化后 代码 先copy读取的表格,然后按照一定的规则修改,将昵称中的学号提取出来替换昵称即可 from xlrd import open_workbookfrom xlutils.copy ...

阿豪boy ⋅ 今天 ⋅ 0

面试题:使用rand5()生成rand7()

前言 读研究生这3 年,思维与本科相比变化挺大的,这几年除了看论文、设计方案,更重要的是学会注重先思考、再实现,感觉更加成熟吧,不再像个小P孩,人年轻时总会心高气傲。有1 道面试题:给...

初雪之音 ⋅ 今天 ⋅ 0

Docker Toolbox Looks like something went wrong

Docker Toolbox 重新安装后提示错误:Looks like something went wrong in step ´Checking if machine default exists´ 控制面板-->程序与应用-->启用或关闭windows功能:找到Hyper-V,如果处......

随你疯 ⋅ 今天 ⋅ 0

Guacamole 远程桌面

本文将Apache的guacamole服务的部署和应用,http://guacamole.apache.org/doc/gug/ 该链接下有全部相关知识的英文文档,如果水平ok,可以去这里仔细查看。 一、简介 Apache Guacamole 是无客...

千里明月 ⋅ 今天 ⋅ 0

nagios 安装

Nagios简介:监控网络并排除网络故障的工具:nagios,Ntop,OpenVAS,OCS,OSSIM等开源监控工具。 可以实现对网络上的服务器进行全面的监控,包括服务(apache、mysql、ntp、ftp、disk、qmail和h...

寰宇01 ⋅ 今天 ⋅ 0

AngularDart注意事项

默认情况下创建Dart项目应出现以下列表: 有时会因为不知明的原因导致列表项缺失: 此时可以通过以下步骤解决: 1.创建项目涉及到的包:stagehand 2.执行pub global activate stagehand或pub...

scooplol ⋅ 今天 ⋅ 0

Java Web如何操作Cookie的添加修改和删除

创建Cookie对象 Cookie cookie = new Cookie("id", "1"); 修改Cookie值 cookie.setValue("2"); 设置Cookie有效期和删除Cookie cookie.setMaxAge(24*60*60); // Cookie有效时间 co......

二营长意大利炮 ⋅ 今天 ⋅ 0

【每天一个JQuery特效】淡入淡出显示或隐藏窗口

我是JQuery新手爱好者,有时间就练练代码,防止手生,争取每天一个JQuery练习,在这个博客记录下学习的笔记。 本特效主要采用fadeIn()和fadeOut()方法显示淡入淡出的显示效果显示或隐藏元...

Rhymo-Wu ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部