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

資訊專(zhuān)欄INFORMATION COLUMN

leetcode 300. Longest Increasing Subsequence

eechen / 490人閱讀

摘要：題目要求找到整數(shù)數(shù)組中最長(zhǎng)的遞增子數(shù)組。該子數(shù)組可以為不連續(xù)的。如題目中例子所示，得到的最長(zhǎng)子數(shù)組為。最后我們還需要遍歷一遍全部子數(shù)組的長(zhǎng)度并獲得最大的長(zhǎng)度。

題目要求 
Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

找到整數(shù)數(shù)組中最長(zhǎng)的遞增子數(shù)組。該子數(shù)組可以為不連續(xù)的。如題目中例子所示，[10, 9, 2, 5, 3, 7, 101, 18]得到的最長(zhǎng)子數(shù)組為[2,3,7,101]。

思路一：動(dòng)態(tài)規(guī)劃

從動(dòng)態(tài)規(guī)劃的角度來(lái)說(shuō)，假設(shè)要計(jì)算以第i位為結(jié)尾所構(gòu)成的最長(zhǎng)遞增子數(shù)組，并且我們已經(jīng)知道了第0位，第1位...第i-1位的任何一個(gè)值為最后一個(gè)數(shù)字時(shí)所能構(gòu)成的最長(zhǎng)子數(shù)組的長(zhǎng)度。那么我們只需要從中找到值比當(dāng)前小的值的下標(biāo)，并且比較二者構(gòu)成的子數(shù)組的長(zhǎng)度，再?gòu)闹蝎@得最大長(zhǎng)度的遞增子數(shù)組，作為當(dāng)前數(shù)組為最后一個(gè)值所構(gòu)成的遞增子數(shù)組的最大長(zhǎng)度。

最后我們還需要遍歷一遍全部子數(shù)組的長(zhǎng)度并獲得最大的長(zhǎng)度。

   public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        if(length==0) return 0;
        int T[] = new int[nums.length];
        for(int i = 1 ; i=0 ; j-- ){
                if(nums[j] < nums[i] && T[j] + 1 > T[i]){
                    T[i] = T[j] + 1;
                }
            }
        }
        int max = 0;
        for(int cur : T){
            max = Math.max(cur, max);
        }
        return max+1;
    }
思路二：大牛思路

這里附上一個(gè)解釋的非常好的文章，我根據(jù)其思路的實(shí)現(xiàn)如下：

    public int lengthOfLIS2(int[] nums){
        int length = nums.length;
        if(length == 0) return 0;
        
        int[] tmp = new int[length];
        tmp[0] = nums[0];
        int max = 1;
        for(int i = 1 ; i=0 ; j--){
                if(j==0 && nums[i] < tmp[j]) tmp[j] = nums[i];
                else if(j == max-1 && nums[i] > tmp[j]){
                    tmp[j+1] = nums[i];
                    max++;
                    break;
                }
                else if(nums[i] < tmp[j] && nums[i] >tmp[j-1]){
                    tmp[j] = nums[i];
                    break;
                } 
            }
        }
        return max;
    }


想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

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

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

相關(guān)文章

  • LeetCode[300] Longest Increasing Subsequence

    摘要：再用二分法找當(dāng)前值應(yīng)該在排好序的數(shù)組中的插入位置。因?yàn)橐业氖亲铋L(zhǎng)的序列，所以每次將排好序的數(shù)組中替換成已經(jīng)排好序的，會(huì)能保證得到的結(jié)果是最長(zhǎng)的。保證升序相等也要替換這個(gè)值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...

    blankyao 評(píng)論0 收藏0

  • [LeetCode] 300. Longest Increasing Subsequence

    Problem Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18]Output: 4 Explanation: The longest increasing subsequence is [2,3,7...

    luckyyulin 評(píng)論0 收藏0

  • leetcode-300-Longest Increasing Subsequence

    摘要：本質(zhì)找出最長(zhǎng)的遞增子序列的長(zhǎng)度，可以是不連續(xù)的。應(yīng)用判斷滿足一定條件的子序列的最大長(zhǎng)度，用動(dòng)態(tài)數(shù)組加以處理。二分法確定滿足條件的位置。類(lèi)似二分法查找元素，查找某種情況的子序列。 本質(zhì)： 找出最長(zhǎng)的遞增子序列的長(zhǎng)度，可以是不連續(xù)的。 用一個(gè)數(shù)組存儲(chǔ) 遞增子序列，遍歷原始數(shù)組，每增加一個(gè)數(shù)，往里添加到對(duì)應(yīng)的順序，記錄他的位置，即為此數(shù)組的長(zhǎng)度。 成立的理由：每一個(gè)數(shù)添加以后，都有對(duì)...

    amc 評(píng)論0 收藏0

  • [leetcode]Longest Increasing Subsequence

    摘要：對(duì)于一個(gè)遞增子序列，想要增加它的長(zhǎng)度，就必須在尾部添加一個(gè)更大的值。表示以結(jié)尾的最長(zhǎng)遞增序列的長(zhǎng)度。長(zhǎng)度增加的條件就是一個(gè)數(shù)字比大。長(zhǎng)度最大值即為輸入數(shù)組的長(zhǎng)度。 Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10,...

    wow_worktile 評(píng)論0 收藏0

  • Longest Increasing Subsequence

    摘要：題目鏈接主要兩種方法和用，就是每次找出為結(jié)尾的最長(zhǎng)的串的長(zhǎng)度就好了。所以分解成就是，這個(gè)復(fù)雜度是。用一個(gè)數(shù)組，表示的長(zhǎng)度為，表示長(zhǎng)度為的，最右邊的可能的最小值。這里只要求長(zhǎng)度即可，那就直接用就可以了，整個(gè)用個(gè)數(shù)組就行了。 Longest Increasing Subsequence 題目鏈接：https://leetcode.com/problems... 主要兩種方法：dp和gree...

    FullStackDeveloper 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

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