今天是小浩算法 “365刷题计划” 第85天。穿插着为大家分享一道经典面试题目。额外说明的一点是,这道题本身很简单,但是却可以作为很多 中等/困难 题目的基础,
比如 超级次方,实现pow(x,n) 等等,在面试时需要额外小心。建议大家掌握!话不多说,直接看题。
本题原始版本出自《剑指offer》,leetcode或许是因为自身原因,并没有很好的进行移植。当然,这道题本身也确实不太好移植,尤其是测试样例的构建,很容易把系统搞崩掉,所以一些测试样例处理成内存溢出,也是情有可原。
题目:输入数字 n
,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。
如果是第一次看到本题,应该是会想到????????????的解法。
直接通过 Math.pow 函数,计算出最大的 n 位十进制数,通过遍历求解。因为过于简单,所以直接上代码:
这种题解,应该不存在说有看不懂的。。。吧?(有的话,面壁思过!)
郑重申明(读我的文章必看):
“不允许使用math.pow,请手动实现一下”,“恶毒”的面试官发问了。
不让使用 math.pow , 那我们就不使用呗。根据上面的题解,我们已经把握到了关键,只要能找到 最大的 n 位十进制数,就可以解决问题。那我们就手动算一下:
(看起来还不错~但我肯定不会告诉你这是因为go语言提交少的缘故!)
“这道题目的名字叫做大数打印,如果阈值超出long类型,该怎么办呢?请手动实现一下!” 面试官总是可以想方设法为难咱们。(玩笑归玩笑,其实这个才是本题的核心)
到现在为止,本题才进入到关键环节。因为如果一个数很大,肯定没办法用单个变量类型进行表达。问题也发生了转化:如何使用其他的数据类型来模拟大数的表达?
这里先复习一下大数加法:在加法运算的时候假如有两个10000位数的两个数进行相加,那么用int、long、double型都装不下这么多位数,一般采用char数组来实现加法运算,解决精度的问题。说白了是啥意思,我们用 1234567 和 1234 来模拟一下:
-
取两个数位数大的一个作为数组长度
-
对两个数建立char数组,保存每一位上的值
-
对于位数小的数,高位补0。
-
同时创建sumArr,用来保存两数之和
当然,一般我们还使用一些比如 翻转存储计算 之类的技巧,这里就不说了,回头我会出一个单独的大数计算系列篇单独讲解。回到今天的题目。
对于本题,我们该如何模拟一个 “最大的n位十进制数” 呢?其实也是一样的,我们采用 char 数组进行存储。而我们每次递增1,相当于进行一次字符串相加的运算。但是这里额外要说明的一点是,我把题解恢复成了原题的要求:使用打印输出,而不是通过数组返回的形式。毕竟返回数组的形式只是
leetcode 为了兼容平台测试而改编的。这里我就直接给出从剑指offer改编的题解了(JAVA):
3 //声明字符数组,用来存放一个大数 12 //循环体退出标识 28 //进位之后减10,并把进位标识设置为1 48 // 到这里并没有继续往下实现一个存储数组的版本,是因为原题其实就是要求打印数值。 49 // 这道题目在leetcode上被改动成返回int数组的形式,也只是为了测试方便, 50 // 本身leetcode并没有提供对应的大数测试样例,也是担心其内存溢出。 51
// 总之大家知道本题的考察点所在就可以了。
同样,我也实验了一下,如果我硬性的把代码改成数组的形式,然后在leetcode测试用例中构造 n = 10,就会出现这个:
(所以建议大家是在IDE里练习)
今天的题目到这里就结束了,如果想看其他面试题相关内容的,可以看:
如果你问我对学习算法有什么建议,这篇文章是必看的:
小浩算法,每日一题
关注领取《图解算法》高清版
进群的小伙伴请加右侧私人微信(备注:进群)