C ++中的加数

假设我们有一个仅包含从'0'到'9'的数字的字符串，我们必须编写一个函数来确定它是否为加数。加号是一个字符串，其数字可以形成加号序列。有效的加法序列应至少包含三个数字。在此，除了前两个数字外，序列中的每个后续数字都必须是前两个数字的和。因此，如果输入类似于“ 112358”，则答案将是正确的，因为2 = 1 + 1、3 = 1 + 2、5 = 2 + 3、8 = 3 + 5。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个名为的方法ok()，它将采用s，index，prev1，prev2

• 如果索引> = s的大小，则返回true

• req：= prev1 + prev2和num：= req作为字符串

• x：=一个空白字符串

• 对于i在s大小的范围索引中

• x：= x + s [i]

• 如果x = num，并且ok（s，i + 1，prev2，x为整数），则返回true

• 返回假

• 从主要方法中执行以下操作-

• n：= num的大小

• 当我在1到n – 2的范围内时

• s1：= num的子串，从0到j – 1

• s2：=从j到i – num的子字符串

• x：= s1大小和s2大小的最大值

• 如果x> n – i，则进行下一次迭代

• 如果（s1 [0]为0且s1的大小> 0）或（s2 [0]为0且s2的大小> 1），则跳至下一个迭代

• 如果ok（num，i + 1，s1为整数，s2为整数）为true，则返回true

• 对于1到i范围内的j

• 返回假

例子（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