[leetcode] 842. Split Array into Fibonacci Sequence

[leetcode] 842. Split Array into Fibonacci Sequence

Description

Given a string S of digits, such as S = “123456579”, we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type); F.length >= 3; and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2. Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input:

"123456579"

Output:

[123,456,579]

Example 2:

Input:

"11235813"

Output:

[1,1,2,3,5,8,13]

Example 3:

Input:

"112358130"

Output:

[]

Explanation:

The task is impossible.

Example 4:

Input:

"0123"

Output:

[]

Explanation:

Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

Input:

"1101111"

Output:

[110, 1, 111]

Explanation:

The output [11, 0, 11, 11] would also be accepted.

Note:

1 <= S.length <= 200S contains only digits.

分析

题目的意思是：把一个字符串分割成Fibonacci数组序列。

回溯法。Fibonacci数列是这样定义的：F[0] = 0F[1] = 1for each i ≥ 2: F[i] = F[i-1] + F[i-2]形如：0, 1, 1, 2, 3, 5, 8, 13, …，这种Fibonacci序列是当前的数为前两个数之和，弄清楚这个之后，我们就在递归遍历的时候进行判断就行了。终止条件就是idx遍历到末尾，并且res的size为3，表明已经有三个数了。否则返回false。递归的条件是前两个数只和等于当前的数。

代码

class Solution {public: vector splitIntoFibonacci(string S) { vector res; solve(S,0,res); return res; } bool solve(string s,int idx,vector &res){ if(idx==s.size()&&res.size()>=3){ return true; } long num=0; for(int i=idx;iINT_MAX) return false; if(res.size()>=2&&res[res.size()-2]+res.back()!=num) continue; res.push_back(num); if(solve(s,i+1,res)) return true; res.pop_back(); } return false; }};

参考文献

​​842. Split Array into Fibonacci Sequence​​​​Fibonacci数列​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。