首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。 例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。
输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。 例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。
admin
2019-03-29
134
问题
输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。
选项
答案
#include "string.h" #include "stdlib.h" int NumberOf1(const char* strN); int PowerBase10(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 ///////////////////////////////////////////////////////////////////////////// int NumberOf1BeforeBetween1AndN_Solution2(int n) { if(n <= 0) return 0; // convert the integer into a string char strN[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 ///////////////////////////////////////////////////////////////////////////// int NumberOf1(const char* strN) { if(!strN || *strN < ’0’ || *strN > ’9’ || *strN == ’\0’) return 0; int firstDigit = *strN - ’0’; unsigned int length = static_cast
(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 to the first digit int numFirstDigit = 0; // numOtherDigits is the number of 1 01346-21345 due to all digits // except the first one int numOtherDigits = firstDigit * (length - 1) * PowerBase10(length - 2); // numRecursive is the number of 1 of integer 1345 int numRecursive = 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’s 10000-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’s 10000-12345 else if(firstDigit == 1) numFirstDigit = atoi(strN + 1) + 1; return numFirstDigit + numOtherDigits + numRecursive; } ///////////////////////////////////////////////////////////////////////////// // Calculate 10^n ///////////////////////////////////////////////////////////////////////////// int PowerBase10(unsigned int n) { int result = 1; for(unsigned int i = 0; i < n; ++ i) result *= 10; return result; }
解析
这是一道广为流传的google面试题。用最直观的方法求解并不是很难,但遗憾的是效率不是很高;而要得出一个效率较高的算法,需要比较强的分析能力,并不是件很容易的事情。当然,google的面试题中简单的也没有几道。
首先我们来看最直观的方法,分别求得1到n中每个整数中1出现的次数。而求一个整数的十进制表示中1出现的次数,就和本面试题系列的第22题很相像了。我们每次判断整数的个位数字是不是1。如果这个数字大于10,除以10之后再判断个位数字是不是1。基于这个思路,不难写出如下的代码:
int NumberOf1(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
/////////////////////////////////////////////////////////////////////////////
int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n)
{
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
/////////////////////////////////////////////////////////////////////////////
int NumberOf1(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(10
4
)次;另外一种情况是1出现在除了最高位之外的其他位中。例子中1346-21345,这20000个数字中后面四位中1出现的次数是2000次(2*10
3
,其中2的第一位的数值,10
3
是因为数字的后四位数字其中一位为1,其余的三位数字可以在0到9这10个数字任意选择,由排列组合可以得出总次数是2*10
3
)。
至于从1到1345的所有数字中1出现的次数,我们就可以用递归地求得了。这也是我们为什么要把1-21345分为1-1235和1346-21345两段的原因。因为把21345的最高位去掉就得到1345,便于我们采用递归的思路。
分析到这里还有一种特殊情况需要注意:前面我们举例子是最高位是一个比1大的数字,此时最高位1出现的次数10
4
(对五位数而言)。但如果最高位是1呢?比如输入12345,从10000到12345这些数字中,1在万位出现的次数就不是10
4
次,而是2346次了,也就是除去最高位数字之后剩下的数字再加上1。
基于前面的分析,我们可以写出以下的代码。在参考代码中,为了编程方便,我把数字转换成字符串了。
转载请注明原文地址:https://kaotiyun.com/show/4xmZ777K
0
程序员面试
相关试题推荐
WhenIseeclients,thisisthequestionthatI’maskedthemost.Ifyou’reinapublicplace,lookaround.【F1】Nearlyeveryone
C#中,stringstr=null与stringstr=””,请尽量用文字说明区别。(要点:说明详细的内存空间分配)
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。例如:输入两个
设置Internet选项使得在表单上完成输入用户名就会自动完成填写密码。
设置拨号连接属性使得用户在使用拨号连接时需要使用我的Windows登录名和密码。
设置用户在拨号前不需要等待扬声器发出拨号声音。
请恢复金山反垃圾邮件过滤列表。
对于PPoint来说,以下说法正确的是()。A.启动PPoint后直到关闭的过程中,只能建立或编辑一个演示文稿文件B.启动PPoint后直到关闭的过程中,可以建立或编辑多个演示文稿文件C.启动PPoint后,不能编辑多个演示文稿文件D.启动
在Excel97中,要使B5单元格中的数据为A2和A3单元格中数据之和,而且B5单元格中的公式被复制到其他位置时不改变这一结果,可在B5单元格中输入公式()。A.=$A$2+$A$3B.=A2+A3C.=A:2+A:3D.=SUM(A2:A3
一个软件的架构设计是随着技术的不断进步而不断变化的。以编译器为例,其主流架构经历了管道—过滤器到数据共享为中心的转变过程。以下关于编译器架构的叙述中,错误的是______。
随机试题
设函数f(x)具有连续的导数,则()
Thespacecraft______theearththreetimes.
欲研究新法接生是否能减少新生儿窒息的发生率,选择某市级医院为试验组,进行新法接生,选择某县级医院为对照组,用常规方法接生,该方案
(共用备选答案)A.处方调剂B.治疗药物的监测C.参与健康教育D.药物利用研究和评价E.药物不良反应监测和报告确定药物利用的指数
批准的()是项目投资控制总目标。
甲公司和乙运输公司签订运输合同,约定,甲公司按时向乙公司交付所要运输的货物,并支付运费。乙公司准时将货物运输至目的地。其中的法律关系是()。
近期某地发生了3人落水死亡事件,遇难者家属在网上发帖指责海事局不作为,其他网友纷纷转载跟帖。你是海事局宣传部的工作人员,领导让你来处理这件事,你怎么办?
在智利环境恶劣的北部沙漠地区的卡玛罗纳斯谷,人们发现了世界上一些最为古老的小乃伊,即Chinchorro人的木乃伊。木乃伊毛发分析结果显示,砷含量都很高。砷这种金属元素在卡玛罗纳斯谷以及周围火山坡较为常见,砷被季节性融雪水冲入河流,而河流正是牛活在下游的人
简述传播淫秽物品牟利罪的构成要件。
Georgehadstolensomemoney,butthepolicehadcaughthimandhehadbeenputinprison.Nowhistrialwasabouttobegin,and
最新回复
(
0
)