面试题12-打印1到最大的n位数

Posted on Edited on In

题目

输入数字n， 按顺序打印出从1 最大的n 位十进制数。比如输，则打印出1 、2 、3 一直到最大的3 位数即999 。

1
2
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

解题

此题目主要考察某些编程语言（JAVA/C/C++等）存在的大数问题。

直接法

直接法只能用于一些不存在大数问题的语言，如Python。

为什么Python没有大数问题：

refs:

深度剖析凭什么python中整型不会溢出

Python 3 的 int 类型详解（为什么 int 不存在溢出问题？）

1
2
3
class Solution:
    def printNumbers(self, n):
        return [i for i in range(1,10**n)]

字符串模拟加法

最常用也是最容易的方法是用字符串或者数组表达大数。

字符串里每个字符都是0到9之间的某一个字符，用来表示数字中的一位。这里用一个长度为n+1的字符串来表示数字，第0位（也即最高位）用来表示溢出的进位（《剑指offer》中则是最高位用的\0表示结束符，也就是个空格；判断是否溢出是判断加法计算后第0位是否>10）。当实际数字不够n 位的时候，在字符净的前半部分补0 。

需要做两件事： 一是在字符串表达的数字上模拟加法，二是把字符串表达的数字打印出来。

其中的两个问题分别是：1）如何判断加法溢出而停止；2）如何判断打印出符合习惯的数，不包含首位的0。

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
import java.util.Arrays;

public class printToMaxOfNDigits1 {
	
	public static void main(String[] args) {
		printToMaxOfNDigits1(3);
	}
	
	public static void printToMaxOfNDigits1(int n) {
        if(n <= 0) {
            return;
        }
        char[] nums = new char[n + 1];
        Arrays.fill(nums, '0');
        while(!increment(nums)) {
            printNum(nums);
        }
    }

    public static boolean increment(char[] nums) {
    	//这是一个能够判断溢出的
        int carry = 0;
        for(int i = nums.length - 1; i >= 0; i--) {
        	// 转换为int
            int temp = nums[i] - '0' + carry;
            //因为是加1，所以肯定是在最后一位上加1了
            if(i == nums.length - 1) {
                temp++;
            }
            // 查看进位
            carry = temp / 10;
            // 取个位
            temp %= 10;
            // 转换为字符串
            nums[i] = (char)(temp + '0');
        }
        // 最高位进位为1时则说明溢出了,它实现了用0(1 ）时间判断是不是已经到了最大的n位数
        return nums[0] == '1';
    }

    // 打印
    public static void printNum(char[] nums) {
        int index = 0;
        // 除去前面无意义的0
        for(; index < nums.length; index++) {
            if(nums[index] != '0'){
                break;
            }
        }
        for(; index < nums.length; index++) {
        	// 连续打印
            System.out.print(nums[index]);
        }
        System.out.println();
    }

}

递归法全排

n位所有十进制数其实就是n个从0到9 的全排列。

递归结束的条件是我们已经设置了数字的最后一位。

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
public class printToMaxOfNDigits2 {
	
	public static void main(String[] args) {
		printToMaxOfNDigits2(2);
	}
	
    public static void printToMaxOfNDigits2(int n) {
        if(n <= 0) {
            return;
        }
        char[] nums = new char[n];
        recursiveProductNum(0, n, nums);
    }

    public static void recursiveProductNum(int index, int length, char[] nums) {
        // 填充完所有位后打印
    	if(index == length) {
            printNum(nums);
            return;
        }
    	// 每一位从0-9循环
        for(char i = '0'; i <= '9'; i++){
        	// 填充第index位
            nums[index] = i;
            // 递归填充下一位
            recursiveProductNum(index + 1, length, nums);
        }
    }

    public static void printNum(char[] nums) {
        int index = 0;
        for(; index < nums.length; index++) {
            if(nums[index] != '0'){
                break;
            }
        }
        for(; index < nums.length; index++) {
            System.out.print(nums[index]);
        }
        System.out.println();
    }
}

总结

  1. 字符串是一个简单、有效的表示大数的方法。
  2. 扩展：8 个bit 的char 型字符最多能表示256 个字符，用char 型字符串来表示十进制的数字并没有充分利用内存，有一些浪费。有没有更高效的方式来表示大数？
  3. 进阶题目：以实现任意两个整数的加法。

References

《剑指offer》

剑指Offer-14-打印1到最大的n位数