C++의 덧셈 숫자

'0'부터 '9'까지의 숫자만 포함하는 문자열이 있다고 가정하면, 덧셈 숫자인지 여부를 판별하는 함수를 작성해야 합니다. 추가 번호는 숫자가 추가 시퀀스를 형성할 수 있는 문자열입니다. 유효한 덧셈 시퀀스에는 최소 3개의 숫자가 포함되어야 합니다. 여기에서 처음 두 숫자를 제외하고 시퀀스의 각 후속 숫자는 앞의 두 숫자의 합이어야 합니다. 따라서 입력이 "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 :=하나의 빈 문자열
for i in range index to s
- x :=x + s[i]
- x =num이고 ok(s, i + 1, prev2, x가 정수)인 경우 true를 반환합니다.
거짓을 반환
주요 방법에서 다음을 수행하십시오 -
n :=숫자 크기
범위 1에서 n – 2의 i에 대해
- 범위 1에서 i까지의 j에 대해
  - s1 :=0에서 j까지 num의 부분 문자열 – 1
  - s2 :=j에서 i까지 num의 부분 문자열 – j
  - x :=s1 크기와 s2 크기의 최대값
  - x> n – i이면 다음 반복으로 이동합니다.
  - (s1[0]이 0이고 크기가 s1> 0인 경우) 또는 (s2[0]이 0이고 크기가 s2> 1인 경우) 다음 반복으로 건너뜁니다.
  - ok(num, i + 1, s1은 정수, s2는 정수)가 true이면 true를 반환합니다.
거짓을 반환

예시(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++)

입력

출력