首先這道題一定要考慮大數溢位的情況，那么你就需要用到一個字串操作了，
而對于字串你每次都要++，這么一直玩下去列印下去，字串的進位并不是那么的容易，而且對于不知道幾位的抽象寫法也不好實作，
而對于這種每一個數字都會有的情況，其實就是數字的全排列情況，數字的全排列不就是嘗試遞回玩法么！
所以說這道題就是玩dfs遞回，然后形成有序的全排列！
而對于結果有幾個注意的點，人家要求的是列印1，你可能給他干成00001的字串，還有人家是從1開始，你會整出來一個00000
針對這兩個問題，對于c++語言內部的介面可以處理，前者直接把字串搞成數字，后者直接在最后確定這個數的時候判斷是否為0就行了，也只是針對這道題AC了，
但是這并沒有從根本上解決問題，如果題目要求輸出字串集合呢？
class Solution {
public:
vector<int> output;
vector<int> printNumbers(int n) {
// 以下注釋的前提：假設 n = 3
if(n <= 0) return vector<int>(0);
string s(n, '0'); // s最大會等于999，即s的長度為n
while(!overflow(s)) inputNumbers(s);
return output;
}
bool overflow(string& s)
{
// 本函式用于模擬數字的累加程序，并判斷是否越界（即 999 + 1 = 1000，就是越界情況）
bool isOverFlow = false;
int carry = 0; // carry表示進位
for(int i=s.length()-1; i>=0; --i)
{
int current = s[i] - '0' + carry; // current表示當前這次的操作，s[i] - '0'是的s[i]的值，直接轉int是會得到ASCII碼的
if(i == s.length() - 1) current ++; // 如果i此時在個位，current執行 +1 操作
if(current >= 10)
{
// 假如i已經在最大的那一位了，而current++之后>=10，說明回圈到頭了，即999 + 1 = 1000
if(i == 0) isOverFlow = true;
else
{
// 只是普通進位，比如current從9變成10
carry = 1;
s[i] = current - 10 + '0';
}
}
else
{
// 如果沒有進位，更新s[i]的值，然后直接跳出回圈，這樣就可以回去執行inputNumbers函式了，即往output里添加元素
s[i] = current + '0';
break;
}
}
return isOverFlow;
}
void inputNumbers(string s)
{
// 本函式用于回圈往output中添加符合傳統閱讀習慣的元素，比如001，我們會添加1而不是001，
bool isUnwantedZero = true; // 判斷是否是不需要添加的0，比如001前面的兩個0
string temp = "";
for(int i=0; i<s.length(); ++i)
{
if(isUnwantedZero && s[i] != '0') isUnwantedZero = false;
if(!isUnwantedZero) temp += s[i];
}
output.push_back(stoi(temp));
}
};
上邊這個只是加1，對于兩個大整數相加的玩法下面：
(73條訊息) 面試演算法題(2)--兩個大數相加_阿杜的博客-CSDN博客_大數相加
(73條訊息) 怎樣實作大整數相加？_allyyhh的博客-CSDN博客_大整數加法
最后還有一種思路就是，對于它每次加1，就是對于這些數字的全排列
class Solution {
public:
void dfs (vector<int>& v, int n,int deep, string& ans){
if(deep == n){
if(atoi(ans.c_str()) == 0)return;
v.push_back(atoi(ans.c_str()));
return;
}
string s = "0123456789";
for(int i = 0; i < 10; i++){
ans[deep] = s[i];
dfs(v, n, deep + 1, ans);
}
}
vector<int> printNumbers(int n) {
vector<int> v;
string ans(10, 0);
dfs(v, n, 0, ans);
//v.erase(v.begin(), v.begin() + 1);
return v;
}
};轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/387268.html
標籤：區塊鏈