NC381. 累加序列
描述
示例1
输入:
"12358"
输出:
true
说明:
1+2=3 2+3=5 3+5=8示例2
输入:
"19101929"
输出:
true
说明:
1+9=10 9+10=19 10+19=29示例3
输入:
"191011"
输出:
false
C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-08-02
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param arr string字符串
* @return bool布尔型
*/
typedef long long LL;
bool AdditiveArray(string arr) {
// write code here
int n = arr.size();
for (int i = 0; i < 10 && i <= n / 3; i ++)
{
LL a = stoll(arr.substr(0, i + 1));
for (int j = i + 1; j < i + 10 && j < n / 3 * 2; j ++)
{
if (arr[j] == '0') break;
int b = stoll(arr.substr(i + 1, j - i));
if (dfs(arr, a, b, j + 1)) return true;
}
}
return false;
}
bool dfs(string &s, LL a, LL b, int idx) {
int n = s.size();
//cout << a << " --- " << b << endl;
if (idx >= n) return true;
if(s[idx] == '0') return false;
for (int i = idx; i < n && i < idx + 10; i ++) {
LL c = stoll(s.substr(idx, i - idx + 1));
if (a + b == c) {
//cout << a << " " << b << " " << c << endl;
return dfs(s, b, c, i + 1);
}
}
return false;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 396KB, 提交时间: 2022-08-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param arr string字符串
* @return bool布尔型
*/
typedef long long LL;
bool AdditiveArray(string arr) {
// write code here
int n=arr.size();
for(int i=0;i<10&&i<=n/3;i++)
{
LL a=stoll(arr.substr(0,i+1));
for(int j=i+1;j<i+10&&j<n/3*2;j++)
{
if(arr[j]=='0')
break;
int b=stoll(arr.substr(i+1,j-i));
if(dfs(arr,a,b,j+1))
return true;
}
}
return false;
}
bool dfs(string &s,LL a,LL b,int idx)
{
int n=s.size();
if(idx>=n)
return true;
if(s[idx]=='0')
return false;
for(int i=idx;i<n&&i<idx+10;i++)
{
LL c=stoll(s.substr(idx,i-idx+1));
if(a+b==c)
{
return dfs(s,b,c,i+1);
}
}
return false;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-07-17
class Solution {
public:
bool AdditiveArray(string arr) {
int h = arr.size();
for (int i = 1; i < h - 1; ++i) {
string x = arr.substr(0, i);
if (x.size() > 1 && x[0] == '0') {
break;
}
for (int j = i; j < h - 1; ++j) {
string y = arr.substr(i, j - i + 1);
if (y.size() > 1 && y[0] == '0') {
break;
}
if (dfs(arr.substr(j + 1), x, y)) {
return true;
}
}
}
return false;
}
private:
bool dfs(string arr, string num1, string num2) {
string c = add(num1, num2);
if (c == arr) {
return true;
}
if (c.size() >= arr.size() || arr.substr(0, c.size()) != c) {
return false;
}
return dfs(arr.substr(c.size()), num2, c);
}
string add(string num1, string num2) {
string z;
int i = (int)num1.size() - 1;
int j = (int)num2.size() - 1;
int f = 0;
while (i >= 0 || j >= 0) {
int m = (i >= 0) ? (num1[i--] - '0') : 0;
int n = (j >= 0) ? (num2[j--] - '0') : 0;
int sum = m + n + f;
z.push_back(sum % 10 + '0');
f = sum / 10;
}
if (f) {
z.push_back(f + '0');
}
reverse(z.begin(), z.end());
return z;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 512KB, 提交时间: 2022-06-29
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param arr string字符串
* @return bool布尔型
*/
bool AdditiveArray(string arr) {
// write code here
int n = arr.size();
for (int i = 1; i < n - 1; ++i) {
string s1 = arr.substr(0, i);
if (s1.size() > 1 && s1[0] == '0') {
break;
}
for (int j = i; j < n - 1; ++j) {
string s2 = arr.substr(i, j - i + 1);
if (s2.size() > 1 && s2[0] == '0') {
break;
}
if (dfs(arr.substr(j + 1), s1, s2)) {
return true;
}
}
}
return false;
}
private:
bool dfs(string arr, string num1, string num2) {
string sumStr = add(num1, num2);
if (sumStr == arr) {
return true;
}
if (sumStr.size() >= arr.size() || arr.substr(0, sumStr.size()) != sumStr) {
return false;
}
return dfs(arr.substr(sumStr.size()), num2, sumStr);
}
string add(string num1, string num2) {
string res;
int i = (int)num1.size() - 1;
int j = (int)num2.size() - 1;
int carry = 0;
while (i >= 0 || j >= 0) {
int val1 = (i >= 0) ? (num1[i--] - '0') : 0;
int val2 = (j >= 0) ? (num2[j--] - '0') : 0;
int sum = val1 + val2 + carry;
res.push_back(sum % 10 + '0');
carry = sum / 10;
}
if (carry) {
res.push_back(carry + '0');
}
reverse(res.begin(), res.end());
return res;
}
};
C 解法, 执行用时: 5ms, 内存消耗: 400KB, 提交时间: 2022-06-27
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param arr string字符串
* @return bool布尔型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
#include <stdio.h>
#include <stdbool.h>
static char tmpResult[100] = "";
int strToInt(char *str, int len) {
int sLen = strlen(str);
int sum = 0;
if (len > sLen) {
len = sLen;
}
for (int i = 0; i < len; i++) {
sum = sum * 10 + str[i] - '0';
}
return sum;
}
char *intToStr(int val) {
int v = val, index = 0;
while(v > 0) {
tmpResult[index++] = v % 10 + '0';
v = v / 10;
}
tmpResult[index] = '\0';
int halfLen = index / 2;
char tmp;
for (int i = 0; i < halfLen; i++) {
tmp = tmpResult[i];
tmpResult[i] = tmpResult[index - 1 - i];
tmpResult[index - 1 - i] = tmp;
}
return tmpResult;
}
bool hasPrefix(char *str, char *pre) {
int sLen = strlen(str), preLen = strlen(pre);
if (sLen < preLen) {
return false;
}
for (int i = 0; i < preLen; i++) {
if (str[i] != pre[i]) {
return false;
}
}
return true;
}
bool checkValid(char *str, int first, int sLen) {
if (str[0] == '0') {
return false;
}
int second = 0, result = 0, tmp, strResultLen = 0, remainLen, nextStartIndex;
char *strResult;
for (int i = 0; i < sLen - 1; i++) {
second = strToInt(str, i+1);
result = first + second;
remainLen = sLen - i - 1;
nextStartIndex = i+1;
while(remainLen > 0) {
strResult = intToStr(result);
strResultLen = strlen(strResult);
if (hasPrefix(str+nextStartIndex, strResult)) {
if (strResultLen == remainLen) {
return true;
} else {
tmp = result;
result = second + result;
second = tmp;
remainLen = remainLen - strResultLen;
nextStartIndex += strResultLen;
}
} else {
break;
}
}
}
return false;
}
bool AdditiveArray(char* arr ) {
int sLen = strlen(arr);
for (int i = 0; i < sLen - 2; i++) {
int first = strToInt(arr, i + 1);
if (checkValid(arr + i + 1, first, sLen - i - 1)) {
return true;
}
}
return false;
}