剑指offer——打印从1到最大的n位数

题目:
输入数字n,按顺序打印出从1最大的n位十进制数。
比如输入3,则打印出1、2、3、4、5、6…… 一直到最大的3位数即999。
/*
* 【注意】
* 大数问题:–>用数组
* 法1:
* 模拟大数相加,从0开始,每次加1,
* 直到arr的最高位(倒数第n+1位)有进位时,即最大的n位数已经打印完毕。
*
* 法2:
* 递归
* 打印1 ~ n位的所有十进制数,其实就是从第1位开始设置0~9的全排列,直到递归将最后一个位置设置完毕,开始打印。
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
public class 打印从1到最大的n位数 {
    public static void print1n1(int n) {
        //n<0,抛出异常
        if(n < 0 ) {
            throw new IllegalArgumentException("n>0");
        }
        //定义一个n+1长度的数组来存储,并将所有位置初始化为0;
        int[] arr = new int[n+1];
        for(int i = 0;i< arr.length;i++) {
            arr[i] = 0;
        }
        /* 模拟加法,并打印
         * while语句的条件语句执行后,arr数组发生变化,如果满足的执行打印,
         * 因为返回的是true,继续执行addone(arr)语句,进行返回值判断,同时更改arr数组。
         */

       
        while(addone(arr)) {
            System.out.println(Arrays.toString(arr));
            //System.out.println("-----------");
            printnum(arr);
        }
    }
    //打印算法,从头开始遍历,遇到第一个非0元素表示可以开始打印,设定标签isBeginning0来判定是不是开始的0
    private static void printnum(int[] arr) {
        boolean isBeginning0 = true;
        for (int i = 0; i < arr.length; i++) {
            if (isBeginning0 && arr[i]!=0){
                isBeginning0 = false;
            }
            if (!isBeginning0){
                System.out.print(arr[i]);
            }
        }
        System.out.println();      
    }
    /*
     * 模拟加法
     * 对arr的最低位加1,return true;
     * 直到 加到最高位(index==0时),如果还有进位,则return false;
     * 一般执行完之后 carry==0&&index==0,返回false;如果最高位有进值,
     * 例如 2位数99+1=100,carry>0&&index==0,触发false
     * 所以carry>0&&index==0改为carry==1&&index==0也可以完成判断
     */

    private static boolean addone(int[] arr) {
        int carry = 1; //进位值
        int index = arr.length - 1; //最低位
       
        // 如果index=0说明已经处理了最高位,carry>0说明最高位有进位,返回false
        while(carry != 0 && index > 0) {
            arr[index] += carry;  //处理位的值+进位值
            carry = arr[index]/10; // 求处理位置的进位
            arr[index] %= 10; // 求处理位置的值
            index --;
        }
        if(carry==1 && index == 0) { //看最高位是否进位
            return false;
        }
        return true;
    }
    public static void print1n2(int n) {
        //n<0,抛出异常
        if(n < 0 ) {
            throw new IllegalArgumentException("n>0");
        }
        //定义一个n长度的数组来存储,并将所有位置初始化为0;
        int[] arr = new int[n];
        for(int i = 0;i< arr.length;i++) {
            arr[i] = 0;
        }
        //模拟加法,并打印
        print1n2dg(0,arr);
    }
    //递归类似于n位元素的1-9的全排列
    private static void print1n2dg(int i, int[] arr) {
        if (i == arr.length){
            printnum(arr);
            return;
        }
        for (int j = 0; j <= 9; j++) {
            arr[i] = j;
            print1n2dg(i+1, arr);
        }      
    }
    public static void main(String[] args) {
        System.out.println(Integer.MAX_VALUE);
        System.out.println(Integer.MIN_VALUE);
        print1n2(2);
    }                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              

}
0 条评论
发表一条评论