Re: [閒聊] 每日leetcode
873. Length of Longest Fibonacci Subsequence
費波那契數列一定是超過3個數字
所以我們先固定前兩個數字，在往後找有沒有符合條件的數字
並且紀錄最長的數列
先用一個map:rec紀錄arr裡的所有數字
假設數列的前兩位是arr[i]、arr[j] ( i < j )
令cur = arr[j] next = arr[i]+arr[j]
先檢查rec[next]是否存在
存在的話，把cur、next各自往前一位
cur = next、next = next + cur
這樣找出最長的數列
func lenLongestFibSubseq(arr []int) int {
rec, ans, n := make(map[int]bool), 0, len(arr)
for _, val := range arr {
rec[val] = true
}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
next := arr[i] + arr[j]
if rec[next] {
cnt, cur, next := 3, next, next+arr[j]
for rec[next] {
cnt++
cur, next = next, next+cur
}
ans = max(ans, cnt)
}
}
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.142.63 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1740676878.A.D49.html
推
02/28 01:30,
9月前
, 1F
02/28 01:30, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1354 之 1552 篇)：