Lintcode371 Print Numbers by Recursion solution 题解
发布在刷题能手——Lintcode 题解2018年3月9日view:287
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Print numbers from 1 to the largest number with N digits by recursion.

Notice

It’s pretty easy to do recursion like:

recursion(i) {

if i > largest number:

return

results.add(i)

recursion(i + 1)

}

however this cost a lot of recursion memory as the recursion depth maybe very large. Can you do it in another way to recursive with at most N depth?

用递归的方法找到从1到最大的N位整数。

【注】用下面这种方式去递归其实很容易:

recursion(i) {

if i > largest number:

return

results.add(i)

recursion(i + 1)

}

但是这种方式会耗费很多的递归空间,导致堆栈溢出。你能够用其他的方式来递归使得递归的深度最多只有 N 层么?

【题目链接】

www.lintcode.com/en/problem/print-numbers-by-recursion/

【题目解析】

从小至大打印 N 位的数列,正如题目中所提供的recursion(i), 解法简单粗暴,但问题在于 N 稍微大一点时栈就溢出了,因为递归深度太深了。能联想到的方法大概有两种,一种是用排列组合的思想去解释,把0~9当成十个不同的数(字符串表示),塞到 N 个坑位中,这个用DFS来解应该是可行的;另一个则是使用数学方法,依次递归递推,比如 N=2 可由 N=1递归而来,具体方法则是乘10进位加法。题中明确要求递归深度最大不超过 N, 故DFS方法比较危险。

【参考答案】

www.jiuzhang.com/solutions/print-numbers-by-recursion/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