剑指Offer17-打印从1到最大的n位数

兴趣爱好交流 每日一题
1

剑指Offer17-打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:


输入: n = 1

输出: [1,2,3,4,5,6,7,8,9]

说明：

  • 用返回一个整数列表来代替打印

  • n 为正整数

来源：力扣（LeetCode）

链接：力扣

一解


class Solution:

    def printNumbers(self, n: int) -> List[int]:

        return [i for i in range(1, 10**n)]

使用一行搞定，但存在重大问题，如果数字 n 无限大，一解在其它语言会越界（比如 Java），可以使用字符串替代数字。

二解

  • digit表示要生成的数字的位数，从1开始到n位

  • 数字开头不能是0，要单独处理首位first，其范围是1~9

  • 使用递归生成除首位，剩下的位数digit-1

  • 递归中止条件是已生成的位数==目标位数，即index == digit


class Solution:

    def printNumbers(self, n: int) -> List[int]:

        def dfs(index, num, digit):

            # 已生成位数 == 目标位数

            if index == digit:

                res.append(int(''.join(num)))

                return

            # 生成除首位的其它位

            for i in range(10):

                # 递归追加一个数字到 res

                num.append(str(i))

                dfs(index + 1, num, digit)

                # 将已追加的数字弹出，继续追加其它数字

                num.pop()

        res = []

        for digit in range(1, n + 1):

            # 首位数字单独处理

            for first in range(1, 10):

                num = [str(first)]

                dfs(1, num, digit)

        

        return res
2 
def print_numbers(n: int) -> List[int]:
    def iter_():
        def dfs(index, num, digit):
            if index == digit:
                yield "".join(num)
            else:
                for i in range(10):
                    num.append(str(i))
                    yield from dfs(index + 1, num, digit)
                    num.pop()

        for digit in range(1, n + 1):
            for first in range(1, 10):
                num = [str(first)]
                yield from dfs(1, num, digit)

    return list(iter_())

跟着老师做了几天题，感觉对递归渐渐有了一些理解:+1::+1::+1:

3

python中不需要考虑越界的问题吧

def printnumber(n):
    return [i for i in range(10**n)]

print(printnumber(5))
4 
class Solution:

    def printNumbers(self, n) :

        x=1
        list1=[]
        while len(str(x)) <= n:
            list1.append(x)
            x +=1
        return list1
5

需要考虑，python 数字是根据内存定的，如果面试这么写，会被挂

6 
class Solution:
    @staticmethod
    def printNumbers(n: int) -> List[int]:
        return [i for i in range(10 ** n)]


print(Solution.printNumbers(2))
7

不建议这种解法，详见我上面的解释

8 
def dfs(n):
    res = []
    def signal(nums,index):
            for i in range(0, 10):
                if index == 1:
                    nums.append(str(i))
                    res.append(''.join(nums))
                    nums.pop()
                else:
                    nums.append(str(i))
                    signal(nums, index-1)
                    nums.pop()
   #  共 1 - n 位
    for i in range(1,n+1):
        #处理首位数字 1- 9
        for first in range(1,10):
            # 如果仅一位，添加到结果集
            if i == 1 :
                res.append(first)
            # 否者的话，将第一位加进nums列表
            else:
                nums = [str(first)]
                signal(nums,i-1)

    for i in res:
        print(str(i))

if __name__=="__main__":
    dfs(3)