文章目录
打印从1到最大的n位数问题描述问题分析算法思路一：字符数组模拟算法思路二（全排列）总结
打印从1到最大的n位数
问题描述
问题分析
首先这道题肯定是不会让你用最简单的循环去做的，但是为什么不能用循环呢？因为这道题并没有说不考虑大数的限制，也就是说使用int或者long可能会导致溢出所以对于大数的情况，我们一般都是用字符数组去模拟数字的加法，这就是算法思路一其次就是可以把问题转化为数字的全排列问题，无非就是对定长的字符数组，每一位都可能取0-9，进行全排列，这样的思路是最优的，但是我没怎么看懂代码实现！
算法思路一：字符数组模拟
输入n，使用n+1位的字符数组模拟存储，并且同时进行加1的实现
有几个问题是需要注意的：
字符数组必须初始化为‘0’，默认初始化的值看起来为0，实际上在计算的时候会不一样字符与数字做运算转化的时候必须要 加上或者减 ‘0’ （因为ascll的原因）每次输出的时候要注意要去掉前面的0如何判断结束？只需要判断字符数组的第一位是否为1即可，因为我们多用了一位进行存储
public static void printMaxNum1(int n
){
char[] nums
= new char[n
+1];
for(int i
= 0; i
< n
+1; i
++) nums
[i
] = '0';
while (nums
[0] != '1'){
for(int i
= n
; i
>= 0; i
--){
int result
= nums
[i
] - '0' + 1;
if(result
> 9){
nums
[i
] = '0';
}else {
nums
[i
] = (char) (result
+ '0');
break;
}
}
int index
= 0;
for( ; index
< n
+ 1; index
++){
if(nums
[index
] != '0') break;
}
if(nums
[0] != '1'){
String str
= new String(nums
);
System
.out
.println(str
.substring(index
,n
+1));
}
}
}
算法思路二（全排列）
实际上这个全排列的思想我是清楚地，但是代码实现我是看了挺久都没看懂，这里使用了递归的写法，我就把别人的代码放过来了
public static void printToMaxOfDigits(int n
){
if(n
<= 0){
System
.out
.println("输入的n没有意义");
return;
}
char number
[] = new char[n
];
for (int i
= 0; i
< number
.length
; i
++) {
number
[i
] = '0';
}
for (int i
= 0; i
< 10; ++i
) {
number
[0] = (char) (i
+ '0');
printToMaxOfNDigitsRecursively(number
, n
, 0);
}
}
public static void printToMaxOfNDigitsRecursively(char[] number
, int n
, int index
) {
if(index
== n
- 1){
printNumber(number
);
return;
}
for (int i
= 0; i
< 10; ++i
) {
number
[index
+ 1] = (char) (i
+ '0');
printToMaxOfNDigitsRecursively(number
, n
, index
+ 1);
}
}
private static void printNumber(char[] number
) {
boolean isBeginning0
= true;
int nLength
= number
.length
;
for (int i
= 0; i
< nLength
; ++i
) {
if(isBeginning0
&& number
[i
]!='0'){
isBeginning0
= false;
}
if(!isBeginning0
){
System
.out
.print(number
[i
]);
}
}
System
.out
.println();
}
总结
写第一种算法的时候遇见了之前没有遇见过的问题，对于不初始化的字符数组，debug的时候发现默认存储的的确是‘0’，但是实际使用 （- ‘0’ + 1 ）方式进行计算的时候会是不一样的结果，我也不知道原因。所以最后还是初始化了字符与数字进行计算的时候，要减去‘0’ ，这个好久没写了，有点忘记了
