【剑指offer】面试题17：打印从 1 到最大的 n 位数

系统管理员 2022-03-30 06:48 169阅读 0赞

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

*  ##  1、跳进面试官的陷进 ##

这个题目看起来很简单。我们看到这个问题后，最容易想到的办法是求出最大的n位数，然后用一个循环从1开始逐个打印。于是我们很容易写出下面的代码：

public class Print1ToMaxOfNDigits {
    
    	// 方法一：没有考虑大数的问题，跳进了面试官的陷进
    	public void print1ToMaxOfNDigits_Method1(int n){
    		int number = 1;
    		int i = 0;
    		// 找出最大数 + 1 = number
    		while(i++ < n){
    			number *= 10;  // number = 10 的n次方
    		}
    		// 打印
    		for (i = 1; i < number; i++) {
    			System.out.println(i);
    		}
    	}
    	
    	// 测试
    	public static void main(String[] args) {
    		Print1ToMaxOfNDigits ptd = new Print1ToMaxOfNDigits();
    		ptd.print1ToMaxOfNDigits_Method1(100);
    	}
    }

初看之下好像没有什么问题，但如果仔细分析这个问题，我们就能注意到**面试官没有规定 n 的范围**。当输入n很大的时候，我们求最大的n位数是不是用整型（int)或者长整型（long)都会溢出？也就是说**我们需要考虑大数问题。这是面试官在这道题里设置的一个大陷阱。**

*  ## 2、在字符串上模拟数字加法的解法，绕过陷进才能拿到Offer ##

经过前面的分析，我们很自然的想到解决这个问题需要一个大数。最常用的也是最容易的**用字符串或者数组表达大数**。接下来我们用字符串和数组分别来解决大数问题。

我们需要做两件事情：

1、在字符串表达的数字上模拟加法；

2、把字符串表达的数字打印出来。需要注意的是当实际数字不够n位的时候，在字符串的前半部分补0，但是打印的时候，这些0不能打印出来。

*  **字符串实现**

public class Print1ToMaxOfNDigits {
    
    	// 方法二：在字符串上模拟数字加法的模式
    	public static void print1ToMaxOfNDigits_Method2(int n){
    		if(n <= 0){
    			return;
    		}
    		
    		// 创建一个字符串对象
    		StringBuffer number = new StringBuffer();
    		
    		for (int i = 0; i < n; i++) {
    			number.append('0');  // 初始化为0
    		}
    		
    		while(!increment(number)){
    			printNumber(number);
    		}
    	}
    	// 在字符串中模拟加1操作
    	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;   // 当前值
    			// 只有是个位时，数值加1
    			if(i == nLength - 1){
    				nSum++;
    			}
    			// 满10进1
    			if(nSum >= 10){
    				if(i == 0){
    					// 超过n位了
    					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 isBeginAtZero = true;
    		for (int i = 0; i < number.length(); i++) {
    			if(isBeginAtZero && number.charAt(i) != '0'){
    				isBeginAtZero = false;
    			}
    			if(!isBeginAtZero){
    				System.out.print(number.charAt(i));
    			}
    		}
    		System.out.println();
    	}
    
    
    	// 测试
    	public static void main(String[] args) {
    		Print1ToMaxOfNDigits ptd = new Print1ToMaxOfNDigits();
    		ptd.print1ToMaxOfNDigits_Method2(5);
    	}
    }

*  **数组实现**

public class Solution {
        public void printToMaxOfNDedits(int n){
            if(n < 0)
                return;
            if (n ==0 ){
                System.out.println("0");
            }
            char [] num = new char[n];
            // 初始化
            for (int i = 0; i < num.length; i++) {
                num[i] = '0';
            }
            while(!increment(num)){
                print(num);
            }
        }
        private static boolean increment(char [] num){
            boolean isEnd = false;
            int len = num.length;
            int nTakeOver = 0;  // 进位
            for (int i = len - 1; i >= 0 ; i--) {
                int nSum = num[i] - '0' + nTakeOver;  // 当前值
                // 只有是个位时，数值加1
                if(i == len - 1)
                    nSum++;
                // 满10进1
                if (nSum > 9){
                    if(i == 0){
                        // 超过n位
                        isEnd = true;
                    }else {
                        nTakeOver = 1;
                        num[i] = '0';
                    }
                }else {
                    num[i] = (char) ('0' + nSum);
                    break;
                }
            }
            return isEnd;
        }
        private static void print(char [] num){
            StringBuilder str = new StringBuilder();
            boolean isBegin = false;
            int len = num.length;
            for (int i = 0; i < len; i++) {
                if(num[i] != '0' && !isBegin){
                    isBegin = true;
                }
                if (isBegin){
                    str.append(String.valueOf(num[i]));
                }
            }
     
            if(str.toString().matches("^9+$")){
                System.out.println(str.toString()+" ");
            } else {
                System.out.print(str.toString()+" ");
            }
        }
    }

*  ## 3、把问题转化成数字排列的解法，递归让代码更加简洁  【面试用】 ##

上面使用数组和字符串模拟整数的加法，代码有点复杂，在面试中不容易实现。那么现在我们换一种思路：

如果我们在数字前面补0，就会发现n位所有十进制数其实就是n个从0到9的**[全排列][Link 1]**。也就是说，我们把数字的每一位都从0到9排列一遍，就得到了所有的十进制数。只是在打印的时候，排在前面的0不打印出来罢了。

全排列用递归很容易表达，数字的每一位都可能是0~9中的每一个数，然后设置下一位。递归结束的条件是我们已经设置了数字的最后一位。

public class Print1ToMaxOfNDigits {
    
