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

$\textrm{Language: C++}$

$\textrm{Label: String}$

$\textrm{Solution:}$

题目本身没有特殊的技巧,因为确定一个斐波那契数列只需要首端的两个数,所以我们应当枚举所有元组$(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{:}$

  1. $\textrm{S = S.substr($len_0+len_1$) }$
  2. $\textrm{while(!S.empty())}$
  3. $\textrm{tar = $A_i+A_{i-1}$}$
  4. $\textrm{check = to_string(tar)}$
  5. $\textrm{if(check == $S_{left}$.substr(0,check.size()) undate S;}$
  6. $\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)$

$\textrm{C++ Source Code}$

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;
    }
};

$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$

$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$

$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$

$\textrm{Last Modified: 2020-12-08 14:46}$