LeetCode300. 最長上升子序列

題目描述：

給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。
示例：
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。

動態(tài)規(guī)劃版
時間復(fù)雜度：O(n2)
空間復(fù)雜度：O(n)

Python代碼：

class Solution:
    def lengthOfLIS(self, nums):
        if nums == []:
            return 0
        cell = [1]*len(nums)
        for i in range(1,len(nums)):
            for j in range(i):
                if(nums[j] < nums[i]):
                    cell[i] = max(cell[i], cell[j]+1)
        return max(cell)

二分查找版

時間復(fù)雜度：O(nlogn)。二分搜索需要花費logn的時間且調(diào)用n次。
空間復(fù)雜度：O(n)，用了大小為 n的列表cell。

新建數(shù)組 cell，用于保存最長上升子序列。對原序列進行遍歷，將每位元素二分插入 cell 中。如果 cell 中元素都比它小，將它插到最后。否則，用它覆蓋掉比它大的元素中最小的那個。
總之，思想就是讓 cell 中存儲比較小的元素。這樣，cell 未必是真實的最長上升子序列，但長度是對的。

class Solution:
    def lengthOfLIS(self, nums):
        size = len(nums)
        if size<2:
            return size
        
        cell = [nums[0]]
        for num in nums[1:]:
            if num>cell[-1]:
                cell.append(num)
                continue
            
            l,r = 0,len(cell)-1
            while l<r:
                mid = l + (r - l) // 2
                if cell[mid]<num:
                    l = mid + 1
                else:
                    r = mid
            cell[l] = num
        return len(cell)

使用bisect模塊二分查找：

class Solution:
    def lengthOfLIS(self, nums):
        cell = [-float('inf')]
        for i in nums:
            if i > cell[-1]:
                cell += [i]
            else:
                cell[bisect.bisect_left(cell, i)] = i
        return len(cell) - 1

bisect模塊

bisect.bisect(seq, item, lo = 0, hi =len(list_name))

在有序列表seq中查找item的位置，并且返回其索引index，使得
插入item后序列依然保持有序。
有兩個可選參數(shù)lo和hi來縮小搜索范圍，lo的默認(rèn)值為0，hi的默
認(rèn)值為序列的長度。

>>> import bisect
>>> a = [3,4,6,7,9]
>>> b = bisect.bisect(a,8)
>>> b
4
>>> b = bisect.bisect(a,9.0)
>>> b
5
>>> b = bisect.bisect_left(a,9.0)
>>> b
4

bisect函數(shù)是bisect_right函數(shù)的別名，返回的索引是原序列相等元素之后的位置，新元素插入在舊元素的右邊。
bisect_left函數(shù)返回的索引是原序列中相等元素的位置，新元素插入在舊元素的左邊。

LeetCode673. 最長遞增子序列的個數(shù)

題目描述：

給定一個未排序的整數(shù)數(shù)組，找到最長遞增子序列的個數(shù)。
示例:
輸入: [1,3,5,4,7]
輸出: 2
解釋: 有兩個最長遞增子序列，分別是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

Python代碼：

class Solution:
    def findNumberOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        l = len(nums)
        dq = list()
        totals = list()
        for num in nums:
            index = len(dq)-1
            if not dq or num >dq[-1]:
                dq.append(num)
                totals.append(collections.defaultdict(int))
            else:
                while index >= 0 and dq[index]>= num:
                    index -= 1
                dq[index+1] = num
            if not index+1:
                totals[index+1][num] +=1
            else:
                totals[index+1][num] += sum([val for key,val in totals[index].items() if key <num ])
        return sum(totals[-1].values())