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

資訊專欄INFORMATION COLUMN

[leetcode]Longest Increasing Subsequence

wow_worktile / 598人閱讀

摘要：對于一個遞增子序列，想要增加它的長度，就必須在尾部添加一個更大的值。表示以結(jié)尾的最長遞增序列的長度。長度增加的條件就是一個數(shù)字比大。長度最大值即為輸入數(shù)組的長度。

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(n^2) complexity.

對于一個遞增子序列，想要增加它的長度，就必須在尾部添加一個更大的值。
O(n^2)
dp[i]表示以nums[i]結(jié)尾的最長遞增序列的長度。長度增加的條件就是一個數(shù)字比nums[i]大。

public int lengthOfLIS(int[] nums) {
        int N = nums.length;
        if (N == 0) return 0;
        int[] dp = new int[N];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

O(nlogn)
長度最大值即為輸入數(shù)組的長度。用dp[i]表示，長度為i時，結(jié)尾的數(shù)字?？梢圆粩喔?。這里可以用binarySearch來查詢需要插放的位置。
Java自帶的binarySearch，如果有該元素則返回正確的index,如果沒有返回-(index+1)，是一個負(fù)數(shù)，我們需要替換成正確的數(shù)值。

public class Solution {
    public int lengthOfLIS(int[] nums) {            
        int[] dp = new int[nums.length];
        int len = 0;

        for(int x : nums) {
            int i = Arrays.binarySearch(dp, 0, len, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }
}

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

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

相關(guān)文章

  • LeetCode[300] Longest Increasing Subsequence

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

    blankyao 評論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 評論0 收藏0

  • leetcode 300. Longest Increasing Subsequence

    摘要：題目要求找到整數(shù)數(shù)組中最長的遞增子數(shù)組。該子數(shù)組可以為不連續(xù)的。如題目中例子所示，得到的最長子數(shù)組為。最后我們還需要遍歷一遍全部子數(shù)組的長度并獲得最大的長度。 題目要求 Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [...

    eechen 評論0 收藏0

  • leetcode-300-Longest Increasing Subsequence

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

    amc 評論0 收藏0

  • Longest Increasing Subsequence

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

    FullStackDeveloper 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<