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

$\textrm{Problem Description : }$$\href{https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/}{\textrm{LeetCode842—Split Array into Fibonacci Sequence}}$

题目本身没有特殊的技巧，因为确定一个斐波那契数列只需要首端的两个数，所以我们应当枚举所有元组$(A_0,A_1)$为数列的首端，然后在此条件下，字符串本身是否能分割成斐波那契数列。流程因当分为:

如果枚举$A_0,A_1$
如何在首端确定的情况下检测序列合法

对于$A_0$，其首下标$\textrm{index=0}$，仅需枚举长度，命名为$len_0$，于是$A_1$的起始下标为$len_1 = 0+len_0$，然后还需在此基础上枚举$A_1$的长度，命名其为$len_1$。显然这是一个二层$\textrm{for}$循环的结构，题干中有提到所有整数都在$\textrm{int}$范围内，且除$\textrm{0}$本身之外，不会有任何$\textrm{0}$开头的数，因此我们还需要向$\textrm{for}$循环结构中添加一些判定条件:

$\textrm{if(head == '0' and length > 1) continue or break; //0}$开头的数直接舍弃
$\textrm{if($A_i$ > INT_MAX) break; //}$不能超过$\textrm{INT}$的范围

这样就完成了首部的枚举，然后讨论如果对后续的部分进行$\textrm{check}$。令$\textrm{tar = $A_i+A_{i-1}$}$,那么我们既可以将字符串转换成$\textrm{int}$类型，然后与$\textrm{tar}$比较是否相等，也可以将$\textrm{tar}$转换成$\textrm{string}$类型，然后取相同长度的字串来对比。这里采用后者，因为题干中说过，除$\textrm{0}$本身之外，不会有任何$\textrm{0}$开头的数，而将字符串转换成$\textrm{int}$的过程中，会将开头的$\textrm{0}$直接抹去；相反，比较字符串本身时，会保留既有的$\textrm{0}$，省去了一些比较的代码。简述为$\textrm{:}$

$\textrm{S = S.substr($len_0+len_1$) }$
$\textrm{while(!S.empty())}$
$\textrm{tar = $A_i+A_{i-1}$}$
$\textrm{check = to_string(tar)}$
$\textrm{if(check == $S_{left}$.substr(0,check.size()) undate S;}$
$\textrm{or it's a false ($A_0,A_1$)}$

实际操作的过程中可以免去计算$\textrm{S}$的子串过程，而改用一个值来记录剩余部分的首下标，依次来获取子串。此外，加入一个参数$\textrm{cnt}$来计算斐波那契数列中的数的个数，以便在找到一个合法的序列之后快速构建$\textrm{vector}$，而不是再一次分割字符串。

最后分析一下时间与空间复杂度，对于空间复杂度，因为除去存储答案本身之外，只申请了常数个变量，所以空间复杂度为$O(1)$，而对于时间复杂度，我们首先假设字符长度足够长，那么在字符串$\textrm{11}$位时，必定超过$\textrm{INT_MAX}$，所以两层$\textrm{for}$循环最多进行$\textrm{100}$次。而对于字符串不够长的时候，$\textrm{$A_0,A_1$}$最长为$\textrm{S.size()/3}$,我们应当取其最小值，即$\textrm{min{S.size()/3,10}}$。对于后续序列的检测，相当于检测整个字符串的每一位，可以取其上界$\textrm{n}$,于是时间复杂度应为$O(k^2n)$，其中$\textrm{k =min{S.size()/3,10}}$

时间复杂度: $O(k^2n)$，其中$\textrm{k =min{S.size()/3,10}}$

空间复杂度: $O(1)$

typedef long long ll;
class Solution {
public:
    vector<int> splitIntoFibonacci(string s) {
        ll first = 0,second = 0;  //A0与A1
        int n = s.size(),cnt;
        bool f = true;         //标识符，表示是否还需进行搜索，找到一个合法的A0,A1后会被修改为false
        for(int index = 0;index < n-2 && f;index++) //至少需要2位给后两个数，所以为n-2
        {
            first = first*10+(s[index]-'0');
            if(s[0] == '0' && index > 0) break;  //首端为0的数直接舍弃
            if(first >= INT_MAX) break;             //不能超过int的范围
            second = 0;
            for(int len = 1;index+len < n-1 && f;len++)//至少需要1位给后两个数，所以为n-1
            {
                second = second*10+(s[index+len]-'0'); 
                if(s[index+1] == '0' && len > 1) break; //首端为0的数直接舍弃
                if(second >= INT_MAX) break;            //不能超过int的范围
                int i = index+len+1;
                ll tar = first+second,pre = second;
                cnt = 2;
                while(true)
                {
                    if(i == n)  //相当于S.empty()
                    {
                        f = false;  //合法的首端
                        break;
                    }
                    if(tar > INT_MAX) break;
                    string check = to_string(tar);
                    if(i+check.size() <= n && s.substr(i,check.size()) == check)
                    {
                        i += check.size();  //更新S
                        int t = tar;
                        tar += pre;
                        pre = t;
                        cnt++;
                    }
                    else break;
                }
            }
        }
        if(f) return {};
        //根据cnt构造答案
        vector<int> ans(cnt);
        ans[0] = first; ans[1] = second;
        for(int i = 2;i < cnt;i++) ans[i] = ans[i-1]+ans[i-2];
        return ans;
    }
};

Author@Kuroko

GitHub@SuperKuroko

LeetCode@kuroko177

Last Modified: 2020-12-08 14:46