leetcode-打印从1到最大的n位十进制数

刷leetcode《剑指offer》第十六题"打印从1到最大的n位十进制数"，有感

题目

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

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

解析

1. 因为题目要求返回值为整型数组，那就默认不会有大数溢出情况，那就直接循环。
2. 但是这道题，一般会考虑整数溢出的问题。所以使用字符来代替整形。

注意

1. 在考虑大数溢出的情况下，要考虑每个数字左边的零个数，要去掉
2. 使用分治法以及全排列。

具体代码实现

第一种方法

class Solution {
    public int[] printNumbers(int n) {
        int m = (int) Math.pow(10,n);
        int[] arr = new int[m-1];
        for (int i = 0; i < m-1; i++) {
            arr[i] = i+1;
        }
        return arr;
    }
}

第二种方法

// 考虑大数
public void printNumbers1(int n) {
    StringBuilder str = new StringBuilder();
    // 将str初始化为n个0的字符串
    for (int i = 0; i < n; i++) {
        str.append('0');
    }
    // 判断去掉左侧的0
    while (!increment(str)) {
        // 去掉左侧的0
        int index = 0;
        while (index < str.length() && str.charAt(index) == '0') {
            index++;
        }
        System.out.println(str.toString().substring(index));
    }
}

/**
     * 判断是否溢出
     *
     * @param str 字符串
     * @return 返回判断值
     */
private boolean increment(StringBuilder str) {
    boolean isOverflow = false;
    for (int i = str.length() - 1; i >= 0; i--) {
        char s = (char) (str.charAt(i) + 1);
        // 如果s> '9'则发生进位
        if (s > '9') {
            // 将'9'变为'0'
            str.replace(i, i + 1, "0");
            if (i == 0) {
                isOverflow = true;
            }
        } else {
            // 没有发生进位
            str.replace(i, i + 1, String.valueOf(s));
            break;
        }
    }
    return isOverflow;
}