题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12,从1到12这些整数中包含1
的数字有1,10,11和12,1一共出现了5次。
分析:这是一道广为流传的google面试题。用最直观的方法求解并不是很难,但遗憾的是效率不是很高;而要得出一个效率较高的算法,需要比较强的分析能力,并不是件很容易的事情。当然,google的面试题中简单的也没有几道。
首先我们来看最直观的方法,分别求得1到n中每个整数中1出现的次数。而求一个整数的十进制表示中1出现的次数,就和本面试题系列的第22题很相像了。我们每次判断整数的个位数字是不是1。如果这个数字大于10,除以10之后再判断个位数字是不是1。基于这个思路,不难写出如下的代码:
intNumberOf1(unsigned
int n);
/////////////////////////////////////////////////////////////////////////////
//Find the number of 1 in the integers between 1 and n
//Input: n - an integer
//Output: the number of 1 in the integers between 1 and n
/////////////////////////////////////////////////////////////////////////////
intNumberOf1BeforeBetween1AndN_Solution1(unsigned
intn)
{
int number =0;
//Find the number of 1 in each integer between 1 and n
for(unsigned
int i = 1; i <= n; ++ i)
number += NumberOf1(i);
return number;
}
/////////////////////////////////////////////////////////////////////////////
//Find the number of 1 in an integer with radix 10
//Input: n - an integer
//Output: the number of 1 in n with radix
/////////////////////////////////////////////////////////////////////////////
intNumberOf1(unsigned
int n)
{
int number =0;
while(n)
{
if(n % 10 ==1)
number ++;
n= n / 10;
}
return number;
}
这个思路有一个非常明显的缺点就是每个数字都要计算1在该数字中出现的次数,因此时间复杂度是O(n)。当输入的n非常大的时候,需要大量的计算,运算效率很低。我们试着找出一些规律,来避免不必要的计算。
我们用一个稍微大一点的数字21345作为例子来分析。我们把从1到21345的所有数字分成两段,即1-1235和1346-21345。
先来看1346-21345中1出现的次数。1的出现分为两种情况:一种情况是1出现在最高位(万位)。从1到21345的数字中,1出现在10000-19999这10000个数字的万位中,一共出现了10000(104)次;另外一种情况是1出现在除了最高位之外的其他位中。例子中1346-21345,这20000个数字中后面四位中1出现的次数是2000次(2*103,其中2的第一位的数值,103是因为数字的后四位数字其中一位为1,其余的三位数字可以在0到9这10个数字任意选择,由排列组合可以得出总次数是2*103)。
至于从1到1345的所有数字中1出现的次数,我们就可以用递归地求得了。这也是我们为什么要把1-21345分为1-1235和1346-21345两段的原因。因为把21345的最高位去掉就得到1345,便于我们采用递归的思路。
分析到这里还有一种特殊情况需要注意:前面我们举例子是最高位是一个比1大的数字,此时最高位1出现的次数104(对五位数而言)。但如果最高位是1呢?比如输入12345,从10000到12345这些数字中,1在万位出现的次数就不是104次,而是2346次了,也就是除去最高位数字之后剩下的数字再加上1。
基于前面的分析,我们可以写出以下的代码。在参考代码中,为了编程方便,我把数字转换成字符串了。
#include
"string.h"
#include
"stdlib.h"
intNumberOf1(const
char* strN);
intPowerBase10(unsigned
int n);
/////////////////////////////////////////////////////////////////////////////
//Find the number of 1 in an integer with radix 10
//Input: n - an integer
//Output: the number of 1 in n with radix
/////////////////////////////////////////////////////////////////////////////
intNumberOf1BeforeBetween1AndN_Solution2(int
n)
{
if(n <= 0)
return 0;
//convert the integer into a string
charstrN[50];
sprintf(strN, "%d", n);
return NumberOf1(strN);
}
/////////////////////////////////////////////////////////////////////////////
//Find the number of 1 in an integer with radix 10
//Input: strN - a string, which represents an integer
//Output: the number of 1 in n with radix
/////////////////////////////////////////////////////////////////////////////
intNumberOf1(const
char* strN)
{
if(!strN || *strN <
'0' || *strN >
'9' || *strN ==
'\0')
return 0;
intfirstDigit = *strN -
'0';
unsigned
int length =
static_cast<unsigned
int>(strlen(strN));
//the integer contains only one digit
if(length ==1 && firstDigit == 0)
return 0;
if(length == 1 &&firstDigit > 0)
return 1;
//suppose the integer is 21345
// numFirstDigit is the number of 1 of 10000-19999 due tothe first digit
intnumFirstDigit = 0;
// numOtherDigits is the number of 1 01346-21345 due to alldigits
// except the first one
intnumOtherDigits = firstDigit * (length - 1) * PowerBase10(length - 2);
// numRecursive is the number of 1 of integer 1345
intnumRecursive = NumberOf1(strN + 1);
//if the first digit is greater than 1, suppose in integer 21345
// number of 1 due to the first digit is 10^4. It's10000-19999
if(firstDigit> 1)
numFirstDigit = PowerBase10(length - 1);
//if the first digit equals to 1, suppose in integer 12345
// number of 1 due to the first digit is 2346. It's10000-12345
else
if(firstDigit == 1)
numFirstDigit = atoi(strN + 1) + 1;
return numFirstDigit +numOtherDigits + numRecursive;
}
/////////////////////////////////////////////////////////////////////////////
//Calculate 10^n
/////////////////////////////////////////////////////////////////////////////
intPowerBase10(unsigned
int n)
{
int result =1;
for(unsigned
int i = 0; i < n; ++ i)
result *= 10;
return result;
}
分享到:
相关推荐
计算从1到n(一个正数)中,x(一个数字)出现的次数。
在从 1 到 n 的正数中 1 出现的次数 题目: 输入一个整数 n,求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。 例如输入 12,从 1 到 12 这些整数中包含 1 的数字有 1, 10, 1 1 和 12, 1 一共出现了 5 次 ...
5.15 数据段中已定义了一个有N个字数据的数组M,试编写一程序求出M中绝对值最大的数,把它放在数据段的M+2n单元中,并将该数的偏移地址存放在M+2(n+1)单元中。 5.16 在首地址为DATA的字数组中,存放了100H个16位...
一开始任选一个正整数m作为报数上限值,从第一个人开始按顺时针报数,报到m时停止,报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。...
53.数字在排序数组中出现的次数 Binary Search 常考 54.二叉搜索树中的第k个结点 Tree 55.二叉树的深度 Tree 55.平衡二叉树 Tree 56.数组中只出现一次的数字 Array 57.和为S的两个数字 Array 57.和为S的连续...
scanf函数 scanf函数称为格式输入函数,即按用户指定的格式从键盘上把数据输入到指定的变量之中。 一、scanf函数的一般形式 scanf函数是一个标准库函数,它的函数原型在头文件“stdio.h”中,与printf函数相同,...
假设有一批产品,总数为N,其中不合格数为d,从这批产品中随机地抽出n件作为被检样品,样品中的不合格数X服从的分布称超几何分布。 X的分布概率为: X=0,1,…… X的期望 E(X)=nd/N X的方差 D(X)=((nd...
13. 下面程序段中带有下划线的语句的执行次数的数量级是( ) 【合肥工业大学 2001 三、1(2分)】 i:=n*n WHILE i<>1 DO i:=i div 2; 14. 计算机执行下面的语句时,语句 s的执行次数为 _______ 。【南京理工大学 ...
在LINGO中,只有在初始部分中给出的集属性值在以后的求解中可更改。这与前面并不矛盾,初始部分是LINGO求解器的需要,并不是描述问题所必须的。 2.3.2 定义派生集 为了定义一个派生集,必须详细声明: •集的名字 •...
(3) 编制另一个主函数以及计算被积函数值的函数f(x),在主函数中调用(1)中的函数计算并输出下列积分值。要求主函数与函数f(x)在同一个文件中。 说明: 用梯形法求定积分,梯形公式为 s=h[f(a)+f(b)]/2+hf(a+kh)其中...
内容及步骤: 1、 设有一个线性表(e0,e1,e2,e3,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置,即将数组的前n个原地址内容置换为(en-1,en-2,…,e3,...
因此42在其位置1,3,5的值为1(从右边以0开始数);这样42是21+23+25的和,也即是2+8+32 。 所有的整数类型(除了char 类型之外)都是有符号的整数。这意味着他们既能表示正数,又能表示负数。Java 使用大家知道的...
1.4.8. 计算 1 到 N 的十进制数中 1 的出现次数 ............................................. 97 1.4.9. 栈的 push、pop 序列[数据结构] .......................................................... 99 1.4.10....
由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。 3.最小的K个数 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 4.连续子...
补码= 反码 +1 正数=负数的补码(反码+1) 反码= 非(二进制数) 八进制数,零开头 011(八进制)=9(十进制) 十六进制数,零x开头 0x55(十六进制)=5*16+5(十进制) 类型:数据都必须有类型 boolean (8bit,不定...
的出现次数作为从 0 到 n 的数字中的数字 第 4 天:01-03-20 二和问题 字符串中所有数字的总和 第 5 天:16-03-20 在 O(n) 中分离数组中的正数和负数 最小对数的最大值 第 6 天 : 20-03-20 快速排序 递归冒泡排序 第...
negative.cpp-以恒定的额外空间将所有负数移动到开始并以正数结束的程序-O(n) 交集.cpp-查找两个数组交集的程序-O(n + m)n-数组1的大小,m-数组2的大小 union.cpp-查找两个数组的并集的程序-O(n + m)n-数组1...
多项式中除常数项外的每一项的形式为AnxN,其中An(-100)是一个整数,表示该项的系数,x是变量名,N(0<=N)是该项的次数。首项系数为正数时,系数前的’+’省略;当首相系数为负数时,负号与整数之间没有空格;系数为...
打印从1到最大的n位数 5、21. 调整数组顺序使奇数位于偶数前面 6、29. 顺时针打印矩阵 7、39. 数组中出现次数超过一半的数字 8、57. 和为s的两个数字 9、57-II. 和为s的连续正数序列 10、 58-I. 翻转单词顺序 11、58...
多项式中除常数项外的每一项的形式为AnxN,其中An(-100)是一个整数,表示该项的系数,x是变量名,N(0<=N)是该项的次数。首项系数为正数时,系数前的’+’省略;当首相系数为负数时,负号与整数之间没有空格;系数为0...