剑指offer--位运算--打印1到最大的n位数

                                 打印1到最大的n位数

概念

如果面试题是关于位的整数并且没有限定n的取值范围，或者输入任意大小的整数，那么这道题目很有可能是需要考虑大数问题的字符串是一种简单、有效地表示大数的方法。

思路

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

代码

字符串

public class Test1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //print1ToMaxOfNDights1s(sc.nextInt());
        print1ToMaxOfNDights1s(3);
    }
    public static void print1ToMaxOfNDights1s(int n) {
        if(n<=0)
        {
            return;
        }
        char[] digit = new char[n];
        for(int i=0;i<n;i++)
        {
            digit[i]='0';
        }
        for(int i=n-1;i>=0;i--) {
            while(digit[i]!='9') {
                int m=0;
                digit[m]++;
                while(m<n-1 && digit[m]>'9') {
                    digit[m]='0';
                    digit[m+1]++;
                    m++;
                }
                printdigits(digit);
            }
        }
    }

    private static void printdigits(char[] digit) {
        int m = digit.length-1;
        while('0' == digit[m])
        {
            m--;
        }
        for(int i=m;i>=0;i--)
        {
            System.out.print(digit[i]);
        }
        System.out.println();
    }
}

方法2 

public  static void main(String[] args) {
        printToMaxOfDigits(3);
    }

    //打印1到最大的n位数
    public static void printToMaxOfDigits(int n){
        if(n <= 0){
            System.out.println("输入的n没有意义");
            return;
        }
        //声明字符数组,用来存放一个大数
        char number[] = new char[n];
        for (int i = 0; i < number.length; ++i) {
            //放字符0进行初始化
            number[i] = '0';
        }
        while(!incrementNumber(number)){
            //如果大数自加，直到自溢退出
            printNumber(number);
            //打印大数
        }
    }
    //自加
    private static boolean incrementNumber(char[] number) {
        boolean isOverflow = false;
        //判断是否溢出
        int nTakeOver = 0;
        //判断是否进位
        int nLength = number.length;
        for (int i = nLength - 1; i >= 0 ; --i) {
            int nSum = number[i] - '0' + nTakeOver;
            //取到第i位的字符转换为数字 +进位符
            if(i == nLength - 1){
                //末尾自加1
                ++nSum;
            }
            if(nSum >= 10){
                if(i == 0){
                    isOverflow = true;
                }else{
                    nSum -= 10;
                    nTakeOver = 1;
                    number[i] = (char) ('0' + nSum);
                }
            }else{
                number[i] = (char) (nSum + '0');
                break;
            }
        }
        return isOverflow;
    }
    //打印数字
    private static void printNumber(char[] number) {
        boolean isBeginning0 = true;
        int nLength = number.length;
        for (int i = 0; i < nLength; ++i) {
            if(isBeginning0 && number[i]!='0'){
                isBeginning0 = false;
            }
            if(!isBeginning0){
                System.out.print(number[i]);
            }
        }
        System.out.println();
    }

全排列递归

import java.util.Scanner;

/**
 * @Auther: liuhaidong
 * Data: 2019/10/15 0015、20:28
 * Description:数组全排列
 * @version: 1.0
 */
public class Test2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        print1ToMaxOfNDigits2(sc.nextInt());
    }
    /**
     * 采用递归的方法
     */
    public static void print1ToMaxOfNDigits2(int n) {
        if (n <= 0)
        {
            return;
        }
        char[] number = new char[n];
        for (int k = 0; k < number.length; k++)
        {
            number[k] = '0';
        }
        for (int i = 0; i <= 9; i++) {
            makeNumber(n, number, i, 0);
        }
    }

    /**
     * 生成数字
     */
    private static void makeNumber(int n, char[] number, int nNumber, int index) {
        if (index == number.length - 1) {
            number[index] = (char) (nNumber + '0');
            printCharNumber2(number);
            // 打印数字代码与第一个方法一样
            return;
        } else {
            number[index] = (char) (nNumber + '0');
            for (int i = 0; i <= 9; i++) {
                makeNumber(n, number, i, index + 1);
            }
        }
    }

    /**
     * 打印字符数组形成的数字
     * 自己的方法：找出第一个非零字符位置，往后进行打印
     */
    private static void printCharNumber2(char[] number) {
        int beginner = number.length;
        // 不写成number.length-1，以防写出0
        for (int i = 0; i <= number.length - 1; i++) {
            if ((number[i] - '0') != 0) {
                beginner = i;
                break;
            }
        }
        for (int i = beginner; i <= number.length - 1; i++) {
            System.out.print(number[i]);
        }
        if (beginner != number.length)
            // 数字为0时，换行符不输出
            {
                System.out.println();
            }
    }
}

扩展题目

1 在前面的代码中，我们用一个char型字符表示十进制数字的一位。8bit的 char型字符最多能表示256个字符，而十进制数字只有0 〜 9 的 10个数字。因此，用 char型字符来表示十进制数字并没有充分利用内存，有一些浪费。有没有更高效的方式来表示大数？

参考https://blog.csdn.net/weixin_41563161/article/details/102575854

 

 

2 定义一个函数，在该函数中可以实现任意两个整数的加法。由于没有限定输入两个数的大小范围，我们也要把它当作大数问题来处理。在前面的代码的第一种思路中，实现了在字符串表示的数字上加1的功能，我们可以参考这种思路实现两个数字的相加功能。另外还有一个需要注意的问题：如果输入的数字中有负数，那么我们应该怎么处理？