- 浏览: 21905 次
- 性别:
- 来自: 南京
最新评论
给定一个十进制整数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"的个数加起来,就得到了问题的解。
view sourceprint?01 public long CountOne3(long n)
02 {
03 long i = 0,j = 1;
04 long count = 0;
05 for (i = 0; i <= n; i++)
06 {
07 j = i;
08 while (j != 0)
09 {
10 if (j % 10 == 1)
11 count++;
12 j = j / 10;
13 }
14 }
15 return count;
16 }
此方法简单,容易理解,但它的问题是效率,时间复杂度为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;
递归的出口条件为:
view sourceprint?1 if(1<n<10) return 1;
2 else if (n == 0) return 0;
基于此,编写如下代码:
view sourceprint?01 public long CountOne(long n)
02 {
03 long count = 0;
04 if (n == 0)
05 count = 0;
06 else if (n > 1 && n < 10)
07 count = 1;
08 else
09 {
10 long highest = n;//表示最高位的数字
11 int bit = 0;
12 while (highest >= 10)
13 {
14 highest = highest / 10;
15 bit++;
16 }
17
18 int weight = (int)Math.Pow(10, bit);//代表最高位的权重,即最高位一个1代表的大小
19 if (highest == 1)
20 {
21 count = CountOne(weight - 1)
22 + CountOne(n - weight)
23 + n - weight + 1;
24 }
25 else
26 {
27 count = highest * CountOne(weight - 1)
28 + CountOne(n - highest * weight)
29 + weight;
30 }
31 }
32 return count;
33 }
此算法的优点是不用遍历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。
综合以上分析,写出如下代码:
view sourceprint?01 public long CountOne2(long n)
02 {
03 long count = 0;
04 long i = 1;
05 long current = 0,after = 0,before = 0;
06 while((n / i) != 0)
07 {
08 current = (n / i) % 10;
09 before = n / (i * 10);
10 after = n - (n / i) * i;
11
12 if (current > 1)
13 count = count + (before + 1) * i;
14 else if (current == 0)
15 count = count + before * i;
16 else if(current == 1)
17 count = count + before * i + after + 1;
18
19 i = i * 10;
20 }
21 return count;
22 }
此算法的时间复杂度仅为O(lgN),且没有递归保存现场的消耗和堆栈溢出的问题。
例如: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"的个数加起来,就得到了问题的解。
view sourceprint?01 public long CountOne3(long n)
02 {
03 long i = 0,j = 1;
04 long count = 0;
05 for (i = 0; i <= n; i++)
06 {
07 j = i;
08 while (j != 0)
09 {
10 if (j % 10 == 1)
11 count++;
12 j = j / 10;
13 }
14 }
15 return count;
16 }
此方法简单,容易理解,但它的问题是效率,时间复杂度为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;
递归的出口条件为:
view sourceprint?1 if(1<n<10) return 1;
2 else if (n == 0) return 0;
基于此,编写如下代码:
view sourceprint?01 public long CountOne(long n)
02 {
03 long count = 0;
04 if (n == 0)
05 count = 0;
06 else if (n > 1 && n < 10)
07 count = 1;
08 else
09 {
10 long highest = n;//表示最高位的数字
11 int bit = 0;
12 while (highest >= 10)
13 {
14 highest = highest / 10;
15 bit++;
16 }
17
18 int weight = (int)Math.Pow(10, bit);//代表最高位的权重,即最高位一个1代表的大小
19 if (highest == 1)
20 {
21 count = CountOne(weight - 1)
22 + CountOne(n - weight)
23 + n - weight + 1;
24 }
25 else
26 {
27 count = highest * CountOne(weight - 1)
28 + CountOne(n - highest * weight)
29 + weight;
30 }
31 }
32 return count;
33 }
此算法的优点是不用遍历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。
综合以上分析,写出如下代码:
view sourceprint?01 public long CountOne2(long n)
02 {
03 long count = 0;
04 long i = 1;
05 long current = 0,after = 0,before = 0;
06 while((n / i) != 0)
07 {
08 current = (n / i) % 10;
09 before = n / (i * 10);
10 after = n - (n / i) * i;
11
12 if (current > 1)
13 count = count + (before + 1) * i;
14 else if (current == 0)
15 count = count + before * i;
16 else if(current == 1)
17 count = count + before * i + after + 1;
18
19 i = i * 10;
20 }
21 return count;
22 }
此算法的时间复杂度仅为O(lgN),且没有递归保存现场的消耗和堆栈溢出的问题。
发表评论
-
KMP快速字符串查找算法
2011-08-25 19:29 672在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
求解最大公约数问题
2011-08-25 19:27 698最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1086在程序设计相关领域, ... -
整数拆分问题的动态规划解法
2011-08-25 19:26 3073输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方 ... -
背包问题介绍与分析
2011-08-25 19:24 1032背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1292我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 699Problem 1 : Is it a loop ? ( ... -
各种排序算法的C++实现与性能比较
2011-08-25 19:21 926排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法, ... -
背包问题之硬币找零问题
2011-08-25 19:19 1176设有6 种不同面值的硬 ... -
求能被1到20的数整除的最小正整数
2011-08-25 19:18 1374求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这 ... -
买书折扣最优惠问题解法
2011-08-25 19:17 756题目:在节假日的时候 ... -
二叉树中的最近公共祖先问题
2011-08-25 19:16 1324题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1827题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1061很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
KMP快速字符串查找算法
2011-08-25 18:57 967在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 760快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
数字1亿里面有多少个1呢
2011-08-25 18:52 745乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单 ... -
最大子序列、最长公共子串、最长公共子序列
2011-08-25 18:33 794最大子序列 最大子序列是要找出由数组成的一维数组中和最大的连续 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1042阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
计算从1到n(一个正数)中,x(一个数字)出现的次数。
在本题目中,我们需要编写一个C语言程序,用于计算从1到给定正整数N之间所有整数中数字"1"出现的总次数。这是一个典型的字符串处理和数学计算问题,涉及到了数字转换、字符串遍历以及计数算法。下面我们将深入探讨这...
计算从1~n的奇数序列,统计3出现的次数,源于网络流传的一个段子。 实际上这题是Leetcode中一个题目的变种,即1~n中,1出现的次数。 该代码主要考虑缩减时间复杂性。其实原理与这个题目相同,稍作变化即可,把1换成...
)这款小工具,便以解决这样一个基础问题为己任——计算从1开始到任意整数n的和。虽然这个问题看起来简单,但在多种情况下,如数据分析、编程调试、教育演示等,一个能够迅速给出答案的工具是非常宝贵的。 等差数列...
统计数字问题 一本书的页码从自然数1 开始顺序...程序运行结束时,输出有10行,在第k行输出页码中用到数字k-1 的次数,k=1,2,…,10。 Sample Input 11 Sample Output 1;4;1;1;1;1;1;1;1;1(竖着的!)
第二行是n+1个整数,表示这n个矩阵的行数及其最后一个矩阵的列数,各个数之间用空格隔开。 #### 四、输出格式 输出应包含C行,每行对应一组测试数据的结果,即计算出的矩阵连乘积所需的最少乘法次数。 #### 五、...
在给定的问题中,我们需要计算从1到n所有整数中数字1出现的次数。这个问题是基于编程算法的,特别是与计算机科学中的动态规划和数学分析相关。它来源于LeetCode平台,这是一个练习和解决编程问题的在线平台。 首先...
在编程领域,递归函数是一种强大的工具...总的来说,理解和计算递归函数调用次数是编程中的重要技能,它涉及到算法分析、性能优化和问题解决策略等多个方面。通过熟练掌握递归,程序员能更好地应对各种复杂的编程挑战。
题目中的任务是编写一个函数来计算特定的级数和,即 \( n^1 + n^2 + n^3 + \ldots + n^{10} \),其中 \( n \) 可以取值 1、2 或 3,且函数参数的默认值为 1。这个级数实际上是一个有限等比数列的和,公式如下: \[ ...
给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重 集S中重数最大的元素称为众数。 例如,S={1,2,2,2,3,5}。 多重集S的众数是2,其重数为3。 编程任务: 对于给定的由n 个...
根据题目描述,我们面对的问题是计算一本书的所有页码中各个数字0至9出现的次数,其中这本书的页码是从自然数1开始一直到自然数n。为了解决这个问题,我们需要理解几个关键的概念和技术: ### 问题定义 对于一本...
其核心思想是遍历从1到n的每一个数字,然后逐位分解每个数字,并统计每种数字出现的次数。具体步骤如下: 1. 初始化一个大小为10的数组`count`,用于存储0至9每个数字出现的次数,初始值均为0。 2. 从1开始遍历到n...
在文件中,我们预计会看到一个或多个函数,这些函数会封装实现上述两种方法,即计算从0到N之间所有数字中1出现的总数。这些函数应该接受一个整数N作为参数,并返回相应的1的数量。在实现这些函数时,编写者需要考虑...
// 如果不存在,将其添加到HashMap中并设置出现次数为1 map.put(temp, 1); } else { // 如果存在,取出该字符的出现次数,加1后重新放入HashMap int n = map.get(temp); n += 1; map.put(temp, n); } } } ...
这个问题要求我们计算从1到n的所有整数中,数字1作为十进制表示的一部分总共出现了多少次。例如,当n=12时,1出现在1、10、11和12这四个数字中,总共出现了5次。 **解法一**: 这是一个直观的方法,通过遍历1到n的...
- 在此问题中,为了统计每个元素的出现次数,可以使用数组 `a[]` 作为计数器,数组下标表示元素值,数组值表示元素的出现次数。 #### 算法实现 - **读取数据**:首先通过 `scanf` 读取多重集 S 中元素的个数 n,...
然后,利用FOR循环结构,从1开始累乘到n。每次循环,将当前乘积与循环索引相乘,并将结果保存在变量中。最后,将计算得到的阶乘值返回到前面板的显示控件。 **三、实训步骤与要求** 1. **创建前面板**:打开...
`这样的表达式,用于计算字段中“sum”关键字的出现次数,进而推算出总和。 综上所述,选择合适的方法来统计字符串中特定字符的出现次数,需要综合考虑代码的可读性、执行效率以及资源消耗。在不同的应用场景下,应...