剑指offer-77、打印从1到最⼤的n位数
<h2 id="题描述">题⽬描述</h2><p>输⼊数字 n ，按顺序打印出从 1 到最⼤的 n 位⼗进制数。⽐如输⼊ 3 ，则打印出 1 、2 、3⼀直到最⼤的 3 位数 999 。</p>
<ol>
<li>⽤返回⼀个整数列表来代替打印</li>
<li>n 为正整数</li>
</ol>
<p>示例1<br>
输⼊：1<br>
返回值：</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="直接计算">直接计算</h3>
<p>不太清楚这道题是要考察什么（苦笑），⼏乎都是⼀个循环能解决的事情，仔细想了⼀下，也并没有想到其他⽐较令⼈⽿⽬⼀新的做法，⽤Math.pow(10, n) - 1 取出最⼤的边界条件</p>
<pre><code class="language-java">public class Solution {
public int[] printNumbers(int n) {
double len = Math.pow(10, n) - 1;
int[] result = new int[(int) len];
for (int i = 0; i < len; i++) {
result = i + 1;
}
return result;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(10ⁿ)，需要生成10ⁿ-1个数字</li>
<li><strong>空间复杂度</strong>：O(10ⁿ)，需要存储所有数字</li>
</ul>
<p>当n≥10时，10ⁿ-1会超过int范围，导致溢出</p>
<h3 id="字符串模拟">字符串模拟</h3>
<p>针对大数问题，使用字符串来模拟数字的生成。</p>
<pre><code class="language-java">import java.util.ArrayList;
import java.util.List;
public class Solution {
public int[] printNumbers(int n) {
if (n <= 0) return new int;
// 使用List存储结果，再转为数组
List<Integer> list = new ArrayList<>();
char[] number = new char;// 存储当前数字的字符表示
// 递归生成所有n位数
generateNumbers(number, 0, list);
// 转换为数组（去掉前导0）
int[] result = new int;
for (int i = 0; i < list.size(); i++) {
result = list.get(i);
}
return result;
}
private void generateNumbers(char[] number, int index, List<Integer> list) {
if (index == number.length) {
// 将字符数组转换为整数
int num = convertToInt(number);
if (num != 0) {// 跳过0
list.add(num);
}
return;
}
// 当前位置可以填0-9
for (char c = '0'; c <= '9'; c++) {
number = c;
generateNumbers(number, index + 1, list);
}
}
private int convertToInt(char[] number) {
int result = 0;
boolean leadingZero = true;
for (char c : number) {
if (c != '0' || !leadingZero) {
if (leadingZero) leadingZero = false;
result = result * 10 + (c - '0');
}
}
return result;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n×10ⁿ)</li>
<li>空间复杂度：O(n×10ⁿ)</li>
</ul>
<p>优化版本：</p>
<pre><code class="language-java">public class Solution {
public int[] printNumbers(int n) {
if (n <= 0) return new int;
int max = (int) Math.pow(10, n) - 1;
int[] result = new int;
// 直接计算并填充，避免字符串转换开销
for (int i = 0; i < max; i++) {
result = i + 1;
}
return result;
}
// 处理大数的版本（返回字符串列表）
public String[] printNumbersBig(int n) {
if (n <= 0) return new String;
int max = (int) Math.pow(10, n) - 1;
String[] result = new String;
for (int i = 0; i < max; i++) {
result = String.valueOf(i + 1);
}
return result;
}
}
</code></pre>
<h3 id="递归回溯">递归回溯</h3>
<p>利用递归生成所有可能的数字组合。</p>
<pre><code class="language-java">import java.util.ArrayList;
import java.util.List;
public class Solution {
private List<Integer> result;
private char[] number;
public int[] printNumbers(int n) {
if (n <= 0) return new int;
result = new ArrayList<>();
number = new char;
// 从第0位开始递归生成
dfs(0);
// 转换为数组
int[] arr = new int;
for (int i = 0; i < result.size(); i++) {
arr = result.get(i);
}
return arr;
}
private void dfs(int index) {
if (index == number.length) {
// 将字符数组转换为整数
int num = 0;
boolean isZero = true;
for (int i = 0; i < number.length; i++) {
if (number != '0' || !isZero) {
if (isZero) isZero = false;
num = num * 10 + (number - '0');
}
}
// 跳过0
if (num > 0) {
result.add(num);
}
return;
}
// 当前位置可以填0-9
for (char c = '0'; c <= '9'; c++) {
number = c;
dfs(index + 1);
}
}
}
</code></pre>
<ul>
<li>时间复杂度：O(10ⁿ)</li>
<li>空间复杂度：O(n) - 递归栈深度</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19631381
頁:
[1]