菜鸟系列之C/C++经典试题(十)

本是古典何须时尚 2022-08-12 00:21 128阅读 0赞

**打印1到最大的n位数**

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

方法一：

这道题一看感觉很简单，首先求的n位数的最大值，然一个从1到这个最大值的循环就搞定了， 如果真的就把这样的答案面试官的话， 后果很是严重。首先， 没有考虑到获得的这个最大的数会不会溢出，如果溢出了， 答案肯定不对。这个代码比较简单， 我就不列出来了。

方法二:

很明显， 这道题我们可以用递归做， 就是每当多添加一位时， 我就把所以的都打印一遍连带刚添加的这个位， 比如之前是1位的时候， 我当我变成两位数的时候， 就从1-9设置十位数， 每当设置一个值比如1的时候， 就打印除了这个1这个位剩下的所有的可能的数的情况，注意这里的每一个最高位只能1-9，但是别的位的范围是0-9。但是这样的递归很有可能会导致调用栈溢出，我算了一下，最大的8字节的long long类型的整数最大值能达到43位， 这样的话如果用递归去做， 很有可能…..不管怎么样， 这题考的就是个思路， 好了不多说了， 我把我的实现给列出来：

inline void printOneNum(char *pNumbers)
    {
        static int count = 0;
    
        printf("%-6s,", pNumbers);
    
        if (++count == 10)
        {
            cout << endl;
            count = 0;
        }
    }
    
    inline void printOneNum(long long val)
    {
        static int count = 0;
    
        printf("%-6ld", val);
    
        if (++count == 10)
        {
            cout << endl;
            count = 0;
        }
    }
    
    void digitRecursive(char *pNumbers, int offset, int bitIndex, const int allBits)
    {
        if (bitIndex == allBits)
        {
            printOneNum(pNumbers + offset);
            return;
        }
    
        for (int i = 0; i < 10; ++i)
        {
            pNumbers[bitIndex] = i + '0';
            digitRecursive(pNumbers, offset, bitIndex + 1, allBits);
        }
    }
    
    void printEachBitsNumbers(char *pNumbers, int bitIndex, const int allBits)
    {
        for (int i = 1; i < 10; ++i)
        {
            pNumbers[bitIndex] = i + '0';
            digitRecursive(pNumbers, bitIndex, bitIndex + 1, allBits);
        }
    }
    
    inline int getMaxBitOfLONGLONG()
    {
        return (int)log(LLONG_MAX);
    }
    
    long long getMaxValueOfNBits(const int n)
    {
        if (n > getMaxBitOfLONGLONG())
        {
            return -1;
        }
    
        register long long max = 1;
        for (int i = 0; i < n; ++i)
        {
            max *= 10;
        }
    
        return max - 1;
    }
    
    void printAllWithoutRecursive(const int n)
    {
        register const long long max = getMaxValueOfNBits(n);
    
        for (long long i = 1; i <= max; ++i)
        {
            printOneNum(i);
        }
    }
    
    void printAllNumbers(const int n)
    {
        if (n < 0)
        {
            fprintf(stderr, "Input param error, the n must large than 0\n");
            return;
        }
    
        if (n < getMaxBitOfLONGLONG())
        {
            printAllWithoutRecursive(n);
            return;
        }
    
        char *pNumbers = new char[n + 1];
        pNumbers[n] = '\0';
    
        for (int i = n - 1; i >= 0; --i)
        {
            printEachBitsNumbers(pNumbers, i, n);
        }
    
        delete[] pNumbers;
    }

上面的代码的话， 我两中都实现了， 就是当输入的位数比较小的时候， 不溢出， 就用方法一， 如果会溢出， 就用方法二。

当然还有别的实现方法， 这里我就不列出来了。

如果有错误欢迎指出， 分享请辨明

感觉好的话就顶一个， 感觉不错的话就踩一个。