[Swift]LeetCode842.将数组拆分成斐波那契序列|SplitArrayintoFibonacciSequence ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10614994.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 <= 200
S contains 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 }