剑指offer-问题12

怼烎@ 2022-05-10 14:46 173阅读 0赞

package offer;
    
    /**
     * offer interview 12
     */
    public class Test12 {
    
        //method 01
        public static void printOneToNthDigits(int n){
            if (n < 1 ){
                throw new RuntimeException("the input num must larger than 0");
            }
    
            int[] arr = new int[n];
            printOneToNthDigits(0,arr);
    
        }
    
        public static void printOneToNthDigits(int n,int[] arr){
    
            if (n >= arr.length){
                printArray(arr);
            }else{
                for (int i = 0 ; i <= 9 ; i++){
                    arr[n] = i;
                    printOneToNthDigits(n + 1,arr);
                }
            }
    
        }
    
        public static void printArray(int[] arr){
            int index = 0;
            while (index < arr.length && arr[index] == 0){
                index++;
            }
    
            for (int i = index ; i < arr.length;i++ ){
                System.out.print(arr[i]);
            }
    
            if (index < arr.length){
                System.out.println();
            }
        }
    
        // method 02
        public static void printOneToNthDigits2(int n){
            if (n < 1){
                throw new RuntimeException("the input number must be larger than 0");
            }
    
            int[] arr = new int[n];
            for (int i = 0 ; i < arr.length ; i++ ){
                arr[i] = 0;
            }
    
            while (addOne(arr) == 0){
                printArray(arr);
            }
        }
    
        public static int addOne(int[] arr){
            //保存进位值，因为每次最低位加1
            int carry = 1;
            //最低位的位置的后一位
            int index = arr.length;
    
            do {
                // 指向上一个处理位置
                index--;
                // 处理位置的值加上进位的值
                arr[index] = arr[index] + carry;
                // 求处理位置的进位
                carry = arr[index] / 10;
                // 求处理位置的值
                arr[index] = arr[index] % 10;
    
            }while (carry != 0 && index > 0);
            // 如果index=0说明已经处理了最高位，carry>0说明最高位有进位，返回1
            if (carry > 0 && index == 0){
                return 1;
            }
            // 无进位返回0
            return 0;
        }
    
    
        //test
        public static void main(String[] args){
            printOneToNthDigits(2);
            System.out.println();
            printOneToNthDigits2(2);
        }
    }