本文主要是介绍842. Split Array into Fibonacci Sequence(Leetcode每日一题-2020.12.08),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Problem
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.
Note:
- 1 <= S.length <= 200
- S contains only digits.
Example1
Input: “123456579”
Output: [123,456,579]
Example2
Input: “11235813”
Output: [1,1,2,3,5,8,13]
Example3
Input: “112358130”
Output: []
Explanation: The task is impossible.
Example4
Input: “0123”
Output: []
Explanation: Leading zeroes are not allowed, so “01”, “2”, “3” is not valid.
Example5
Input: “1101111”
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.
Solution
class Solution {
public:vector<int> splitIntoFibonacci(string S) {if(S.empty())return {};vector<long long> ret;cout<<dfs(S,0,ret);if(S[0] == '0' && ret.size() > 1 && ret[0] != 0)return {};vector<int> ret_int(ret.begin(),ret.end());return ret_int;}bool dfs(string &s,int start,vector<long long> &ret){if(start == s.length() && ret.size() >=3 && ret[ret.size()-1] == ret[ret.size()-2] + ret[ret.size()-3])return true;if(ret.size() >=3 && ret[ret.size()-1] != ret[ret.size()-2] + ret[ret.size()-3])return false;long long cur = 0;for(int i = start;i<s.length();++i){if(cur >= (INT_MAX-(s[i] - '0'))/10) //溢出直接剪枝return false;cur = 10 * cur + s[i] - '0';ret.push_back(cur);if(dfs(s,i+1,ret))return true;ret.pop_back();}return false;}
};
这篇关于842. Split Array into Fibonacci Sequence(Leetcode每日一题-2020.12.08)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!