題目：打印從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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。