[Swift]LeetCode873. 最长的斐波那契子序列的长度 | Length of Longest Fibonacci Subsequence...
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公眾號：山青詠芝（shanqingyongzhi）
?博客園地址：山青詠芝（https://www.cnblogs.com/strengthen/）
?GitHub地址：https://github.com/strengthen/LeetCode
?原文地址：?https://www.cnblogs.com/strengthen/p/10600243.html?
?如果鏈接不是山青詠芝的博客園地址，則可能是爬取作者的文章。
?原文已修改更新！強烈建議點擊原文地址閱讀！支持作者！支持原創(chuàng)！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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}
給定一個嚴(yán)格遞增的正整數(shù)數(shù)組形成序列，找到?A?中最長的斐波那契式的子序列的長度。如果一個不存在，返回??0 。
（回想一下，子序列是從原序列?A?中派生出來的，它從?A?中刪掉任意數(shù)量的元素（也可以不刪），而不改變其余元素的順序。例如，?[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 }?
轉(zhuǎn)載于:https://www.cnblogs.com/strengthen/p/10600243.html
總結(jié)
以上是生活随笔為你收集整理的[Swift]LeetCode873. 最长的斐波那契子序列的长度 | Length of Longest Fibonacci Subsequence...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
