劍指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的功能，我們可以參考這種思路實作兩個數字的相加功能。另外還有一個需要注意的問題：如果輸入的數字中有負數，那麼我們應該怎麼處理？