• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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. 1 <= S.length <= 200
  2. 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. 1 <= S.length <= 200
  2. 字符串 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift: 用Alamofire做http请求,用ObjectMapper解析JSON发布时间:2022-07-13
下一篇:
Swift 编程语言入门教程 - Stars-OnMyWay发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap