热门标签 | HotTags
当前位置:  开发笔记 > 人工智能 > 正文

从1到N这N个数中1的出现了多少次?

给定一个十进制整数N,求出从1到N的所有整数中出现1的个数。例如:N2,1,2出现了1个1。N12,1,2,3,4,5,6,7,8,9,10,11,12。出现了5个1。最直接的方法就是从1开始遍历到N,将其中每一个数中含有1的个数加起来,就得到了问题的解。

给定一个十进制整数N,求出从1到N的所有整数中出现"1"的个数。

例如:N=2,1,2出现了1个"1"。

N=12,1,2,3,4,5,6,7,8,9,10,11,12。出现了5个"1"。

最直接的方法就是从1开始遍历到N,将其中每一个数中含有"1"的个数加起来,就得到了问题的解。

public long CountOne3(long n)
{
	long i = 0,j = 1;
	long count = 0;
	for (i = 0; i <= n; i++)
	{
		j = i;
		while (j != 0)
		{
			if (j % 10 == 1)
				count++;
			j = j / 10;
		}
	}
	return count;
}

此方法简单,容易理解,但它的问题是效率,时间复杂度为O(N * lgN),N比较大的时候,需要耗费很长的时间。

我们重新分析下这个问题,对于任意一个个位数n,只要n>=1,它就包含一个"1";n<1,即n=0时,则包含的"1"的个数为0。于是我们考虑用分治的思想将任意一个n位数不断缩小规模分解成许多个个位数,这样求解就很方便。

但是,我们该如何降低规模?仔细分析,我们会发现,任意一个n位数中"1"的个位可以分解为两个n-1位数中"1"的个数的和加上一个与最高位数相关的常数C。例如,f(12) = f(10 - 1) + f(12 - 10) + 3,其中3是表示最高位为1的数字个数,这里就是10,11,12;f(132)=f(100 -1) + f(132 - 100) + 33,33代表最高位为1的数字的个数,这里就是100~132;f(232) = 2*f(100 - 1) + f(32) + 100,因为232大于199,所以它包括了所有最高位为1的数字即100~199,共100个。

综上,我们分析得出,最后加的常数C只跟最高位n1是否为1有关,当最高位为1时,常数C为原数字N去掉最高位后剩下的数字+1,当最高位为1时,常数C为10bit,其中bit为N的位数-1,如N=12时,bit=1,N=232时,bit=2。

于是,我们可以列出递归方程如下:

if(n1 == 1)
f(n) = f(10bit-1) + f(n - 10bit) + n - 10bit+ 1;
else
f(n) = n1*f(10bit-1) + f(n – n1*10bit) + 10bit;

递归的出口条件为:

if(1
	
	

基于此,编写如下代码:

public long CountOne(long n)
{ 
	long count = 0;
	if (n == 0)
		count = 0;
	else if (n > 1 && n <10)
		count =  1;
	else
	{
		long highest = n;//表示最高位的数字
		int bit = 0;
		while (highest >= 10)
		{
			highest = highest / 10;
			bit++;
		}
		int weight = (int)Math.Pow(10, bit);//代表最高位的权重,即最高位一个1代表的大小
		if (highest == 1)
		{
			count = CountOne(weight - 1)
			+ CountOne(n - weight)
			+ n - weight + 1;
		}
		else
		{
      		count = highest * CountOne(weight - 1)
    		+ CountOne(n - highest * weight)
        	+ weight;
		}
	}
	return count;
}

此算法的优点是不用遍历1~N就可以得到f(N)。经过我测试,此算法的运算速度比解法一快了许多许多,数字在1010内时,算法都可以在毫秒级内结束,而解法一在计算109时,时间超过了5分钟。但此算法有一个显著的缺点就是当数字超过1010时会导致堆栈溢出,无法计算。

还有就是,我尝试了许久也没有计算出此算法的时间复杂度到底是多少,似乎是O(lg2N),我并不确定,希望知道的高手能给予解答。

解法二告诉我们1~ N中"1"的个数跟最高位有关,那我们换个角度思考,给定一个N,我们分析1~N中的数在每一位上出现1的次数的和,看看每一位上"1"出现的个数的和由什么决定。

1位数的情况:在解法二中已经分析过,大于等于1的时候,有1个,小于1就没有。

2位数的情况:N=13,个位数出现的1的次数为2,分别为1和11,十位数出现1的次数为4,分别为10,11,12,13,所以f(N) = 2+4。N=23,个位数出现的1的次数为3,分别为1,11,21,十位数出现1的次数为10,分别为10~19,f(N)=3+10。

由此我们发现,个位数出现1的次数不仅和个位数有关,和十位数也有关,如果个位数大于等于1,则个位数出现1的次数为十位数的数字加1;如果个位数为0,个位数出现1的次数等于十位数数字。而十位数上出现1的次数也不仅和十位数相关,也和个位数相关:如果十位数字等于1,则十位数上出现1的次数为个位数的数字加1,假如十位数大于1,则十位数上出现1的次数为10。

3位数的情况:

N=123,个位出现1的个数为13:1,11,21,…,91,101,111,121。十位出现1的个数为20:10~19,110~119。百位出现1的个数为24:100~123。

我们可以继续分析4位数,5位数,推导出下面一般情况: 假设N,我们要计算百位上出现1的次数,将由三部分决定:百位上的数字,百位以上的数字,百位一下的数字。

如果百位上的数字为0,则百位上出现1的次数仅由更高位决定,比如12013,百位出现1的情况为100~199,1100~1199,2100~2199,…,11100~11199,共1200个。等于更高位数字乘以当前位数,即12 * 100。

如果百位上的数字大于1,则百位上出现1的次数仅由更高位决定,比如12213,百位出现1的情况为100~199,1100~1199,2100~2199,…,11100~11199,12100~12199共1300个。等于更高位数字加1乘以当前位数,即(12 + 1)*100。

如果百位上的数字为1,则百位上出现1的次数不仅受更高位影响,还受低位影响。例如12113,受高位影响出现1的情况:100~199,1100~1199,2100~2199,…,11100~11199,共1200个,但它还受低位影响,出现1的情况是12100~12113,共114个,等于低位数字113+1。

综合以上分析,写出如下代码:

public long CountOne2(long n)
{
	long count = 0;
	long i = 1;
	long current = 0,after = 0,before = 0;
	while((n / i) != 0)
	{           
		current = (n / i) % 10;
		before = n / (i * 10);
		after = n - (n / i) * i;
		if (current > 1)
			count = count + (before + 1) * i;
		else if (current == 0)
			count = count + before * i;
		else if(current == 1)
			count = count + before * i + after + 1;
		i = i * 10;
	}
	return count;
}

此算法的时间复杂度仅为O(lgN),且没有递归保存现场的消耗和堆栈溢出的问题。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1064,欢迎访问原出处。


推荐阅读
  • Søren Kierkegaard famously stated that life can only be understood in retrospect but must be lived moving forward. This perspective delves into the intricate relationship between our lived experiences and our reflections on them. ... [详细]
  • 计算机网络复习:第五章 网络层控制平面
    本文探讨了网络层的控制平面,包括转发和路由选择的基本原理。转发在数据平面上实现,通过配置路由器中的转发表完成;而路由选择则在控制平面上进行,涉及路由器中路由表的配置与更新。此外,文章还介绍了ICMP协议、两种控制平面的实现方法、路由选择算法及其分类等内容。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
  • 探讨一个显示数字的故障计算器,它支持两种操作:将当前数字乘以2或减去1。本文将详细介绍如何用最少的操作次数将初始值X转换为目标值Y。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 本文探讨如何设计一个安全的加密和验证算法,确保生成的密码具有高随机性和低重复率,并提供相应的验证机制。 ... [详细]
  • 深入解析:手把手教你构建决策树算法
    本文详细介绍了机器学习中广泛应用的决策树算法,通过天气数据集的实例演示了ID3和CART算法的手动推导过程。文章长度约2000字,建议阅读时间5分钟。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
  • 在给定的数组中,除了一个数字外,其他所有数字都是相同的。任务是找到这个唯一的不同数字。例如,findUniq([1, 1, 1, 2, 1, 1]) 返回 2,findUniq([0, 0, 0.55, 0, 0]) 返回 0.55。 ... [详细]
  • 本文探讨了卷积神经网络(CNN)中感受野的概念及其与锚框(anchor box)的关系。感受野定义了特征图上每个像素点对应的输入图像区域大小,而锚框则是在每个像素中心生成的多个不同尺寸和宽高比的边界框。两者在目标检测任务中起到关键作用。 ... [详细]
  • 网络攻防实战:从HTTP到HTTPS的演变
    本文通过一系列日记记录了从发现漏洞到逐步加强安全措施的过程,探讨了如何应对网络攻击并最终实现全面的安全防护。 ... [详细]
  • 本文深入探讨了Linux系统中网卡绑定(bonding)的七种工作模式。网卡绑定技术通过将多个物理网卡组合成一个逻辑网卡,实现网络冗余、带宽聚合和负载均衡,在生产环境中广泛应用。文章详细介绍了每种模式的特点、适用场景及配置方法。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
author-avatar
mobiledu2502912677
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有