0%

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

Posted on In

####题目
输入数字 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

1
func printOneToMaxOfDigits(digitNumber:Int) {
2
    //初始化一个全为0的长度为digitNumber的数组
3
    var array = Array(repeating: 0, count: digitNumber)
4
    //相当于生成一个从digitNumber-1到0的一个序列
5
    let strideTo = stride(from: digitNumber - 1, to: -1, by: -1)
6
7
   //对数组进行加1的函数，若返回false则代表已经超出最大值，可以停止了
8
    func addOne() -> Bool{
9
        for index in strideTo {
10
            if array[index] + 1 > 9 {
11
                array[index] = 0
12
                if index == 0 {
13
                    return false
14
                }
15
            }else {
16
                array[index] = array[index] + 1
17
                break
18
            }
19
        }
20
        return true
21
    }
22
23
    //对数组进行打印
24
    func printArray() {
25
        var result = ""
26
        var isAppend = false
27
        for item in array {
28
            if isAppend || item != 0 {
29
                result += "\(item)"
30
                isAppend = true
31
            }
32
        }
33
        print(result)
34
    }
35
36
37
    //调用加1方法，知道加1方法返回false
38
    while addOne() {
39
        printArray()
40
    }
41
}
42
printOneToMaxOfDigits(digitNumber: 5)