题目 打印1到最大的n位数。
示例: 1 2 3 输入 n = 1 打印 1 2 3 4 5 6 7 8 9
思路 + 代码 常规操作是暴力循环打印 1 到 n 位数,但是大数问题,存在数值溢出。
采用字符串 或者数组 存储中间结果。
思路1 用一个 长度为 n 的数组存储,然后分别在最后一位计算,每次加一 ,逢十进一。
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 public class PrintToNNumber { private static boolean increment (int [] nums) { if (nums==null || nums.length==0 ) return false ; int overflow = 0 ; int len = nums.length; for (int i = len - 1 ; i >= 0 ; i--) { int nSum = overflow + nums[i]; if (i==len-1 ){ nSum++; } if (nSum < 10 ) { nums[i] = nSum; return true ; } if (i==0 ){ return false ; } nums[i] = 0 ; overflow = 1 ; } return false ; } public static void printArray (int [] nums) { int len = nums.length; boolean isZero = true ; for (int i = 0 ; i < len; i++) { if (nums[i]!=0 ) isZero = false ; if (!isZero) { System.out.print(nums[i]); } } System.out.println(); } public static void main (String[] args) { int n = 3 ; int [] nums = new int [n]; while (increment(nums)){ printArray(nums); } } }
思路2 使用递归方法 ,递归到组后一位,然后依次往前打印。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 private static void recursive (int [] nums, int index) { if (nums.length == index) { printArray(nums); return ; } for (int i = 0 ; i < 10 ; i++) { nums[index] = i; recursive(nums, index+1 ); } } public static void main (String[] args) { int n = 3 ; int [] nums = new int [n]; recursive(nums, 0 ); }