$\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{:}$
- $\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)$
$\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}$
退出登录?