当前位置:网站首页>【LeetCode】306.累加数(思路+题解)

【LeetCode】306.累加数(思路+题解)

2022-08-11 05:33:00 sakamotoen

【LeetCode】306.累加数(思路+题解)

记录个人解题思路与代码,欢迎和谐讨论


一、题目

累加数 是一个字符串,组成它的数字可以形成累加序列。

一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。

给你一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是 累加数 。如果是,返回 true ;否则,返回 false

说明:累加序列里的数 不会 以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

来源:力扣(LeetCode)
链接:源力扣地址

示例 1:

输入:“112358”
输出:true
解释:累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2:

输入:“199100199”
输出:true
解释:累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

提示:

1 <= num.length <= 35
num 仅由数字(0 - 9)组成

二、思路

这道题的解法是经典的回溯算法,回溯算法类似与枚举的搜索尝试,主要是在搜索尝试中寻找问题的解。在本题中,我们设两个待加数字为a与b,结果为c,那么在此问题中搜索即是搜索a与b,尝试判断其是否等于c。在提示中题目强调了num字符串的最长长度为35,那么就意味着可以出现长度为17的数字,其大小远大于int类型支持的位数,因此在算法中采用 long long int类型来保存过程中出现的数字。

除此之外,在问题中强调不会出现以0开头的数字,那么就要求在此之中必须能够判断字符串转出来的数字是否合法。由于在问题中可以看出不会出现复数,那么我们可以通过编写一个字符串转long long int 的函数顺便判断了这个数字是否合法,非法则返回-1.

随后在判断中,如遇到a+b>c的情况,可能是由于进位产生的,因此我们再给c补一位再重新判断是否相等,若a+b<c则显然是出现了搜索错误,因此直接将b的长度++进行新一轮搜索即可。

最后看看效果:
在这里插入图片描述

三、代码

代码如下:

class Solution {
    
private:
    long long int getNum(const string num, int pos, int len) {
          //字符串转ll数字,如果非法返回-1;
        if (pos != 0 and len != 1 and num[pos] == '0')
            return -1;
        return stoll(num.substr(pos, len), NULL, 10);
    }
public:
    bool isAdditiveNumber(string num) {
    
        if (num.size() < 3)    return 0;
        int a_len = 1;
        bool a_f = true;
        while (a_len <= floor(num.size() / 2) and a_f) {
    
            int a_pos = 0;
            int b_pos = a_pos + a_len;
            int b_len = 1;
            bool b_f = true;
            while (b_len <= floor((num.size() - a_len) / 2) and a_f and b_f) {
    
                int c_pos = b_pos + b_len;
                int c_len = max(a_len, b_len);
				bool c_f = true;
                long long int a = getNum(num, a_pos, a_len);
                if (a == -1) {
    
                    a_f = false;
                    break;
                }
                long long int b = getNum(num, b_pos, b_len);
                if (b == -1) {
    
                    b_f = false;
                    break;
                }
                int a_len_temp = a_len;
                int b_len_temp = b_len;
				while (c_pos + c_len <= num.size()) {
    
					if (c_len > (max(a_len_temp, b_len_temp) + 1) and c_f) 
						break;
					long long int c = getNum(num, c_pos, c_len);
					if (c == -1) {
    
						c_f = false;
						break;
					}
					if (a + b == c) {
    
                        a = b;
                        b = c;
                        a_len_temp = b_len_temp;
                        b_len_temp = c_len;
                        c_pos = c_pos + c_len;
					}
                    else if (a + b > c) 
                        ++c_len;
                    else if (a + b < c) 
                        break;
                    if (c_pos == num.size())
                        return 1;
				}
                ++b_len;
            }
            ++a_len;
        }
        return 0;
    }
};

原网站

版权声明
本文为[sakamotoen]所创,转载请带上原文链接,感谢
https://blog.csdn.net/Jicky233/article/details/122419279