累加数

306. 累加数

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

一个有效的 累加序列 必须至少包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。

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

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

示例 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）组成

进阶：你计划如何处理由过大的整数输入导致的溢出?

相似题目

将数组拆分成斐波那契序列

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool isAdditiveNumber(string num) { } };

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-12 10:05:02

func add(a, b string) string {
    res, one := []byte{}, 0
    for i, j := len(a) - 1, len(b) - 1 ; i >= 0 || j >= 0 ; {
        curA, curB := 0, 0
        if i >= 0 {
            curA = int(a[i] - '0')
            i--
        }
        if j >= 0 {
            curB = int(b[j] - '0')
            j--
        }
        cur := curA + curB + one
        one = cur/10
        res = append(res, byte(cur%10)+'0')
    }
    if one == 1 {
        res = append(res, '1')
    }
    for i, n := 0, len(res); i < n/2; i++ {
        res[i], res[n-1-i] = res[n-1-i], res[i]
    }
    return string(res)
}

func dfs(num string, first, second int) bool {
    n, last := len(num), 0
    for second < n {
        if (num[last] == '0' && first > last + 1) || (num[first] == '0' && second > first + 1){
            return false
        }
        s := add(num[last:first], num[first:second])
        if second + len(s) > n || num[second:second + len(s)] != s {
            return false
        }
        last, first, second = first, second, second + len(s)
    }
    return true
}

func isAdditiveNumber(num string) bool {
    for i:=1;i<len(num)-1;i++ {
        for j:=i+1;j<len(num);j++{
            if dfs(num, i, j){
                return true
            }
        }
    }
    return false
}

javascript 解法, 执行用时: 80 ms, 内存消耗: 42.3 MB, 提交时间: 2023-06-12 10:04:48

/**
 * @param {string} num
 * @return {boolean}
 */
var isAdditiveNumber = function(num) {
    add = function(a, b){
        const res = new Array()
        let one = 0
        for(let i=a.length-1,j=b.length-1;i>=0||j>=0;){
            let curA = 0, curB = 0
            if(i >= 0)
                curA = a.charCodeAt(i--) - '0'.charCodeAt(0)
            if(j >= 0)
                curB = b.charCodeAt(j--) - '0'.charCodeAt(0)
            const cur = curA + curB + one
            one = cur >= 10 ? 1 : 0
            res.push(String.fromCodePoint(cur % 10 + '0'.charCodeAt(0)))
        }
        if(one == 1)
            res.push('1')
        return res.reverse().join('')
    }

    dfs = function(i, j){
        let last = 0, first = i, second = j;
        while(second < num.length){
            if((num.charAt(last) == '0' && first > last + 1) || (num.charAt(first) == '0' && second > first + 1))
                return false
            const s = add(num.substring(last, first), num.substring(first, second));
            if(second + s.length > num.length || !(s === num.substring(second, second + s.length)))
                return false
            last = first
            first = second
            second += s.length
            console.log(last, first, second)
        }
        return true
    }

    for(let i=1;i<num.length-1;i++)
        for(let j=i+1;j<num.length;j++)
            if(dfs(i, j))
                return true
    return false
};

java 解法, 执行用时: 0 ms, 内存消耗: 39.1 MB, 提交时间: 2023-06-12 10:04:31

class Solution {
    public boolean isAdditiveNumber(String num) {
        for(int i=1;i<num.length()-1;i++)
            for(int j=i+1;j<num.length();j++)
                if(dfs(i, j, num))
                    return true;
        return false;
    }

    private String add(String a, String b){
        StringBuilder sb = new StringBuilder();
        int one = 0;
        for(int i=a.length()-1,j=b.length()-1;i>=0||j>=0;){
            int curA = 0, curB = 0;
            if(i >= 0)
                curA = a.charAt(i--) - '0';
            if(j >= 0)
                curB = b.charAt(j--) - '0';
            int cur = curA + curB + one;
            one = cur >= 10 ? 1 : 0;
            sb.append((char)('0' + cur%10));
        }
        if(one == 1)
            sb.append('1');
        return sb.reverse().toString();
    }

    private boolean dfs(int i, int j, String num){
        int last = 0, first = i, second = j;
        while(second < num.length()){
            if((num.charAt(last) == '0' && first > last + 1) || (num.charAt(first) == '0' && second > first + 1))
                return false;
            String s = add(num.substring(last, first), num.substring(first, second));
            if(second + s.length() > num.length() || !s.equals(num.substring(second, second + s.length())))
                return false;
            last = first;
            first = second;
            second += s.length();
        }
        return true;
    }
}

python3 解法, 执行用时: 36 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-12 10:04:01

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        for i in range(1, len(num) - 1):
            for j in range(i + 1, len(num)):
                last, first, second = 0, i, j
                while second < len(num):
                    if (num[last] == '0' and first > last + 1) or (num[first] == '0' and second > first + 1) or len(num) - second < second - first:
                        break
                    s = str(int(num[last:first]) + int(num[first:second]))
                    if s != num[second:second+len(s)]:
                        break
                    last, first, second = first, second, second + len(s)
                else:
                    return True
        return False

javascript 解法, 执行用时: 52 ms, 内存消耗: 42 MB, 提交时间: 2023-06-12 10:03:17

/**
 * @param {string} num
 * @return {boolean}
 */
