【問題描述】[中等]

輸入數字 n，按順序打印出從 1 到最大的 n 位十進制數。比如輸入 3，則打印出 1、2、3 一直到最大的 3 位數 999。示例 1:輸入: n = 1 輸出: [1,2,3,4,5,6,7,8,9]說明：用返回一個整數列表來代替打印 n 為正整數

【解答思路】

1. 直接打印

時間復雜度：O(10^N) 空間復雜度：O(1)

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

2. 大數打印

時間復雜度：O(N) 空間復雜度：O(1)

class Solution {int[] res;int nine = 0, count = 0, start, n;char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};public int[] printNumbers(int n) {this.n = n;res = new int[(int)Math.pow(10, n) - 1];num = new char[n];start = n - 1;dfs(0);return res;}void dfs(int x) {if(x == n) {String s = String.valueOf(num).substring(start);// 解決是0的串 0 00 000 0000 if(!s.equals("0")) res[count++] = Integer.parseInt(s);if(n - start == nine) start--;return;}for(char i : loop) {if(i == '9') nine++;num[x] = i;dfs(x + 1);}nine--;} }

【總結】

1.大數全排列模板

class Solution {StringBuilder res;int count = 0, n;char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};public String printNumbers(int n) {this.n = n;res = new StringBuilder(); // 數字字符串集num = new char[n]; // 定義長度為 n 的字符列表dfs(0); // 開啟全排列遞歸res.deleteCharAt(res.length() - 1); // 刪除最后多余的逗號return res.toString(); // 轉化為字符串并返回}void dfs(int x) {if(x == n) { // 終止條件：已固定完所有位res.append(String.valueOf(num) + ","); // 拼接 num 并添加至 res 尾部，使用逗號隔開return;}for(char i : loop) { // 遍歷 ‘0‘ - ’9‘num[x] = i; // 固定第 x 位為 idfs(x + 1); // 開啟固定第 x + 1 位}} }

2.全排序一般使用遞歸處理/回溯法

3.注意回溯時條件要還原

轉載鏈接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题第[17]题[打印从1到最大的n位整数][大整数][递归回溯]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。