如何查询网站打开速度,wordpress微信文章,镇江市住房城乡建设局网站,淘客网站怎么做首页记录来自《剑指offer》上的算法题。
题目如下#xff1a; 输入数字n#xff0c;按顺序打印出从1到最大的n位十进制数。比如输入3#xff0c;则打印出1#xff0c;2#xff0c;3一直到最大的3位数即999。 第一种解法是比较容易想到#xff0c;但是遇到大数问题的时候会有…记录来自《剑指offer》上的算法题。
题目如下 输入数字n按顺序打印出从1到最大的n位十进制数。比如输入3则打印出123一直到最大的3位数即999。 第一种解法是比较容易想到但是遇到大数问题的时候会有溢出的问题其代码如下
// 简单的解法但遇到输入值很大时会出现问题
void Print1ToMaxOfNDigits_1(int n){int number 1;int i 0;while (i n)number * 10;for (i 1; i number; i)cout i ;cout endl;
}
所以这里需要表达一个大数。最常用也是最容易的方法是用字符串或数组表达大数。下面使用字符串来表达大数。解法代码如下
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;
}
// 打印用字符串表示的数字
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_str(int n){if (n 0)return;// 初始化为0char *numbers new char[n 1];memset(numbers, 0, n);numbers[n] \0;while (!Increment(numbers)){PrintNumber(numbers);}delete[] numbers;
}
// 测试
int main(void){int t[] { 0, 1, 3, -1 };for (int i 0; i 4; i){cout test num t[i] : \n;Print1ToMaxOfNDigits_str(t[i]);cout endl;}system(pause);return 0;
}
这种解法中函数Increment()实现在表示数字的字符串numbers上增加1并判断是否出现溢出问题也就是是否达到最大的n位数而PrintNumber()函数则是打印出numbers。
其中在函数Increment()中每次增加1后快速判断是否到了最大的n位数的办法是判断第一个字符是否产生了进位因为只有达到最大的n位数的情况才会对第一个字符下标是0进行进位如n3只有对999再加1才会对第一个字符进行进位在函数中的体现就是在如下代码:
if (nSum 10){if (i 0)isOverflow true;....
}
这种解法思路比较直观但是由于模拟了整数的加法代码有点长下面换另一种思路。如果我们在数字面前补0可以发现n位所有十进制数其实就是n个从0到9的全排列。也就是说我们把数字的每一位都从0到9排列一遍就可以得到所有的十进制数。
全排列用递归很容易表达数字的每一位都是0到9中的一位然后设置下一个数。递归结束的条件是已经设置了数字的最后一位。代码如下
// 递归方法
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);}
}
// 利用字符串来表达大数
void Print1ToMaxOfNDigits_str(int n){if (n 0)return;// 初始化为0char *numbers new char[n 1];//memset(numbers, 0, n);numbers[n] \0;/*while (!Increment(numbers)){PrintNumber(numbers);}*/for (int i 0; i 10; i){numbers[0] i 0;Print1ToMaxOfNDigitsRecursively(numbers, n, 0);}delete[] numbers;
}
上述代码中注释掉的是第二种解法中的代码然后增加适用于递归方法的代码。
更完整例子看出我的Github。
