【题17 打印从1到最大的n位数】

红太狼 2022-03-26 00:51 187阅读 0赞

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

**<跳进陷阱>**  
最容易想到的办法是先求出最大的n位数，然后用一个循环从1开始逐个打印。

**实现**

package ti17;
    
    public class Lianxi1 {
    	//跳进面试官的陷阱： 
    	public static void print1ToMaxOfNDigits(int n) {
            int number = (int) Math.pow(10, n);//10的n次方
            for (int i = 1; i < number; ++i)
                System.out.println(i);
        }
    	public static void main(String[] args) {
    		Lianxi1 lx = new Lianxi1();
    		int n = 3;
    		lx.print1ToMaxOfNDigits(n);
    	}
    }

**存在问题：** 没有规定n的范围。  
当输入的n很大的时候，求最大的n位数是不是用整形（int）或者长整形（long long）都会溢出？也就是说要考虑**大数问题**。——**陷阱1**

**<在字符串上模拟数字加法的解法，绕过陷阱>**  
解决大数问题，最常用的就是用**字符串或者数组**表达大数。  
**用字符串解决大数**  
表示数字最大是n位的，需要一个长度为n+1的字符串（字符串中最后一位是结束符号‘\\0’）。当实际数字不够n位的时候，在字符串的前半部分补0.  
（1） 把字符串中的每个数字都初始化为‘0’。  
（2） 每一次为字符串表示的数字加1，再打印出来。  
**只需要两件事：**  
（1） 在字符串表达的数字上模拟加法；  
（2） 把字符串表达的数字打印出来。  
我们需要知道什么时候停止加1，即什么时候到了最大的n位数，“999999999……99”（n个9）.  
最简单的的办法就是在每次递增之后，都调用函数比较字符串和最大的n位数“9999….999”，  
如果相等则表示已经到了最大的n位数并终止递增。虽然调用函数很简单，但对于长度为n的字符串，它的时间复杂度为O（n）。

如何在每一次增加1之后**快速判断是不是到了最大的n位数**是本题的另一个**陷阱2。**

**考虑如何打印字符串表示的数字。**  
当数字不够n位时，在数字的前面补0，打印的时候这些补位的0不应该打印出来。  
定义函数，在这个函数里，只要在碰到第一个非0的字符之后才开始打印，直至字符串的结尾。能不能按照我们的阅读习惯**打印数字**是设置的另一个**陷阱3.**

**实现**

package ti17;
    
    public class Lianxi2 {
    	//在数组上模拟数字加法的解法，绕过陷阱
    	/**
    	 * 打印从1到最大的n位数：使用数组表示大数
    	 */
    	    // 使用数组实现对数进行+1操作
    	    public boolean increment(int[] number) {
    	        // 最高位产生进位标志
    	        boolean isOverFlow = false;
    
    	        // 进位位
    	        int carry = 0;
    
    	        for (int i = number.length - 1; i >= 0; i--) {
    	            int sum = number[i] + carry;
    	            if (i == number.length - 1) {
    	                sum++;
    	            }
    	            if(sum >= 10){
    	                if(i == 0)
    	                    isOverFlow = true;
    	                else{
    	                    sum = sum - 10;
    	                    carry = 1;
    	                    number[i] = sum;
    	                }
    	            }else{
    	                number[i]++;
    	                break;
    	            }
    	        }
    	        return isOverFlow;
    	    }
    
    	    // 打印数组中表示的数，如果数组中表示的数字位数小于n，则不打印前面的0
    	    public void print(int[] number) {
    	        // 标记：判断是否可以开始打印
    	        boolean isBeginning = false;
    	        for (int i = 0; i < number.length; i++) {
    	            if (!isBeginning && number[i] != 0) {
    	                isBeginning = true;
    	            }
    	            if (isBeginning)
    	                System.out.print(number[i]);
    	        }
    	        System.out.println();
    	    }
    
    	    public static void main(String[] args) {
    	        //使用数组来模拟大数
    	    	Lianxi2 lx = new Lianxi2();
    	        int[] number = new int[3];
    	        while(!lx.increment(number)){
    	            lx.print(number);
    	        }
    	    }
    }

**<把问题转换成数字排列的解法，递归让代码更简洁>**  
换一个思路考虑问题：  
如果在数字前面补0，会发现n位所有十进制数其实就是n个从0到9的全排列。  
也就是说：我们把数字的每一位都从0到9排列一遍，就得到了所有的十进制数。只是在打印的时候，排在前面的0不打印出来罢了。  
全排列的递归很容易表达，数字的每一位都可能是0~9中的一个数，然后设置下一位，递归结束的条件是我们已经设置了数字的最后一位。

**实现**

package ti17;
    
    public class Lianxi3 {
    	//把问题转化成数值排列的解法，递归让代码更简洁： 
    	/**
    	 * 打印从1到n位的最大数：使用递归实现全排列
    	 */
    	
    
    	    //打印数
    	    public void printNumber(StringBuffer sb){
    	        boolean flag = false;
    
    	        for(int i = 0; i < sb.length(); i++){
    	            if(!flag && sb.charAt(i) != '0'){
    	                flag = true;
    	            }
    	            if(flag){
    	                System.out.print(sb.charAt(i));
    	            }
    	        }
    	        if(flag)
    	            System.out.println();
    	    }
    
    	    //打印从1到n位的最大数
    	    public void Print1ToMaxOfNDigits(int n){
    	        if(n <= 0)
    	            return ;
    
    	        //初始化数字（用StringBuffer表示）
    	        StringBuffer sb = new StringBuffer(n);
    	        for(int i = 0; i < n; i++){
    	            sb.append('0');
    	        }
    
    	        print1ToMaxOfNDigits_Recursely(sb, n, 0);
    	    }
    
    	    public void print1ToMaxOfNDigits_Recursely(StringBuffer sb, int n, int index){
    	        if(index == n){
    	            printNumber(sb);
    	            return ;
    	        }
    
    	        for(int i = 0; i < 10; i++){
    	            sb.setCharAt(index, (char)(i+'0'));
    	            print1ToMaxOfNDigits_Recursely(sb, n, index+1);
    	        }
    	    }
    
    	    public static void main(String[] args) {
    	        Lianxi3 test = new Lianxi3();
    	        test.Print1ToMaxOfNDigits(3);
    	    }
    }

参考：  
1.《剑指offer》  
2.[https://blog.csdn.net/weixin\_37672169/article/details/80150580][https_blog.csdn.net_weixin_37672169_article_details_80150580]

[https_blog.csdn.net_weixin_37672169_article_details_80150580]: https://blog.csdn.net/weixin_37672169/article/details/80150580