剑指offer——面试题17：打印从1到最大的n位数

文章目录

题目描述分析（以n=3为例）代码原始代码好理解的版本（只适用于n=3的时候） 笔记`char* number = new char[n+1];`C++中的new ：动态分配内存整型`int`与长整型`long long`的数据范围： leecode上的这道题题目描述：分析：代码：

题目描述

剑指的剑终于打对了~ 题目描述： 输入数字n,按顺序打印出从1到最大的n位十进制数。比如输入3,则打印出1、2、3一直到最大的3位数即999。

分析（以n=3为例）

为啥不直接打印？因为当n很大的时候，数据会溢出，无法AC。

所以有了大数问题的分析方法： 没有递归之前的思路是一个位一个位的放值，先放第0位，也就是百位数，然后是十位，最后是个位。每一个百位值都对应有9个十位的值，对应有9个个位的值。这个图是自己理思路时写的代码，仅供参考。

书上的递归思路还真的蛮难理解的，看了很长时间也没明白，我自己的理解是下图，每回固定一个值，然后遍历去固定下一位的值并打印： 这个代码更好理解一些：

//第0位的数值设置 for(int i=0;i<10;i++) { number[0] = i+'0'; //第1位置的数值放置 for(int i=0;i<10;i++) { number[1] = i+'0'; //第2位置的数值放置 for(int i=0;i<10;i++) { number[2] = i+'0'; PrintNumber(number); } } }

代码

将打印数字的问题转换为字符的排列（大数问题）

原始代码

/*-------打印从1到最大的n位数--------*/ #include<iostream> using namespace std; void PrintNumber(char* number); void PrintRecursively(char* number, int length, int index); //排列数字准备打印 void PrintRecursively(char* number, int length, int index) { //递归条件就是已经设置了数字的最后一位 if(index == length-1) { PrintNumber(number); return; } //递归核心：怎么理解? //第1第2位置的数值放置 for(int i=0;i<10;i++) { number[index+1] = i+'0'; PrintRecursively(number, length, index+1);//递归（调用完函数之后回到这里），number和length一直没变，index在变化 } } //打印此时字符串表示的数字 void PrintNumber(char* number) { bool isBeginning0 = true; int nLength = strlen(number); for(int i=0;i<nLength;i++) { if(isBeginning0 && number[i]!='0')//找到前边的不是0的字符了才打印 isBeginning0 = false; if(!isBeginning0) { printf("%c", number[i]); } } printf("\t"); } //全排列 void Print1ToMaxOfNDigits(int n) { //特殊处理 if(n<=0) return; //处理 char *number = new char[n+1]; number[n] = '\0'; //第0位的数值设置 for(int i=0;i<10;i++) { number[0] = i+'0'; PrintRecursively(number, n, 0); } delete[] number; } int main() { int n = 3; Print1ToMaxOfNDigits(n); return 0; }

好理解的版本（只适用于n=3的时候）

/*-------打印从1到最大的n位数（好理解的版本）--------*/ #include<iostream> using namespace std; void PrintNumber(char* number); //打印此时字符串表示的数字 void PrintNumber(char* number) { bool isBeginning0 = true; int nLength = strlen(number); for(int i=0;i<nLength;i++) { if(isBeginning0 && number[i]!='0')//找到前边的不是0的字符了才打印 isBeginning0 = false; if(!isBeginning0) { printf("%c", number[i]); } } printf("\t"); } //全排列 void Print1ToMaxOfNDigits(int n) { //特殊处理 if(n<=0) return; //处理 char *number = new char[n+1]; number[n] = '\0'; //第0位的数值设置 for(int i=0;i<10;i++) { number[0] = i+'0'; //第1位置的数值放置 for(int i=0;i<10;i++) { number[1] = i+'0'; //第2位置的数值放置 for(int i=0;i<10;i++) { number[2] = i+'0'; PrintNumber(number); } } } delete[] number; } int main() { int n = 3; Print1ToMaxOfNDigits(n); return 0; }

笔记

char* number = new char[n+1];

新建一个字符串指针并给其分配n+1个位置的内存，但并没有赋初值，之后要用delete[] number;操作释放内存。

C++中的new ：动态分配内存

new可以说是个一个关键字，也可以说是一个运算符，并且可以被重载。 1).C++中通过new关键字进行动态内存申请 2).C++中的动态内存分配是基于类型进行的 3).delete关键字用于内存释放

申请变量 Type* pointer = new Type; //... delete pointer; 申请数组 Type* pointer = new Type[N]; //... delete[] pointer; //比如 int * foo; foo = new int [5]; 动态分配内存 int* p = new int; *p = 5; //指针p的值为5 p = new int[10];//动态分配了10个int型的内存空间 delete[] p;//释放分配的内存空间

整型int与长整型long long的数据范围：

int：-2147483648 ~ 2147483647 long long：-9223372036854775808 ~ 9223372036854775807

leecode上的这道题

题目描述：

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

示例 1:

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

分析：

这个输出的是一个数组，证明不考虑数据溢出的问题，相对简单，直接将从1~n位最大数的值放到结果数组里即可。

代码：

class Solution { public: vector<int> printNumbers(int n) { vector<int> res; for(int i = 1; i < pow(10, n); i ++) res.push_back(i); return res; } };