C ++中的加数

2024-04-21 08:44:05 350

假设我们有一个仅包含从'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"

输出结果

C ++中的加数

例子（C++）

输入项

热门推荐

随机推荐