剑指offer--面试题12

题目：打印从1~最大的n位数

分析：知道陷阱在哪，即n很大时若用通常的int,long会溢出；想到用字符串解决，这涉及到字符转数字及反过来。

　　刚开始纠结于字符串怎么加1，想了片刻，觉得应该取出最后一位上的字符，转成数字+1再转成字符，但这就出现个问题：'9'加1后得到'10'，这会产生进位。。。

　　到这思维就乱了。。。1、不断向前进位怎么解决？2、怎么判断到达最大值？

 

在看过作者的代码后才豁然开朗。。。，解决方案：1、将进位与不进位分开，并且进位时设定nTakeOver用于下一字符的加，该过程用循环完成；2、同样判断最大值时，若第一位的数值=10了，那肯定已经到达最大值了

结合参考代码，自己所写代码如下：

#include "stdafx.h" #include <iostream>using namespace std;void PrintNumber(char* number); //打印数字 bool Increment(char* number,int length); //加1// ====================方法一==================== void Print1ToMaxOfNDigits_1(int n) {if(n <= 0)return; //错误处理char *number = new char[n + 1];memset(number, '0', n); //memset()函数设置number的前n位为字符‘0’:memset(number,'0',n); 该函数位于<memory>number[n] = '\0'; //注意字符串以‘/0’结尾！！！while(!Increment(number,n)){PrintNumber(number);} //加1成功则打印delete [] number; }//实现加1操作 //一直到某位上的数值不超过9，终止循环 //利用循环向前进位 bool Increment(char* number, int length) {bool isOverFlow = false;int nTakeOver = 0;for(int i=length-1; i>=0; i--){//加1,要考虑之前的进位nTakeOverint num_value = number[i] - '0' + nTakeOver;if(i == length-1)num_value += 1;if(num_value <= 9){number[i] = num_value + '0';break;}else{//达到最大n位数后终止if(i == 0)isOverFlow = true;else{nTakeOver = 1;number[i] = num_value - 10 + '0';}}}return isOverFlow; }//打印字符串表示的数字 void PrintNumber(char* number) {while(*number != '\0'){if(*number == '0')number++;else{cout<<number<<'\t';break;}} }// ====================测试代码==================== void Test(int n) {printf("Test for %d begins:\n", n);Print1ToMaxOfNDigits_1(n);printf("Test for %d ends.\n", n); }int main() {Test(1);Test(2);Test(3);Test(0);Test(-1);return 0; }

说明：只是在PrintNumber子函数上做了些改进。

 

另一种思路：因为每位为0~9，共n位，所以数字个数=10^n-1，因此相当于全排列的方法，而全排列可用递归实现！

这种方法由于涉及到递归，所以自己很难想到，即便想到也很难写出来。。。

参考代码如下：

// ====================方法二==================== 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);} }

简单明了！！！

PS：对全排列的递归实现，值得关注与记忆！！！

 

转载于:https://www.cnblogs.com/hello-yz/p/3251011.html

总结

以上是生活随笔为你收集整理的剑指offer--面试题12的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。