打印从1到最大的n位数
【打印从1到最大的n位数】《剑指offer》面试题17:打印从1到最大的n位数
题目:输入数字n,按顺序打印出从1到最大的n位十进制数。比如输入3,则打印出1、2、3一直到最大的3位数999。
思路:当输入n很大时,使用int或long都会溢出。需要考虑大数问题。
可以借用字符串或数组表示大数。首先把字符串中的每一个数字初始化为'0',然后每一次为字符串表示的数加1,再打印出来。因此,我们只需要做两件事:一是在字符串表示的数字上模拟加法;二是把字符串表示的数字打印出来。
在模拟加法的过程中需要判断是否已经到了最大的n位数,如果使用库函数则时间复杂度为O(n)。在加法的过程中如果字符串的第一个字符产生了进位,则已经到达了最大的n位数。可以实现O(1)时间判断是否已经达到了最大的n位数。
打印字符串表示的数字时,字符串开始的0不必打印。例如'068'打印68
代码如下:
public static void print1ToMaxOfNDigits(int n) {
if (n < 0) {
return;
}
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0;
i < n;
i++) {
stringBuffer.append('0');
}
// 如果未达到最大的n位数则打印
while (!increment(stringBuffer)) {
printNumber(stringBuffer);
}
}/**
* 判断是否到达最大的n位数
* 时间复杂度:O(1)
* @param number
* @return
*/
private static boolean increment(StringBuffer number) {
boolean isOverFlow = false;
int nTakeOver = 0;
int nLength = number.length();
for (int i = nLength - 1;
i >= 0;
i--) {
int nSum = number.charAt(i) - '0' + nTakeOver;
if (i == nLength - 1) {
nSum++;
}
if (nSum >= 10) {
if (i == 0) {
isOverFlow = true;
} else {
nSum -= 10;
nTakeOver = 1;
number.setCharAt(i,(char)('0' + nSum));
}
} else {
number.setCharAt(i,(char)('0' + nSum));
break;
}
}
return isOverFlow;
}private static void printNumber(StringBuffer number) {
boolean isBegining0 = true;
for (int i = 0;
i < number.length();
i++) {
if (isBegining0 && number.charAt[i] != '0') {
isBegining0 = false;
}
if (!isBegining0) {
System.out.print(number.charAt[i]);
}
}
System.out.println();
}
如果在数字前面补0,则n位所有十进制数其实就是n个从0到9的全排列,把数字的每一位从0到9排列一遍,就得到了全部的十进制数。打印时排在前面的0不打印出来。使用递归实现全排列。
代码如下:
public static void print1ToMaxOfNDigits2(int n) {
if (n < 0) {
return;
}
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0;
i < n;
i++) {
stringBuffer.append('0');
}
for (int i = 0;
i < 10;
i++) {
stringBuffer.setCharAt(0,(char)(i + '0'));
print1ToMaxOfNDigits2Core(stringBuffer,n,0);
}
}private static void print1ToMaxOfNDigits2Core(StringBuffer number,int n,int index) {
if (index == n - 1) {
printNumber(number);
return;
}
for (int i = 0;
i < 10;
i++) {
number.setCharAt(index + 1,(char)(i + '0'));
print1ToMaxOfNDigitsCore(number,n,index + 1);
}
}
推荐阅读
- 2018-02-06第三天|2018-02-06第三天 不能再了,反思到位就差改变
- 一个小故事,我的思考。
- Docker应用:容器间通信与Mariadb数据库主从复制
- 第三节|第三节 快乐和幸福(12)
- 你到家了吗
- 一个人的碎碎念
- 遇到一哭二闹三打滚的孩子,怎么办┃山伯教育
- 死结。
- 我从来不做坏事
- 赢在人生六项精进二阶Day3复盘