C++ 中的加法数
c++server side programmingprogramming更新于 2024/9/1 7:18:00
假设我们有一个仅包含"0"到"9"数字的字符串，我们必须编写一个函数来确定它是否是加法数。加法数是一个数字可以形成加法序列的字符串。有效的加法序列应至少包含三个数字。这里，除了前两个数字外，序列中每个后续数字都必须是前两个数字的总和。因此，如果输入类似于"112358"，则答案将为真，因为 2 = 1 + 1、3 = 1 + 2、5 = 2 + 3、8 = 3 + 5。
为了解决这个问题，我们将遵循以下步骤 −
定义一个名为 ok() 的方法，它将采用 s、index、prev1、prev2
如果 index >= size of s，则返回 true
req := prev1 + prev2 and num := req as string
x := one blank string
for i in range index to size of 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) OR (s2[0] 为 0 且 s2 的大小 > 1)，则跳至下一次迭代
如果 ok(num, i + 1, s1 为整数且 s2 为整数) 为 true，则返回 true
return 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
