資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++中的加法數
假設我們有一個只包含'0'到'9'數字的字串，我們需要編寫一個函式來判斷它是否為加法數。加法數是一個其數字可以構成加法序列的字串。有效的加法序列至少包含三個數字。除了前兩個數字外，序列中的每個後續數字都必須是前面兩個數字的和。例如，如果輸入是“112358”，則答案為真，因為2 = 1 + 1，3 = 1 + 2，5 = 2 + 3，8 = 3 + 5。
為了解決這個問題，我們將遵循以下步驟：
定義一個名為ok()的方法，它將接收s、index、prev1、prev2作為引數。
如果index >= s的大小，則返回true。
req := prev1 + prev2 並且 num := req 作為字串。
x := 一個空字串。
對於i的範圍從index到s的大小
x := x + s[i]
如果x = num，並且ok(s, i + 1, prev2, x作為整數)為真，則返回true。
返回false。
在主方法中執行以下操作：
n := num的大小。
對於i的範圍從1到n – 2
對於j的範圍從1到i
s1 := num從0到j – 1的子字串。
s2 := num從j到i – j的子字串。
x := s1大小和s2大小的最大值。
如果x > n – i，則進入下一個迭代。
如果(s1[0]為0且s1的大小> 0) 或 (s2[0]為0且s2的大小> 1)，則跳到下一個迭代。
如果ok(num, i + 1, s1作為整數和s2作為整數)為真，則返回true。
返回false。
示例(C++)
讓我們看下面的實現來更好地理解：
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
bool ok(string s, int idx, lli prev1, lli prev2){
if(idx >= s.size()) return true;
lli req = prev1 + prev2;
string num = to_string(req);
string x = "";
for(int i = idx; i < s.size(); i++){
x += s[i];
if(x == num && ok(s, i + 1, prev2, stol(x))) return true;
}
return false;
}
bool isAdditiveNumber(string num) {
int n = num.size();
for(int i = 1; i < n - 1; i++){
for(int j = 1; j <= i; j++){
string s1 = num.substr(0, j);
string s2 = num.substr(j, i - j + 1);
int x = max((int)s1.size(), (int)s2.size());
if(x > n - i) continue;
if((s1[0] == '0' && s1.size() > 1) || (s2[0] == '0' && s2.size() > 1)) continue;
if(ok(num, i + 1, stol(s1), stol(s2))) return true;
}
}
return false;
}
};
main(){
Solution ob;
cout << (ob.isAdditiveNumber("112358"));
}輸入
"112358"
輸出
1
更新於：2020年5月2日
511 次瀏覽
廣告