leetcode-300-Longest Increasing Subsequence

amc 發(fā)布于2019-07-30 17:36 / 3243人閱讀

摘要：本質找出最長的遞增子序列的長度，可以是不連續(xù)的。應用判斷滿足一定條件的子序列的最大長度，用動態(tài)數(shù)組加以處理。二分法確定滿足條件的位置。類似二分法查找元素，查找某種情況的子序列。

本質： 找出最長的遞增子序列的長度，可以是不連續(xù)的。

  用一個數(shù)組存儲 遞增子序列，遍歷原始數(shù)組，每增加一個數(shù)，往里添加到對應的順序，記錄他的位置，即為此數(shù)組的長度。
  成立的理由：每一個數(shù)添加以后，都有對應的子序列的長度，將它記錄即可，然后最后取一個最長的。

思考：數(shù)組作為記錄的作用，可以記錄滿足條件的數(shù)值，index可以作為索引，

  可以記錄子數(shù)組，從中獲取子數(shù)組的長度， 可以子數(shù)組修改子數(shù)組，加以覆蓋，修改，根據(jù)最后一個值判斷l(xiāng)ength。

應用： 判斷滿足一定條件的子序列的最大長度，用動態(tài)數(shù)組加以處理。

  二分法確定滿足條件的位置。
  思路： 將滿足條件的數(shù)值記錄在數(shù)組，然后每次新數(shù)值插入此數(shù)組，記錄下此時需要的信息。

類似： 二分法查找元素，查找某種情況的子序列。

class Solution:
    def lengthOfLIS(self, nums):
        length=len(nums)
        dp=[0]*length
        size=0
        for index,num in enumerate(nums):
            i,j=0,size
            while i!=j:
                m=(i+j)//2
                if dp[m]num:
                    j=m
                else:
                    i=m
                    break
            dp[i]=num
            size=max(size,i+1)
        return size
if __name__ == "__main__":
    nums = [10, 9, 2, 5, 3, 7,8,10,14,18,101,18,16,17,18]
    # nums=[3,1,4,1,5,9,2,6]
    print(len(nums))
    st = Solution()
    out=st.lengthOfLIS(nums)
    print(out)

GPU云服務器云服務器 Increasing Subsequence

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

轉載請注明本文地址：http://systransis.cn/yun/42303.html

LeetCode[300] Longest Increasing Subsequence

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

blankyao 2019-08-14 15:01 評論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 2019-08-19 11:13 評論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 2019-08-15 14:44 評論0 收藏0
[LintCode] Longest Increasing Subsequence

Problem Given a sequence of integers, find the longest increasing subsequence (LIS). You code should return the length of the LIS. Clarification Whats the definition of longest increasing subsequence?...

Flands 2019-08-14 14:22 評論0 收藏0
Longest Increasing Subsequence

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

FullStackDeveloper 2019-08-14 17:23 評論0 收藏0