var isAdditiveNumber = function(num) {
    const n = num.length;
    for (let secondStart = 1; secondStart < n - 1; ++secondStart) {
        if (num[0] === '0' && secondStart !== 1) {
            break;
        }
        for (let secondEnd = secondStart; secondEnd < n - 1; ++secondEnd) {
            if (num[secondStart] === '0' && secondStart !== secondEnd) {
                break;
            }
            if (valid(secondStart, secondEnd, num)) {
                return true;
            }
        }
    }
    return false;
};

const valid = (secondStart, secondEnd, num) => {
    const n = num.length;
    let firstStart = 0, firstEnd = secondStart - 1;
    while (secondEnd <= n - 1) {
        const third = stringAdd(num, firstStart, firstEnd, secondStart, secondEnd);
        const thirdStart = secondEnd + 1;
        const thirdEnd = secondEnd + third.length;
        if (thirdEnd >= n || num.slice(thirdStart, thirdEnd + 1) !== third) {
            break;
        }
        if (thirdEnd === n - 1) {
            return true;
        }
        firstStart = secondStart;
        firstEnd = secondEnd;
        secondStart = thirdStart;
        secondEnd = thirdEnd;
    }
    return false;
}

const stringAdd = (s, firstStart, firstEnd, secondStart, secondEnd) => {
    const third = [];
    let carry = 0, cur = 0;
    while (firstEnd >= firstStart || secondEnd >= secondStart || carry !== 0) {
        cur = carry;
        if (firstEnd >= firstStart) {
            cur += s[firstEnd].charCodeAt() - '0'.charCodeAt();
            --firstEnd;
        }
        if (secondEnd >= secondStart) {
            cur += s[secondEnd].charCodeAt() - '0'.charCodeAt();
            --secondEnd;
        }
        carry = Math.floor(cur / 10);
        cur %= 10;
        third.push(String.fromCharCode(cur + '0'.charCodeAt()));
    }
    third.reverse();
    return third.join('');
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-12 10:02:43

func stringAdd(x, y string) string {
    res := []byte{}
    carry, cur := 0, 0
    for x != "" || y != "" || carry != 0 {
        cur = carry
        if x != "" {
            cur += int(x[len(x)-1] - '0')
            x = x[:len(x)-1]
        }
        if y != "" {
            cur += int(y[len(y)-1] - '0')
            y = y[:len(y)-1]
        }
        carry = cur / 10
        cur %= 10
        res = append(res, byte(cur)+'0')
    }
    for i, n := 0, len(res); i < n/2; i++ {
        res[i], res[n-1-i] = res[n-1-i], res[i]
    }
    return string(res)
}

func valid(num string, secondStart, secondEnd int) bool {
    n := len(num)
    firstStart, firstEnd := 0, secondStart-1
    for secondEnd <= n-1 {
        third := stringAdd(num[firstStart:firstEnd+1], num[secondStart:secondEnd+1])
        thirdStart := secondEnd + 1
        thirdEnd := secondEnd + len(third)
        if thirdEnd >= n || num[thirdStart:thirdEnd+1] != third {
            break
        }
        if thirdEnd == n-1 {
            return true
        }
        firstStart, firstEnd = secondStart, secondEnd
        secondStart, secondEnd = thirdStart, thirdEnd
    }
    return false
}

func isAdditiveNumber(num string) bool {
    n := len(num)
    for secondStart := 1; secondStart < n-1; secondStart++ {
        if num[0] == '0' && secondStart != 1 {
            break
        }
        for secondEnd := secondStart; secondEnd < n-1; secondEnd++ {
            if num[secondStart] == '0' && secondStart != secondEnd {
                break
            }
            if valid(num, secondStart, secondEnd) {
                return true
            }
        }
    }
    return false
}

python3 解法, 执行用时: 48 ms, 内存消耗: 16.2 MB, 提交时间: 2023-06-12 10:02:28

# 穷举累加序列第一个数字和第二个数字的所有可能性
class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        n = len(num)
        for secondStart in range(1, n-1):
            if num[0] == '0' and secondStart != 1:
                break
            for secondEnd in range(secondStart, n-1):
                if num[secondStart] == '0' and secondStart != secondEnd:
                    break
                if self.valid(secondStart, secondEnd, num):
                    return True
        return False
    
    def valid(self, secondStart: int, secondEnd: int, num: str) -> bool:
        n = len(num)
        firstStart, firstEnd = 0, secondStart - 1
        while secondEnd <= n - 1:
            third = self.stringAdd(num, firstStart, firstEnd, secondStart, secondEnd)
            thirdStart = secondEnd + 1
            thirdEnd = secondEnd + len(third)
            if thirdEnd >= n or num[thirdStart:thirdEnd+1] != third:
                break
            if thirdEnd == n-1:
                return True
            firstStart, firstEnd = secondStart, secondEnd
            secondStart, secondEnd = thirdStart, thirdEnd
        return False
    
    def stringAdd(self, s: str, firstStart: int, firstEnd: int, secondStart: int, secondEnd: int) -> str:
        third = []
        carry, cur = 0, 0
        while firstEnd >= firstStart or secondEnd >= secondStart or carry != 0:
            cur = carry
            if firstEnd >= firstStart:
                cur += ord(s[firstEnd]) - ord('0')
                firstEnd -= 1
            if secondEnd >= secondStart:
                cur += ord(s[secondEnd]) - ord('0')
                secondEnd -= 1
            carry = cur // 10
            cur %= 10
            third.append(chr(cur + ord('0')))
        return ''.join(third[::-1])

上一题

下一题

详情