国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode 300. Longest Increasing Subsequence

eechen / 425人閱讀

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

題目要求 
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?

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

思路一：動態規劃

從動態規劃的角度來說，假設要計算以第i位為結尾所構成的最長遞增子數組，并且我們已經知道了第0位，第1位...第i-1位的任何一個值為最后一個數字時所能構成的最長子數組的長度。那么我們只需要從中找到值比當前小的值的下標，并且比較二者構成的子數組的長度，再從中獲得最大長度的遞增子數組，作為當前數組為最后一個值所構成的遞增子數組的最大長度。

最后我們還需要遍歷一遍全部子數組的長度并獲得最大的長度。

   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;
    }
思路二：大牛思路

這里附上一個解釋的非常好的文章，我根據其思路的實現如下：

    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;
    }


想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68789.html

相關文章

  • LeetCode[300] Longest Increasing Subsequence

    摘要：再用二分法找當前值應該在排好序的數組中的插入位置。因為要找的是最長的序列，所以每次將排好序的數組中替換成已經排好序的，會能保證得到的結果是最長的。保證升序相等也要替換這個值 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

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

    amc 評論0 收藏0

  • [leetcode]Longest Increasing Subsequence

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

    wow_worktile 評論0 收藏0

  • Longest Increasing Subsequence

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

    FullStackDeveloper 評論0 收藏0

發表評論

0條評論

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