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

[Swift]LeetCode873. 最长的斐波那契子序列的长度 | Length of Longest Fibonacci Sub ...

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

A sequence X_1, X_2, ..., X_n is fibonacci-like if:

  • n >= 3
  • X_i + X_{i+1} = X_{i+2} for all i + 2 <= n

Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A.  If one does not exist, return 0.

(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements.  For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].) 

Example 1:

Input: [1,2,3,4,5,6,7,8]
Output: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18]. 

Note:

  • 3 <= A.length <= 1000
  • 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
  • (The time limit has been reduced by 50% for submissions in Java, C, and C++.)

如果序列 X_1, X_2, ..., X_n 满足下列条件,就说它是 斐波那契式 的:

  • n >= 3
  • 对于所有 i + 2 <= n,都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列,找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在,返回  0 。

(回想一下,子序列是从原序列 A 中派生出来的,它从 A 中删掉任意数量的元素(也可以不删),而不改变其余元素的顺序。例如, [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列) 

示例 1:

输入: [1,2,3,4,5,6,7,8]
输出: 5
解释:
最长的斐波那契式子序列为:[1,2,3,5,8] 。

示例 2:

输入: [1,3,7,11,12,14,18]
输出: 3
解释:
最长的斐波那契式子序列有:
[1,11,12],[3,11,14] 以及 [7,11,18] 。 

提示:

  • 3 <= A.length <= 1000
  • 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
  • (对于以 Java,C,C++,以及 C# 的提交,时间限制被减少了 50%)

228ms

 1 class Solution {
 2     func lenLongestFibSubseq(_ A: [Int]) -> Int {
 3 
 4         var dic = [Int:Int]()
 5         for item in 0..<A.count{
 6             dic[A[item]] = item
 7         }
 8 
 9         var dp = [[Int]](repeating:[Int](repeating: 0, count: A.count) , count: A.count)
10         var result = 0
11         for i in 0..<A.count {
12             for j in 0..<i{
13                 if A[i] - A[j] < A[j] && dic[A[i] - A[j]] != nil {
14                     dp[j][i] = dp[dic[A[i] - A[j]]!][j] + 1
15                     result = max(result, dp[j][i])
16                 }
17             }
18         }
19         return result > 0 ? result + 2 : 0
20     }
21 }

236ms

 1 class Solution {
 2     func lenLongestFibSubseq(_ A: [Int]) -> Int {
 3         var map = [Int: Int]()
 4         for (index, a) in A.enumerated() {
 5             map[a] = index
 6         }
 7         
 8         var result = 0
 9         var dp = [[Int]](repeating: [Int](repeating: 2, count: A.count), count: A.count)
10         for i in 0 ..< A.count {
11             for j in i+1 ..< A.count {
12                 let a = A[i], b = A[j], c = b - a
13                 if map[c] != nil {
14                     if map[c]! >= i {
15                         break
16                     }
17                     dp[i][j] = dp[map[c]!][i] + 1
18                     result = max(result, dp[i][j])
19                 }
20             }
21         }
22         
23         return result
24     }
25 }

368ms

 1 class Solution {
 2     func lenLongestFibSubseq(_ A: [Int]) -> Int {
 3         let N = A.count
 4         var indexMap = [Int: Int]()
 5         for i in 0..<N {
 6             indexMap[A[i]] = i
 7         }
 8         
 9         var longestMap = [Int: Int]()
10         var ans = 0
11         
12         for k in 0..<N {
13             for j in 0..<k {
14                 guard let i = indexMap[A[k] - A[j]] else {
15                     continue
16                 }
17                 if i < j {
18                     var temp = 0
19                     if let cand = longestMap[i * N + j] {
20                         temp = cand + 1
21                     } else {
22                         temp = 3
23                     }
24                     longestMap[j * N + k] = temp
25                     ans = max(ans, temp)
26                 }
27             }
28         }
29         
30         return ans >= 3 ? ans : 0
31     }
32 }

376ms

 1 class Solution {
 2     func lenLongestFibSubseq(_ A: [Int]) -> Int {
 3         var n = A.count, res = 0
 4         var dp = [[Int]](repeating: [Int](repeating: 2, count: n), count: n)
 5         var m = [Int: Int]()
 6         for i in 0..<n {
 7             m[A[i]] = i
 8         }
 9         for j in 1..<n {
10             for i in 0..<j {
11                 if let idx = m[A[j] - A[i]], idx < i {
12                     dp[i][j] = max(dp[i][j], dp[idx][i] + 1)
13                     res = max(res, dp[i][j])
14                 } 
15             }
16         }
17         return res
18     }
19 }

388ms

 1 class Solution {
 2     func lenLongestFibSubseq(_ A: [Int]) -> Int {
 3         let set = Set(A)
 4         var res = 0
 5         for i in 0 ..< A.count {
 6             for j in i + 1 ..< A.count {
 7                 var a = A[i]
 8                 var b = A[j]
 9                 var c = a + b
10                 var size = 2
11                 while set.contains(c) {
12                     size += 1
13                     res = max(res, size)
14                     a = b
15                     b = c
16                     c = a + b
17                 }   
18             }
19         }
20         return res
21     }
22 }

392ms

 1 class Solution {
 2     func lenLongestFibSubseq(_ A: [Int]) -> Int {
 3         let N = A.count
 4         if N <= 2 { return N }
 5         
 6         var map = [Int: Int]()
 7         for i in 0..<N { map[A[i]] = i }
 8 
 9         var res = 0
10         var dp = Array(repeating: Array(repeating: 2, count: N), count: N)
11         for i in (0..<N - 1).reversed() {
12             for j in (i + 1..<N) {
13                 if let k = map[A[i] + A[j]] {
14                     dp[i][j] = dp[j][k] + 1
15                     res = max(res, dp[i][j])
16                 }
17             }
18         }
19         return res
20     }
21 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
Swift NSAttributedString的使用发布时间:2022-07-13
下一篇:
Swift 用户交互翻译,本地化代码中的字符串发布时间: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