面试题17：打印从1到最大的n位数

题目描述

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

注意：本题实际考察大数问题，直接循环打印整形会溢出，采用字符串模拟加法

public static void printToMax(int n) {
        if(n <= 0) return;
        char [] nums = new char[n+1];
        Arrays.fill(nums, '0');
        while(increase(nums)) {
            printNum(nums);
        }
    }
    public static boolean increase(char[] nums) {
        int len = nums.length;
        if(nums[len-1] == '1') return false;
        int takeOver = 1;
        for(int i = 0; i < len; i++) {
            if(takeOver != 0) {
                int sum = nums[i] + 1;
                if((char)sum > '9') {
                    takeOver = 1;
                    nums[i] = '0';
                }else {
                    takeOver = 0;
                    nums[i] = (char)sum;
                }
            }
        }
        return true;
    }
    public static void printNum(char [] nums) {
        String str = "";
        int i = nums.length-2;  //从倒数第二位开始
        boolean flag = false;
        while(i >= 0) { //倒序打印
            if(nums[i] != '0') flag = true;
            if(flag) {
                str += nums[i];
            }
            i--;
        }
        if(str == "") return;
        else System.out.println(str);
    }

回溯全排列

思路

打印从1到最大的n位数其实就是n个0-9的数字的全排列，因而可用回溯法求解

    // 回溯全排列
    public static void strDFS(String str, int n, int index) {
        if(n <= 0) return;  // 处理n小于等于0的情况
        if(index == n) {    // 去除字符串前面多余的0
            int isNot = 0;  // 第一个不为0的下标
            for(int i = 0; i < str.length(); i++) {
                if(str.charAt(i) != '0') {
                    isNot = i;
                    break;
                }
                isNot = n;
            }
            if(isNot == n) return;
            else System.out.println(str.substring(isNot, str.length()));
            return;
        }
        for(int i = 0; i <= 9; i++) {
            str += (char)(i+48);
            strDFS(str, n, index+1);
            str = str.substring(0, str.length()-1);
        }
    }