题目1515：打印1到最大的N位数
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：625
解决：323
- 题目描述：
给定一个数字N，打印从1到最大的N位数。
- 输入：
每个输入文件仅包含一组测试样例。
对于每个测试案例，输入一个数字N(1<=N<=5)。
- 输出：
对应每个测试案例，依次打印从1到最大的N位数。
- 样例输入：
1
- 样例输出：
1
2
3
4
5
6
7
8
9
考察的就是大数据输入。
这种求全部组合的题目，一概可以用DFS来做。虽然本题Java中有自带BigInteger类，但还是按照出题人的意思来做吧。
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner; public class S12 { public static void main(String[] args) throws FileNotFoundException {
BufferedInputStream in = new BufferedInputStream(new FileInputStream("in.in"));
System.setIn(in);
Scanner cin = new Scanner(System.in); while (cin.hasNextInt()) {
int n = cin.nextInt();
print1ToMaxOfNDigits(n);
}
} private static void print1ToMaxOfNDigits(int n) {
if(n <= 0){
return;
} char[] number = new char[n];
rec(number, n, 0);
} private static void rec(char[] number, int length, int curDep){
if(curDep == length){
printNumber(number);
return;
} for(int i=0; i<10; i++){
number[curDep] = (char) (i+'0');
rec(number, length, curDep+1);
}
} private static void printNumber(char[] number){
boolean startingZero = true;
for(int i=0; i<number.length; i++){
if(number[i] != '0'){ // 过滤掉前导零
startingZero = false;
}
if(!startingZero){
System.out.print(number[i]);
}
}
if(!startingZero){
System.out.println();
} }
}