欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

leetcode每日一题—842.将数组拆分成斐波那契数列

程序员文章站 2022-04-02 11:05:22
题目:给定一个数字字符串 S,比如 S = “123456579”,我们可以将它分成斐波那契式的序列 [123, 456, 579]。形式上,斐波那契式序列是一个非负整数列表 F,且满足:0 <= F[i] <= 2^31 - 1,(也就是说,每个整数都符合 32 位有符号整数类型);F.length >= 3;对于所有的0 <= i < F.length - 2,都有 F[i] + F[i+1] = F[i+2] 成立。另外,请注意,将字符串拆分成小块时,每个块的...

题目:
给定一个数字字符串 S,比如 S = “123456579”,我们可以将它分成斐波那契式的序列 [123, 456, 579]。
形式上,斐波那契式序列是一个非负整数列表 F,且满足:
0 <= F[i] <= 2^31 - 1,(也就是说,每个整数都符合 32 位有符号整数类型);
F.length >= 3;
对于所有的0 <= i < F.length - 2,都有 F[i] + F[i+1] = F[i+2] 成立。

另外,请注意,将字符串拆分成小块时,每个块的数字一定不要以零开头,除非这个块是数字 0 本身。
返回从 S 拆分出来的任意一组斐波那契式的序列块,如果不能拆分则返回 []。

思路:
参考:https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/solution/python3-sou-suo-by-fan-cai-q85h/

因为斐波那契数列满足 F[i] + F[i+1] = F[i+2],所以 只要前两个数确定,整个斐波那契数列就确定了。
所以可判断 所有可能的前两个数,并对其后数值进行判断,不符合直接返回False。
F[i]<=2^31-1=2 147 483 647 (10位)
res:最终的结果
now:当前待判断的数

leetcode每日一题—842.将数组拆分成斐波那契数列

解答:

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
            n, up = len(S), 2147483647
            #用res来记录最终返回的斐波那契数列(如果存在)
            res=[]
            
            #根据当前确定的前两个数,判断能否组成斐波那契数列
            def get_list(start):
                # 判断斐波那契数列的第一个数和第二个数 会不会超过上限
                if max(res) > up:
                    return False

                # 遍历后面所有的字符串,看看能不能组成斐波那契数列
                # 如果 数超上限 或 最后一个数超字符串长度 或 字符串并不是下一个数 则直接跳出
                while start < n:
                    now = res[-1] + res[-2]
                    c = len(str(now))
                    if now > up or start + c > n or int(S[start:start + c]) != now:
                        return False
                    res.append(now)
                    start += c
                return True
            
            #第一个数取i位,第二个数取j位,两个数最多分别 10位
            for i in range(1, 11):
                # 当第一个数取i位时,第二个数 最多取n-i-1位 且 不能超过10位,故j最大为 min(11,n-i)-1
                # 至少留一位给第三个数
                for j in range(1, min(11, n - i)):
                    res = [int(S[:i]), int(S[i:i + j])]
                    #防止第二个数为 2位以上,且以0开头
                    if S[i] == '0' and j!=1:
                        break
                    if get_list(i + j):
                        return res
                #防止第一个数位 2位以上,且以0开头
                if S[0] == '0':
                    break
            return []

本文地址:https://blog.csdn.net/jqq125/article/details/110927538

相关标签: leetcode