★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10614994.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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 all0 <= 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 <= 200Scontains only digits.
给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。
形式上，斐波那契式序列是一个非负整数列表 F，且满足：
0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；F.length >= 3；- 对于所有的
0 <= i < F.length - 2，都有F[i] + F[i+1] = F[i+2]成立。
另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
返回从 S 拆分出来的所有斐波那契式的序列块，如果不能拆分则返回 []。
示例 1：
输入："123456579" 输出：[123,456,579]
示例 2：
输入: "11235813" 输出: [1,1,2,3,5,8,13]
示例 3：
输入: "112358130" 输出: [] 解释: 这项任务无法完成。
示例 4：
输入："0123" 输出：[] 解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。
示例 5：
输入: "1101111" 输出: [110, 1, 111] 解释: 输出 [11,0,11,11] 也同样被接受。
提示：
1 <= S.length <= 200- 字符串
S中只含有数字。
8ms
1 class Solution { 2 fileprivate var res = [Int]() 3 fileprivate var maxVal = Int(pow(2.0,31.0)-1) 4 fileprivate var found = false 5 6 func splitIntoFibonacci(_ S: String) -> [Int] { 7 guard S.count >= 3 else { 8 return [Int]() 9 } 10 11 var S = S.characters.map{Int(String($0))!} 12 13 findSequence(S) 14 return found ? res : [Int]() 15 } 16 17 func findSequence(_ S: [Int], _ from: Int = 0){ 18 if from >= S.count && res.count >= 3{ 19 found = true 20 return 21 } 22 23 var current = 0 24 for i in from..<S.count{ 25 current *= 10 26 current += S[i] 27 guard current < maxVal else{ 28 return 29 } 30 31 if i - from >= 1 && current < 10{ 32 return 33 } 34 35 if isFibSeq(current){ 36 findSequence(S, i + 1) 37 if found{ 38 return 39 } 40 res.remove(at: res.count - 1) 41 } 42 } 43 } 44 45 func isFibSeq(_ num: Int)->Bool{ 46 let count = res.count 47 if count < 2{ 48 res.append(num) 49 return true 50 } 51 52 if res[count - 1] + res[count - 2] == num{ 53 res.append(num) 54 return true 55 } 56 57 return false 58 } 59 }
20ms
1 private extension String { 2 var leadingZero: Bool { 3 guard self.count > 1 else { 4 return false 5 } 6 7 if self[self.startIndex] == "0" { 8 return true 9 } 10 11 return false 12 } 13 } 14 15 /// 我们将一个给定的字符串进行分割，分割成斐波那契数列 16 17 class Solution { 18 var limit: Int = 2_147_483_647 19 20 func splitIntoFibonacci(_ S: String) -> [Int] { 21 if S.count < 3 { 22 return [] 23 } 24 var array: [String] = [] 25 26 for index in 1...(min(10, S.count - 2)) { 27 let firstString = String(S.prefix(index)) 28 29 let lastString = String(S.suffix(S.count - index)) 30 31 array.append(firstString) 32 33 if firstString.leadingZero { 34 return [] 35 } 36 37 if findSecondSecondString(String(lastString), list: &array) { 38 return array.map({Int($0) ?? 0}) 39 } else { 40 array.removeAll() 41 } 42 } 43 44 return [] 45 } 46 47 func findSecondSecondString(_ S: String, list: inout [String]) -> Bool { 48 if S.count < 1 { 49 return false 50 } 51 52 for index in 1...(min(10, S.count - 1)) { 53 let firstString = String(S.prefix(index)) 54 55 let lastString = String(S.suffix(S.count - index)) 56 57 list.append(firstString) 58 59 if judgeStringCanUse(lastString, list: &list) { 60 return true 61 } else { 62 let keep = list[0] 63 list.removeAll() 64 list.append(keep) 65 continue 66 } 67 } 68 return false 69 } 70 71 func judgeStringCanUse(_ S: String, list: inout [String]) -> Bool { 72 if S.count == 0 && list.count > 2 { 73 return true 74 } 75 76 let n = Int(list[list.count - 1]) ?? 0 77 let n1 = Int(list[list.count - 2]) ?? 0 78 let target = n + n1 79 guard n <= limit && n1 <= limit && target <= limit else { 80 return false 81 } 82 83 let targetString = "(n + n1)" 84 85 let firstS = S.prefix(targetString.count) 86 87 if firstS == targetString { 88 list.append(String(firstS)) 89 90 return judgeStringCanUse(String(S.suffix(S.count - firstS.count)), list: &list) 91 } 92 93 return false 94 } 95 }
Runtime: 36 ms
Memory Usage: 21.8 MB
1 class Solution { 2 func splitIntoFibonacci(_ S: String) -> [Int] { 3 var ans:[Int] = [Int]() 4 var cur:[Int] = [Int]() 5 if S.isEmpty {return ans} 6 SFhelper(S,0,&cur,&ans) 7 return ans 8 } 9 10 func SFhelper(_ S:String,_ start:Int,_ cur:inout [Int],_ ans:inout [Int]) 11 { 12 if !ans.isEmpty{return} 13 if start == S.count 14 { 15 if cur.count > 2 { ans += cur} 16 return 17 } 18 let N:Int = cur.count 19 var V:Int64 = 0 20 var arrS:[Character] = Array(S) 21 for i in start..<S.count 22 { 23 V = V * 10 + Int64((arrS[i].ascii - 48)) 24 if V > 2147483647 {break} 25 if N < 2 26 { 27 cur.append(Int(V)) 28 SFhelper(S, i + 1, &cur, &ans) 29 cur.popLast() 30 } 31 else 32 { 33 let beforeSum:Int = cur[N - 1] + cur[N - 2] 34 if beforeSum > V {continue} 35 else if beforeSum < V {break} 36 else 37 { 38 cur.append(Int(V)) 39 SFhelper(S, i + 1, &cur, &ans) 40 cur.popLast() 41 } 42 } 43 if V==0 {break} 44 } 45 } 46 } 47 48 //Character扩展 49 extension Character 50 { 51 //Character转ASCII整数值(定义小写为整数值) 52 var ascii: Int { 53 get { 54 return Int(self.unicodeScalars.first?.value ?? 0) 55 } 56 } 57 }
100ms
1 class Solution { 2 private var result: [Int] = [] 3 func splitIntoFibonacci(_ S: String) -> [Int] { 4 split(Array(S), nil, nil, nil, 0, []) 5 return result 6 } 7 8 private func split(_ s: [Character], 9 _ op1: Int?, 10 _ op2: Int?, 11 _ sum: Int?, 12 _ start: Int, 13 _ out: [Int]) -> Bool { 14 if start == s.count { 15 if op1 != nil && op2 != nil && sum != nil { 16 result = out 17 return true 18 } 19 return false 20 } else { 21 for i in start..<s.count { 22 if i - start > 0 && s[start] == "0" { return false } 23 if let num = String(s[start...i]).toInt() { 24 if num > Int(pow(2.0, 31.0)) - 1 { return false } 25 if op1 == nil { 26 if split(s, num, op2, sum, i + 1, out + [num]) { 27 return true 28 } 29 } else if op2 == nil { 30 if split(s, op1, num, sum, i + 1, out + [num]) { 31 return true 32 } 33 } else { 34 if num - op1! == op2! { 35 if split(s, op2, num, num, i + 1, out + [num]) { 36 return true 37 } 38 } 39 } 40 } 41 } 42 return false 43 } 44 } 45 } 46 47 extension String { 48 func toInt() -> Int? { 49 return Int(self)! 50 } 51 }
104ms
1 class Solution { 2 func splitIntoFibonacci(_ S: String) -> [Int] { 3 var result = [Int]() 4 var chars = Array(S) 5 helper(&result, chars) 6 return result 7 } 8 9 fileprivate func helper(_ res: inout [Int], _ chars: [Character]) -> Bool { 10 if res.count > 2 && chars.count == 0 { 11 return true 12 } 13 14 for i in 0..<chars.count { 15 if chars[0] == "0" && i > 0 { 16 break 17 } 18 19 // Int("2147483647214748364")! 20 21 guard let val = Int(String(chars[0...i])), val < Int32.max else { 22 return false 23 } 24 25 26 let size = res.count 27 if size >= 2 && val > res[size - 1] + res[size - 2] { 28 return false 29 } 30 31 if size < 2 || val == res[size - 1] + res[size - 2] { 32 res.append(val) 33 if helper(&res, Array(chars[(i+1)...])) { 34 return true 35 } 36 res.removeLast() 37 } 38 } 39 return false; 40 } 41 }