資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中最長的遞增子序列
假設我們有一個無序的整數列表。我們需要找出最長的遞增子序列。所以，如果輸入是 [10,9,2,5,3,7,101,18]，那麼輸出將是 4，因為遞增子序列是 [2,3,7,101]
為解決此問題，我們將遵循以下步驟 -
- trail := 從長度為 0 到 nums - 1 的陣列，並用 0 填充它們
- 大小 := 0
- 對於 nums 中的 x
- i := 0，j := 大小
- while i 不等於 j
- mid := i + (j - i) / 2
- 如果 trails[mid] < x，則 i := mid + 1，否則 j := mid
- trails[i] := x
- 大小 := i + 1 和大小的最大值
- 返回大小
讓我們看看以下實施，以獲得更好的理解 -
示例
class Solution(object): def lengthOfLIS(self, nums): tails =[0 for i in range(len(nums))] size = 0 for x in nums: i=0 j=size while i!=j: mid = i + (j-i)//2 if tails[mid]< x: i= mid+1 else: j = mid tails[i] = x size = max(i+1,size) #print(tails) return size ob1 = Solution() print(ob1.lengthOfLIS([10,9,2,5,3,7,101,18]))
輸入
[10,9,2,5,3,7,101,18]
輸出
4
更新日期： 04-05-2020
3K+ 檢視次數
廣告