亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

873. 最長的斐波那契子序列的長度

cucumber / 483人閱讀

摘要：示例輸入輸出解釋最長的斐波那契式子序列有，以及。故我們使用二維數(shù)組來存儲這一信息，二維數(shù)組的兩個(gè)索引分別為該斐波那契數(shù)列前兩個(gè)數(shù)在中的索引，其對應(yīng)的值為由該數(shù)列在整個(gè)序列中的最大長度。

如果序列 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] 的一個(gè)子序列）

示例 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] 。

如果直接使用遍歷算法的話，時(shí)間復(fù)雜度大概是O(n^3)這個(gè)數(shù)量級，而題目要求中給出的數(shù)組A的最大長度為1000,如果使用O(n^3)的算法，勢必會超時(shí)。
考慮如何簡化：斐波那契數(shù)列有一個(gè)性質(zhì)，即一但前兩個(gè)數(shù)字確定，整個(gè)數(shù)列即確定的。故我們使用二維數(shù)組來存儲這一信息， 二維數(shù)組map的兩個(gè)索引分別為該斐波那契數(shù)列前兩個(gè)數(shù)在A中的索引，其對應(yīng)的值為由該數(shù)列在整個(gè)序列中的最大長度。
我們只要從后往前遍歷整個(gè)數(shù)組，就能使用到map中所儲存的信息，具體代碼如下：

代碼：

class Solution {
    public int lenLongestFibSubseq(int[] A) {
        int res = 0;
        // HashMap map = new HashMap();
        int [][] map = new int [A.length][A.length];
        map[A.length- 2][A.length -1] = 2;
//        List  list = new ArrayList<>();
//        for(int i = 0 ; i < A.length ; i++){
//            list.add(A[i]);
//        }
        for(int j = A.length - 3; j >= 0; j--){
            for(int i = j + 1; i  target) {
                end = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/72045.html

相關(guān)文章

  • 遞歸

    摘要：遞歸概念遞歸是一種針對簡單循環(huán)難以編程實(shí)現(xiàn)的問題，通過函數(shù)調(diào)用自身，提供優(yōu)雅解決方案的技術(shù)。擁有基礎(chǔ)情況或終止條件來停止遞歸。這個(gè)稱之為遞歸調(diào)用。為了避免重新創(chuàng)建字符串，使用遞歸輔助方法來進(jìn)行改良。 遞歸概念 遞歸是一種針對簡單循環(huán)難以編程實(shí)現(xiàn)的問題，通過函數(shù)調(diào)用自身，提供優(yōu)雅解決方案的技術(shù)。 遞歸都具有以下三個(gè)要點(diǎn)： 使用 if-else 或 switch 語句來引導(dǎo)不同的情況。 ...

    alphahans 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法

    摘要：這是一個(gè)簡單的遞歸函數(shù)，你可以使用它來生成數(shù)列中指定序號的數(shù)值這個(gè)函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計(jì)算。 本章內(nèi)容銜接上一章　數(shù)據(jù)結(jié)構(gòu)與算法：二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu)： 數(shù)組 常見操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸：遞歸是很多算法都使用的一種編程方法 　　- 如何將問題分成基線條件和遞歸條件 　　- 分而治之策略解決棘手問題 ...

    wuyumin 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法

    摘要：這是一個(gè)簡單的遞歸函數(shù)，你可以使用它來生成數(shù)列中指定序號的數(shù)值這個(gè)函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計(jì)算。 本章內(nèi)容銜接上一章　數(shù)據(jù)結(jié)構(gòu)與算法：二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu)： 數(shù)組 常見操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸：遞歸是很多算法都使用的一種編程方法 　　- 如何將問題分成基線條件和遞歸條件 　　- 分而治之策略解決棘手問題 ...

    Carson 評論0 收藏0

  • 從斐波那契數(shù)列看遞歸和動(dòng)態(tài)規(guī)劃

    摘要：大名鼎鼎的斐波那契數(shù)列，，，，，，，，使用數(shù)學(xué)歸納法可以看出其規(guī)律為。對于斐波那契數(shù)列的求解，有自頂向下的記憶化搜索遞歸和自下向上的迭代法，他們都使用了動(dòng)態(tài)規(guī)劃的思想。 大名鼎鼎的斐波那契數(shù)列：0，1，1，2，3，5，8，13，21...使用數(shù)學(xué)歸納法可以看出其規(guī)律為：f(n) = f(n-1) + f(n-2)。 遞歸 下面首先直接使用遞歸（JavaScript實(shí)現(xiàn)）來求解第 n ...

    charles_paul 評論0 收藏0

  • js 實(shí)現(xiàn)斐波那契數(shù)列(數(shù)組緩存、動(dòng)態(tài)規(guī)劃、尾調(diào)用優(yōu)化)

    摘要：根據(jù)該規(guī)則，返回第個(gè)斐波那契數(shù)。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。一個(gè)前端眼中的斐波那契數(shù)列解斐波那契數(shù)列的實(shí)用解法調(diào)用棧尾遞歸和手動(dòng)優(yōu)化尾調(diào)用優(yōu)化譯我從用寫斐波那契生成器中學(xué)到的令人驚訝的件事 斐波那契數(shù)列是以下一系列數(shù)字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數(shù)字 0 和 1 ...

    趙連江 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<