剑指Offer：打印从1到最大的n位数（Python语言实现）

输入数字n，按顺序打印出从1到最大的n位十进制数。

class Solution:
    def print_one_to_max_of_digits(self, n):
        if n <= 0:
            return False
        number = ['0'] * n
        while not self.increment(number):
            self.print_number(number)

    def increment(self, number):
        overflow_flag, carry = False, 0
        n = len(number)
        for ni in range(n-1, -1, -1):
            n_value = ord(number[ni]) - ord('0') + carry
            if ni == n-1:
                n_value += 1

            if n_value >= 10:
                if ni == 0:
                    overflow_flag = True
                else:
                    n_value -= 10
                    carry = 1
                    number[ni] = chr(ord('0') + n_value)
            else:
                number[ni] = chr(ord('0') + n_value)
                break
        return overflow_flag

    def print_number(self, number):
        ni = 0
        for ni, nu in enumerate(number):
            if nu != '0':
                break

        print(''.join(number[ni:]))


st = Solution()
n = 4
print(st.print_one_to_max_of_digits(n))

把问题转换成数字排列的解法，递归让代码更简洁。

class Solution:
    def print_one_to_max_of_digits(self, n):
        if n <= 0:
            return False
        number = ['0'] * n
        for digit in range(10):
            number[0] = chr(digit+ord('0'));
            self.change_carry_digit_recursively(number, n, 0)

    def change_carry_digit_recursively(self, number, length, index):
        if index == length-1:
            self.print_number(number)
            return
        for digit in range(10):
            number[index+1] = chr(digit + ord('0'))
            self.change_carry_digit_recursively(number, length, index+1)

    def print_number(self, number):
        ni = 0
        for ni, nu in enumerate(number):
            if nu != '0':
                break

        print(''.join(number[ni:]))


st = Solution()
n = 4
print(st.print_one_to_max_of_digits(n))

如果面试题是关于n位的整数并且没有限定n的取值范围，或者输入任意大小的整数，那么这道题目很有可能是需要考虑大数问题的。字符串是一种简单、有效地表示大数的方法。

（最近更新：2019年07月16日）