    	// 方法三：全排列 【面试用】 
    	public static void print1ToMaxOfNDigits_Method3(int n){
    		if(n <= 0){
    			return;
    		}
    		
    		char[] num = new char[n];
    		// 初始化为0
    		for (int i = 0; i < num.length; i++) {
    			num[i] = '0';
    		}
            // 全排列：每一个位置上都会出现0~9
    		for (int i = 0; i < 10; i++) {
    			num[0] = (char) (i + '0');
    			print1ToMaxOfNDigitsRecurstively(num, n, 0);
    		}
    	}
    
    	private static void print1ToMaxOfNDigitsRecurstively(char[] num, int length, int index) {
    		if(index == length - 1){
    			print(num);
    			return;
    		}
    		for (int i = 0; i < 10; i++) {
                // index + 1控制元素在数组中的下标
    			num[index + 1] = (char) (i + '0');
    			print1ToMaxOfNDigitsRecurstively(num, length, index + 1);
    		}
    	}
    
        // 打印字符串
    	private static void print(char[] num) {
    		StringBuilder str = new StringBuilder();
    		boolean isBeginAtOne = false;  
    		int len = num.length;
    		
    		for (int i = 0; i < len; i++) {
    			if(num[i] != '0' && !isBeginAtOne){
    				isBeginAtOne = true;
    			}
    			if(isBeginAtOne){
    				str.append(String.valueOf(num[i]));
    			}
    		}
    		
    		if(str.toString().matches("^9+$")){
    			System.out.println(str.toString() + " ");
    		}else{
    			System.out.print(str.toString() + " ");
    		}
    	}
    
    	// 测试
    	public static void main(String[] args) {
    		Print1ToMaxOfNDigits ptd = new Print1ToMaxOfNDigits();
    		ptd.print1ToMaxOfNDigits_Method3(2);
    	}
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

![20190105111518933.png][]

**将char改为byte。**

public class Solution {
        public void printToMaxOfNDedits(int n){
            if(n < 0)
                return;
            if (n ==0 ){
                System.out.println("0");
            }
            byte [] num = new byte[n];
            //初始化
            for (int i = 0; i < num.length; i++) {
                num[i] = 0;
            }
            while(!increment(num)){
                print(num);
            }
        }
        private static boolean increment(byte [] num){
            boolean isEnd = false;
            int len = num.length;
            byte nTakeOver = 0;//进位
            for (int i = len - 1; i >= 0 ; i--) {
                byte nSum = (byte) (num[i]  + nTakeOver);//byte相加，需要强转
                //只有是个位时，数值加1
                if(i == len - 1)
                    nSum++;
                //满10进1
                if (nSum > 9){
                    if(i == 0){
                        //超过n位
                        isEnd = true;
                    }else {
                        nTakeOver = 1;
                        num[i] = 0;
                    }
                }else {
                    num[i] = nSum;
                    break;
                }
            }
            return isEnd;
        }
        private static void print(byte [] num){
            StringBuilder str = new StringBuilder();
            boolean isBegin = false;
            int len = num.length;
            for (int i = 0; i < len; i++) {
                if(num[i] != 0 && !isBegin){
                    isBegin = true;
                }
                if (isBegin){
                    str.append(String.valueOf(num[i]));
                }
            }
     
            if(str.toString().matches("^9+$")){
                System.out.println(str.toString()+" ");
            } else {
                System.out.print(str.toString()+" ");
            }
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

[Link 1]: https://baike.so.com/doc/6677965-6891841.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220330/925a790b22db44ccb442377989d81744.png
[20190105111518933.png]: /images/20220330/18812bc2a96148b39ef2d26b583eed56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220330/806d54ebb9d84990a2c42139f2bb0e15.png