- 浏览: 21242 次
- 性别:
- 来自: 南京
最新评论
给定一个十进制整数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 640在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
求解最大公约数问题
2011-08-25 19:27 661最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1058在程序设计相关领域, ... -
整数拆分问题的动态规划解法
2011-08-25 19:26 3034输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方 ... -
背包问题介绍与分析
2011-08-25 19:24 1001背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1264我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 672Problem 1 : Is it a loop ? ( ... -
各种排序算法的C++实现与性能比较
2011-08-25 19:21 890排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法, ... -
背包问题之硬币找零问题
2011-08-25 19:19 1129设有6 种不同面值的硬 ... -
求能被1到20的数整除的最小正整数
2011-08-25 19:18 1337求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这 ... -
买书折扣最优惠问题解法
2011-08-25 19:17 720题目:在节假日的时候 ... -
二叉树中的最近公共祖先问题
2011-08-25 19:16 1293题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1789题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1034很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
KMP快速字符串查找算法
2011-08-25 18:57 939在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 728快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
数字1亿里面有多少个1呢
2011-08-25 18:52 710乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单 ... -
最大子序列、最长公共子串、最长公共子序列
2011-08-25 18:33 754最大子序列 最大子序列是要找出由数组成的一维数组中和最大的连续 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1016阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
计算从1到n(一个正数)中,x(一个数字)出现的次数。
给定一个十进制正整数N,程序输出从1到N的所有整数中,“1”出现的个数。C语言程序附带实验报告
计算从1~n的奇数序列,统计3出现的次数,源于网络流传的一个段子。 实际上这题是Leetcode中一个题目的变种,即1~n中,1出现的次数。 该代码主要考虑缩减时间复杂性。其实原理与这个题目相同,稍作变化即可,把1换成...
第一行为一个整数C,表示有C组测试数据,接下来有2*C行数据,每组测试数据占2行,每组测试数据第一行是1个整数n,表示有n个矩阵连乘,接下来一行有n+1个数,表示是n个矩阵的行及第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个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重 集S中重数最大的元素称为众数。 例如,S={1,2,2,2,3,5}。 多重集S的众数是2,其重数为3。 编程任务: 对于给定的由n 个...
给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。 例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。 编程任务: 对于给定的由n 个自然数组成的...
编写一个方法,计算从 0 到 n (含 n) 中数字 2 出现的次数。 示例: 输入: 25 输出: 9 解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次) 提示: n <= 10^9 来源:力扣(LeetCode) 链接:...
对于给定的n和k个加油站位置,编程计算最少加油次数。 Input 输入由多组测试数据组成。 每组测试数据输入的第一行有2 个正整数n和k,表示汽车加满油后可行驶n公里,且旅途中有k个加油站。接下来的1 行中,有k+1 ...
设T[0:n-1]是n个元素的数组,如果其中某个元素x在整个数组中的出现次数超过n/2,则称x为数组T的主元素。输入数据由文件名为input.txt的文本文件提供。 请设计一个线性时间算法,判断input中的数据是否存在主元素。在...
根据题目要求使用递归函数,根据题目给定的数学算式,求出Succ(n)的值。可以在每一次调用递归函数时增加一个计数器,用来计算调用了多少次函数,最后输出Succ(n)的值和调用递归函数次数的值。
:给定含有n 个元素的多重集合S,每个元素在S 中出现的次数称为该 元素的重数。多重集S 中重数最大的元素成为众数。例如,S={1,2,2,2,3,5}。多 重集S 的众数是2,其重数为3。 算法设计:对于给定的由n 个自然数组成...
给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。 例如,S={1,2,2,2,3,5}。 多重集S的众数是2,其重数为3。 编程任务: 对于给定的由n 个...
n个矩阵连成,用动态规划的方法计算,找楚醉优加栝号方式,使总的乘法次数最少。
c代码-计算数字出现的次数
众数问题 问题描述: 给定含有 n 个元素的多重集合 S,每个元素在 S 中出现的次数称为该元素的重数。多重集 S 中重数最大的元素称为众数。 例如,S={1,2,2,2,3,5}。 多重集 S 的众数是 2,其重数为 3。 ...
计算顺序数列某一数字出现的个数,可以计算数列0,1,2,3。。。n中某一个数字(0~9)出现的次数
黑色星期五是指某天既是13号又是星期五。13号在星期五的情况比在...给出n年的一个周期,要求计算从1900年1月1日至1900+n-1年12月31日中13号落在周一到周日的次数,n为正整数且不大于400,(已知1900年1月1日是星期一)