BAT面試算法進(jìn)階(10)- 最長的斐波那契子序列的長度(暴力法)
BAT面試算法進(jìn)階(8)- 刪除排序數(shù)組中的重復(fù)項(xiàng)
BAT面試算法進(jìn)階(7)- 反轉(zhuǎn)整數(shù)
BAT面試算法進(jìn)階(6)- BAT面試算法進(jìn)階(6)-最長回文子串(方法二)
BAT面試算法進(jìn)階(5)- BAT面試算法進(jìn)階(5)- 最長回文子串(方法一)
BAT面試算法進(jìn)階(4)- 無重復(fù)字符的最長子串(滑動法優(yōu)化+ASCII碼法)
BAT面試算法進(jìn)階(3)- 無重復(fù)字符的最長子串(滑動窗口法)
BAT面試算法進(jìn)階(2)- 無重復(fù)字符的最長子串(暴力法)
BAT面試算法進(jìn)階(1)--兩數(shù)之和
一.面試題目
如果序列X_1,X_2,...,X_n 滿足下列條件,就說它是 斐波拉契式的:
n >= 3- 對于所有
i+2 <= n,都有X_i + X_{i+1} = X_{i+2};
給定一個(gè)嚴(yán)格遞增的正整數(shù)數(shù)組形成序列.找到A中最長的斐波拉契式子序列的長度.如果一個(gè)不存在,返回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]
三.解決方案-- 使用Set(集合)暴力法
- 思路
將斐波拉契式的子序列中的2個(gè)連續(xù)項(xiàng)A[i],A[j] 視為單個(gè)結(jié)點(diǎn)(i,j).整個(gè)子序列是這些連續(xù)結(jié)點(diǎn)的之間的路徑.例如,對于斐波拉契式的子序列,(A[1] = 2,A[2] = 3,A[4] = 5,A[7] = 8,A[10] = 13),結(jié)點(diǎn)的路徑就為(1,2)<->(2,3)<->(4,7)<->(7,10).
這樣做的目的,只有當(dāng)A[i]+A[j] == A[k]時(shí).兩結(jié)點(diǎn)(i,j)和(j,k)才是連貫的.我們需要這個(gè)信息才能知道它們之間是可以連通的.
- 算法
設(shè)longest[i,j] 是結(jié)束在[i,j]的最長路徑.那么如果(i,j)和(j,k)是連通的,longest[j,k] = longest[i,j]+1.由于 i 是由A.index(A[k] - A[j]) 唯一確定的.我們在 i 檢查每組j < k ,并相應(yīng)更新longest[j,k]
四.代碼
class Solution {
public:
int lenLongestFibSubseq(vector<int>& A) {
int N = A.size();
unordered_map<int, int> index;
for (int i = 0; i < N; ++i)
index[A[i]] = i;
unordered_map<int, int> longest;
int ans = 0;
for (int k = 0; k < N; ++k)
for (int j = 0; j < k; ++j) {
if (A[k] - A[j] < A[j] && index.count(A[k] - A[j])) {
int i = index[A[k] - A[j]];
longest[j * N + k] = longest[i * N + j] + 1;
ans = max(ans, longest[j * N + k] + 2);
}
}
return ans >= 3 ? ans : 0;
}
};
五.復(fù)雜度分析
-
時(shí)間復(fù)雜度:
O(N^2),其中N指的是A的長度 -
空間復(fù)雜度:
O(NlogM),其中M是A中的最大的元素.
六.學(xué)習(xí)建議
- 先了解基本思路
- 在帶著數(shù)據(jù),理解代碼的執(zhí)行
小編OS:
想要獲取更多技術(shù)文章/視頻關(guān)注公眾號!
持續(xù)更新關(guān)注公眾號!
