剑指 Offer 17. 打印从1到最大的n位数 发表于 2022-05-15 Simulation123456789class Solution { public int[] printNumbers(int n) { int[] res = new int[(int) Math.pow(10, n) - 1]; for (int i = 0; i < res.length; i++) { res[i] = i + 1; } return res; }} DFS1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950class Solution { private static final char[] NUMS = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}; private static class State { private int startIndex; private int countOfNine; private int resIndex; private final int n; public State(int n) { this.n = n; this.startIndex = n - 1; // 不要忘记初始化 startIndex, 且为最右侧元素索引,注意不是 0 } } public int[] printNumbers(int n) { int[] res = new int[(int) Math.pow(10, n) - 1]; char[] numArray = new char[n]; State state = new State(n); StringBuilder sb = new StringBuilder(); dfs(res, numArray, 0, state); return res; } private void dfs(int[] res, char[] numArray, int level, State state) { if (level == state.n) { int value = Integer.parseInt(new String(numArray).substring(state.startIndex)); if (value != 0) { res[state.resIndex++] = value; } if (state.countOfNine + state.startIndex == state.n) { state.startIndex--; } return; // 此处不要忘记 return } for (char num : NUMS) { if (num == '9') { state.countOfNine++; } numArray[level] = num; dfs(res, numArray, level + 1, state); } state.countOfNine--; }} Reference剑指 Offer 17. 打印从1到最大的n位数