题目
输入数字 n,按照顺序打印出从 1 到最大的 n 位十进制数。
解答
解法1[Java]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
| public class Problem17Solution1 { public void print1ToMaxOfNDigits(int n) { if (n <= 0) { return; }
char[] number = new char[n]; Arrays.fill(number, '0');
while (!increment(number)) { printNumber(number); } }
private boolean increment(char[] number) { int currentDigitValue; int carry = 0; for (int index = number.length - 1; index >= 0; index--) { currentDigitValue = (number[index] - '0') + carry; if (index == number.length - 1) { currentDigitValue++; }
if (currentDigitValue >= 10) { if (index == 0) { return true; } else { currentDigitValue -= 10; carry = 1; number[index] = (char) ('0' + currentDigitValue); } } else { number[index] = (char) ('0' + currentDigitValue); break; } }
return false; }
private void printNumber(char[] number) { boolean isLeadingZero = true; for (char c : number) { if (isLeadingZero && (c - '0') != 0) { isLeadingZero = false; }
if (!isLeadingZero) { System.out.print(c); } }
System.out.println(); } }
|
思路
使用字符串表示数字,同时模拟加法运算,处理进位等操作。
解法2[Java]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| public class Problem17Solution2 { public void print1ToMaxOfNDigits(int n) { if (n <= 0) { return; }
char[] number = new char[n]; Arrays.fill(number, '0');
for (int i = 0; i < 10; ++i) { number[0] = (char) (i + '0'); print1ToMaxOfNDigitsRecursively(number, n, 0); } }
private void print1ToMaxOfNDigitsRecursively(char[] number, int length, int index) { if (index == length - 1) { printNumber(number); } else { ++index; for (int i = 0; i < 10; ++i) { number[index] = (char) (i + '0'); print1ToMaxOfNDigitsRecursively(number, length, index); } } }
private void printNumber(char[] number) { boolean isLeadingZero = true; for (char c : number) { if (isLeadingZero && (c - '0') != 0) { isLeadingZero = false; }
if (!isLeadingZero) { System.out.print(c); } }
System.out.println(); } }
|
思路
全排列的方式,通过递归实现。
测试用例设计
正常值:1、2、3…
边界值:0、-1