做网站多少钱一个月,windows优化大师如何卸载,网站制,新竹自助建站系统剑指 Offer#xff08;第2版#xff09;面试题 17#xff1a;打印从 1 到最大的 n 位数 剑指 Offer#xff08;第2版#xff09;面试题 17#xff1a;打印从 1 到最大的 n 位数解法1#xff1a;字符数组解法2#xff1a;全排列 剑指 Offer#xff08;第2版#xff09… 剑指 Offer第2版面试题 17打印从 1 到最大的 n 位数 剑指 Offer第2版面试题 17打印从 1 到最大的 n 位数解法1字符数组解法2全排列 剑指 Offer第2版面试题 17打印从 1 到最大的 n 位数
题目描述
输入数字n按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3则打印出 123 一直到最大的 3 位 999。
首先想到的是 for 循环挨个输出但是这样的话会有 n 过大位数过高而造成溢出的情况。
解法1字符数组
我们使用字符串来模拟数字这样的话不管多少位我们都可以解决
构造字符数组先构造一个 n 位每一位都为 ‘0’ 的数组每次最后一位 1重复这一过程到溢出为此如 2 位加到 100 就会溢出因此输出 1 ~ 99
输出前面有 ‘0’ 的话不输出如 “001”应输出 “1”
代码
#include iostream
#include string.h
using namespace std;void print_number(int number);
void print_arr(char *arr);
bool over(char *arr);int main()
{print_number(2);system(pause);return 0;
}void print_number(int number)
{char *arr new char[number 1];memset(arr, 0, number);arr[number] \0;while (!over(arr)){print_arr(arr);}
}void print_arr(char *arr)
{ // 输出字符数组第一个为0的话不输出bool start false;int count 0;while (!start){if (arr[count] ! 0)start true;count;}for (int i count - 1; i strlen(arr); i)cout arr[i];cout \t;
}bool over(char *arr)
{ // 数字加1操作arr[strlen(arr) - 1];int tmp 0;for (int i strlen(arr) - 1; i 0; i--){ // 进1相加arr[i] tmp;if (arr[i] - 0 9){arr[i] 0;tmp 1;}else{tmp 0;}}if (arr[0] 0 tmp 1)return true; // 判断溢出return false;
}复杂度分析
时间复杂度O(2n-1)。
空间复杂度O(n)用到了一个长度为 n1 的字符数组。
解法2全排列
同样基于字符数组每一位的数字都是从0 ~9 之间不断变化因此其是一个排列的问题我们可以使用递归实现数组的排列输出的规则同解法 1。
代码
#include iostream
#include string.h
using namespace std;void print_number(int number);
void print_arr(char *arr);
void permutation(char *arr, int index);int main()
{print_number(2);system(pause);return 0;
}void print_number(int number)
{char *arr new char[number 1];memset(arr, 0, number);arr[number] \0;for (int i 0; i 10; i){arr[0] i 0;permutation(arr, 0);}
}
void permutation(char *arr, int index)
{ // 先递归凑足n位然后排列输出if (index strlen(arr) - 1){print_arr(arr);return;}for (int i 0; i 10; i){arr[index 1] i 0;permutation(arr, index 1);}
}
void print_arr(char *arr)
{ // 输出字符数组第一个为0的话不输出bool start false;int count 0;while (!start){if (arr[count] ! 0)start true;count;}for (int i count - 1; i strlen(arr); i)cout arr[i];cout \t;
}复杂度分析
时间复杂度O(2n-1)。
空间复杂度O(n)递归的深度为 n。
