关于java:17-打印从1到最大的n位数全排列

29次阅读

共计 998 个字符,预计需要花费 3 分钟才能阅读完成。

17. 打印从 1 到最大的 n 位数


留神!需思考大数

思路:

  • n 位数须要输入 1~10^n-1
  • 当须要思考大数时,用 int 类型不能蕴含所有状况,因而须要用 字符数组的全排列 来失去。
  • 两位数须要两层 for 循环来失去十位和个位的排列组合,n 层 for 循环用 递归 代替
  • 字符数组 转换为 int 类型:

    字符数组 -- 字符串(String)--int
      ----s = String.valueOf(num)----Integer.parseInt(s)
  • 用递归示意多层 for:具体

    void def(int n){if(){
         ...
         return;
      }
      for(xxx){def(); 在 for 循环中调用本人
      }
    }
  • 去零。全排列的后果无奈防止地会呈现 [001,002,003…] 而不是题目所须要的[1,2,3,…,999]

    • 后果中的某一个数的位数和 9 的个数和 n 的关系有:
    输出 n 此时的数 此时该数的位数 subString(start)中的 start 9 的个数 nine
    2 09 1 1 1
    3 009 1 2 1
    3 099 2 1 2

    失去论断:

      n  = start + nine

    ,因而在满足以上条件时,须要扩充子字符串的范畴,即start–

    • 计算 nine。是在 for 里计算的,同时 计算了 09,变 20 时跳出个位的循环,须要nine-1,不能影响前面 20 的时候,nine 应该是 0,而不是 1。

操作:

public class Solution {char[] arr = {'0','1','2','3','4','5','6','7','8','9'};
    int n;
    int[] res;
    char[] num;
    int nine,start, k =0;
    public int[] printNumbers(int n){
        this.n = n;
        res = new int[(int) Math.pow(10,n)-1];
        num = new char[n];
        start = n-1;
        def(0);
        return res;
    }
    public void def(int x){if (x == n){String s = String.valueOf(num).substring(start);
            if(s.equals("0")) return;
            res[k] = Integer.parseInt(s);
            k++;
            if (n-start == nine) start--;
            return;
        }
        for (char a :
                arr) {if (a=='9') nine++;
            num[x] = a;
            def(x+1);
        }
        nine--;
    }
}

d25

正文完
 0