《剑指offer》刷题笔记（代码完整性）：打印1到最大的n位数

本文主要是介绍《剑指offer》刷题笔记（代码完整性）：打印1到最大的n位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

《剑指offer》刷题笔记（代码完整性）：打印1到最大的n位数

转载请注明作者和出处：http://blog.csdn.net/u011475210
代码地址：https://github.com/WordZzzz/CodingInterviewChinese2
文章地址：https://github.com/WordZzzz/Note/tree/master/AtOffer
刷题平台：https://www.nowcoder.com/
题库：剑指offer
编者：WordZzzz

剑指offer刷题笔记代码完整性打印1到最大的n位数
- 前言
- 题目描述
- 解题思路
- C版代码实现
  - 字符串模拟
  - 递归

前言

这道题牛客网上没有，但是剑指offer上有，看完之后觉得挺有用的，所以我还是整理一下吧。

题目描述

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

解题思路

没有规定n的范围，所以我们需要考虑大数的问题。

方法一：字符串模拟

用字符串表示数字的时候，最直观的方法就是字符串里每个字符都是‘0’到‘9’之间的某一个字符，用来表示数字中的一位。因为数字最大是n位，所以我们需要一个长度为n+1的字符串（字符串结尾符号‘\0’，这个我记得之前强调过了）。当实际数字不够n位的时候在字符串前半部分补0，打印的时候不打印前半部分的0就好。同时我们用进位标志位作为循环终止条件。

方法二：递归

如果我们在数字前面补0的话，就会发现n位所有十进制数其实就是n个从0到9的全排列。也就是说，我们把数字的每一位都从0到9排列一遍，就得到所有的十进制数，只是我们在打印的时候，数字排在前面的0我们不打印出来罢了。

C++版代码实现：

字符串模拟：

// ====================方法一====================
void Print1ToMaxOfNDigits_1(int n)
{if (n <= 0)return;char *number = new char[n + 1];memset(number, '0', n);number[n] = '\0';while (!Increment(number)){PrintNumber(number);}delete[]number;
}// 字符串number表示一个数字，在 number上增加1
// 如果做加法溢出，则返回true；否则为false
bool Increment(char* number)
{bool isOverflow = false;int nTakeOver = 0;int nLength = strlen(number);for (int i = nLength - 1; i >= 0; i--){int nSum = number[i] - '0' + nTakeOver;if (i == nLength - 1)nSum++;if (nSum >= 10){if (i == 0)isOverflow = true;else{nSum -= 10;nTakeOver = 1;number[i] = '0' + nSum;}}else{number[i] = '0' + nSum;break;}}return isOverflow;
}// ====================公共函数====================
// 字符串number表示一个数字，数字有若干个0开头
// 打印出这个数字，并忽略开头的0
void PrintNumber(char* number)
{bool isBeginning0 = true;int nLength = strlen(number);for (int i = 0; i < nLength; ++i){if (isBeginning0 && number[i] != '0')isBeginning0 = false;if (!isBeginning0){printf("%c", number[i]);}}printf("\t");
}

递归：

// ====================方法二====================
void Print1ToMaxOfNDigits_2(int n)
{if (n <= 0)return;char* number = new char[n + 1];number[n] = '\0';for (int i = 0; i < 10; ++i){number[0] = i + '0';Print1ToMaxOfNDigitsRecursively(number, n, 0);}delete[] number;
}void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index)
{if (index == length - 1){PrintNumber(number);return;}for (int i = 0; i < 10; ++i){number[index + 1] = i + '0';Print1ToMaxOfNDigitsRecursively(number, length, index + 1);}
}// ====================公共函数====================
// 字符串number表示一个数字，数字有若干个0开头
// 打印出这个数字，并忽略开头的0
void PrintNumber(char* number)
{bool isBeginning0 = true;int nLength = strlen(number);for (int i = 0; i < nLength; ++i){if (isBeginning0 && number[i] != '0')isBeginning0 = false;if (!isBeginning0){printf("%c", number[i]);}}printf("\t");
}