数据结构
网络
关系数据库管理系统 (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 次浏览
广告