剑指Offer算法题-打印从1到最大的n位数

题目

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

方案

看到题目，首先想到先求出最大的n位数(maxN),然后从1开始遍历到maxN.但是这里有个陷进，就是maxN有可能超出Int或者long long表示的最大数的范围，这个时候回发生溢出错误。

所以这个时候要选择合适的类型来表示maxN，我这里选择的是用Array来表示maxN，最高位放到数组的最前面。以四位数举例，585可以表示为[0,5,8,5]，

用数组表示maxN之后，面临着三个问题：

1. 输出打印
   这个时候只需要遍历数组，把前面的0去掉即可

2. 加1
   对数组进行倒序遍历，对后位进行+1，若结果大于9，则把该位置0，继续对前面的数进行+1，若结果不大于9，则把结果赋值给当前位并停止遍历

3. 何时停止
   若数组的首位进行进位时，则表示已经遍历了最大值，需要停止循环

代码Swift

func printOneToMaxOfDigits(digitNumber:Int) {
    //初始化一个全为0的长度为digitNumber的数组
    var array = Array(repeating: 0, count: digitNumber)
    //相当于生成一个从digitNumber-1到0的一个序列
    let strideTo = stride(from: digitNumber - 1, to: -1, by: -1)
    
   //对数组进行加1的函数，若返回false则代表已经超出最大值，可以停止了
    func addOne() -> Bool{
        for index in strideTo {
            if array[index] + 1 > 9 {
                array[index] = 0
                if index == 0 {
                    return false
                }
            }else {
                array[index] = array[index] + 1
                break
            }
        }
        return true
    }

    //对数组进行打印
    func printArray() {
        var result = ""
        var isAppend = false
        for item in array {
            if isAppend || item != 0 {
                result += "\(item)"
                isAppend = true
            }
        }
        print(result)
    }


    //调用加1方法，知道加1方法返回false
    while addOne() {
        printArray()
    }
}
printOneToMaxOfDigits(digitNumber: 5)