最优算法100例之24-打印1到最大的n位数

专栏主页：计算机专业基础知识总结（适用于期末复习考研刷题求职面试）系列文章https://blog.csdn.net/seeker1994/category_12585732.html

题目描述

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

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

题解报告

最优解法(C)：
采用递归，问题类似于数字排列，每个位置可取0-9这10个数字。
void printNumbers(int n){
	if(n < 0) return ;
	char *number = new char[n+1];
	number[n] = '\0';
	for(int i=0; i<10;i++){//第一位依次放0,1...9进行递归 
		number[0] = i+'0';
		PrintNum(number, n, 0);
	}
} 
PrintNum(char *number,int n,int index){
	if(index == n-1){//找到末尾，输出 
		OutputNumber(number);//输出该数 
	}
	for(int i=0; i<10; i++){//继续递归 
		number[index + 1] = i+'0';
		PrintNum(number,n,index + 1);
	} 
}
//输出时保证没有前导0
void OutputNumber(char* number){
	int len = strlen(number);
	bool flag = false;
	for(int i=0;i<len;i++){
		if(!flag && number[i] != '0'){
			flag = true;
		}
		if(flag)
			printf("%c",number[i]);
	}	
} 

专栏主页：计算机专业基础知识总结（适用于期末复习考研刷题求职面试）系列文章https://blog.csdn.net/seeker1994/category_12585732.html