打印从1到最大的n位数 - 大数问题

快来打我* 2022-11-20 07:00 107阅读 0赞

## 打印从1到最大的n位数 ##

> 这个题在leetcode上被玩坏了，做成了跟1+1是一个等级的难度，我就自由分析一下吧

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

**示例 1:**

> 输入: n = 1  
> 输出: \[1,2,3,4,5,6,7,8,9\]

说明：  
用返回一个整数列表来代替打印  
n 为正整数

--------------------

## 分析 ##

### 按大数问题分析 ###

如果是大数问题，n的取值可能不会小，比如`n = 100`时，那么这个题就是要输出1到位数为100位的10进制数（一般大数问题是输出，不会让以数组的形式返回数据）

> 试想，输出从1到100位的10进制数，已经超时了。

假设我们不限于时间，而针对这个问题的大数问题，则如何写出解决代码？

假设这个大数的长度是100000，开辟一个数组arr\[100000\];定义一个变量记录数组长度cur\_len，初始值是0;写一个函数实现“数字字符串+1”功能；然后循环n次，执行n次`str_increment`，倒叙输出`arr`n次。

> 此代码非解，只是写出来解决这个大数问题，读者可以参考来改写代码，copy改代码直接可以运行得出结果！

*  由于这是个递归式的程序，考虑深度会不会导致`runtime error`
 *  在正常条件下不会超时，因为只有一个递归入口

#include<stdio.h>
    void str_increment(char *arr, int pos, int *cur_len){ 
        //如果pos已经==cur_len了，说明高位进1
        if(pos == *cur_len){ 
            //注意：加括号，否则错
            (*cur_len)++;
            *(arr + pos) = '1';
            return ;
        }
        if((*(arr + pos) - 47) % 10 == 0){ 
            *(arr + pos) = '0';
            str_increment(arr, pos + 1, cur_len);
        }else{ 
            *(arr + pos) = (*(arr + pos) + 1);
            return ;
        }
        return ;
    }
    
    int main(){ 
        // 开辟100000大小的数组arr
        char *arr = malloc(100000*sizeof(char));
        // cur_len -> int 类型，因为假设了大数的长度是100000
        int cur_len = 0;
        // 循环n次，执行n次str_increment()，倒叙输出n次arr
        int i,j,n = 1000000;
        for(i = 0; i < n; i++){ 
            str_increment(arr,0,&cur_len);
            //倒序输出arr
            for(j = cur_len-1; j >=0 ;j--){ 
                printf("%c", *(arr + j));
            }
            printf("\n");
        }
    }