本篇讲解四道子序列相关题目
1. 最长摆动子序列（No. 376）
题目
摆动序列是指相邻数字的差正负交替（不包括0）。子序列是指从序列中删除一部分数字，剩余的数字保持原来的顺序不变组成的数列。
给一串序列，求它的最长摆动子序列的长度。
思路
形象地，把序列点按顺序画在坐标图上并连接，摆动序列就是一个一上一下的折线图。因此我们只要留下每个上升的最高点以及每次下降的最低点，即可得到最长子序列。也就是只留下每次连续同方向变化的最后一个点。
算法
首先确定第一次变化方向，用一个变量last_is_up表示上一次的变化方向，1为上升，-1为下降。用另一个变量length存储当前子序列长度。
从第三个数开始，遍历每个数，如果这个数与前面的变化方向不一致（即连续两次上升或下降），则长度length加一，变化方向反向；否则不变。
最后返回length即为结果。
注意
注意序列前几个数可能相同，不能通过前两个数判断首次变化方向。
代码
class Solution:
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return len(nums)
last_is_up = None # 变化方向最初不能确定
length = 1
for i in range(1, len(nums)):
d = nums[i] - nums[i-1] # d是变化值
if last_is_up is None: # 先确定首次变化方向
if nums[i] != nums[i-1]:
last_is_up = 1 if d > 0 else -1
length += 1
elif d * last_is_up < 0: # 变化方向不一致
length += 1
last_is_up *= -1
return length
2. 最长连续递增子序列 （No.674）
题目
给一个序列，求最长连续递增子序列的长度
示例
Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3.
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4.
思路
从第二个元素往后扫，比上一个元素大则长度加一，否则清零重新累加。这个过程中长度的最大值即为所求
代码
class Solution:
def findLengthOfLCIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return len(nums)
ml = 1 # 最大长度
l=1 # 当前长度
for i in range(1, len(nums)):
if nums[i] > nums[i-1]: # 若递增，则长度加一
l += 1
else: # 否则当前长度置为1
ml = max(ml, l)
l=1
ml = max(ml, l)
return ml
3. 最长递增子序列 （No.300）
题目
给一个序列，求最长递增子序列的长度
思路
动态规划。定义一个状态函数length(k)，表示以第k个数为结尾的最长递增自序列的长度。length(1)=1,当k>1时，依次求length(k)，具体求法为：
遍历k之前的所有数，如第x个数，如果小于第k个数，则第k个数可以接在这个数之后，形成新的递增子序列，长度为length(x) + 1。所有这些长度中最长的即为length(k)。所有的length之中，最大的就是最长递增子序列的长度。
示例
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.
算法
用一个列表length表示上述状态函数。从前往后扫描序列，填充length列表。求法如下：
length(k) = max(length(x) + 1)
其中，x为前k-1个数中所有小于第k个数的位置
得到的length数组中，最大的数即为所求
代码
class Solution:
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return len(nums)
length = [1]
for i in range(1, len(nums)):
psb = 1 # 可能的长度
for j in range(i):
if nums[j] < nums[i]:
psb = max(psb, length[j] + 1) # 可能的长度中最大的
length.append(psb) # 填充length数组
return max(length)
4. 最长递增子序列数量 （No.673）
题目
求上述最长递增子序列的数量。其中，不同位置的相同数字组成的两个子序列算两个。
示例
Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.
思路
与上一题类似，只是除了用length表示以当前元素结尾的最长递增子序列的长度之外，另外用count表示这上的序列的个数，最后找出所有length为最大值的数对应count值之和。
算法
与上一题类似，用两个数组lengths和counts表示以第i个数为结尾的最长递增子序列的长度和数量。在更新lengths的同时，更新counts。counts的更新方法是：所有当前数字之前的lengths最大对应的counts之和即为当前counts。最后所有lengths最大的counts之和即为所求。
代码
class Solution(object):
def findNumberOfLIS(self, nums):
N = len(nums)
if N <= 1: return N
lengths = [0] * N #lengths[i] 表示以第i个数结尾的最长递增子序列的长度
counts = [1] * N #count[i] 表示以第i个数结尾的最长递增子序列的数量
for j, num in enumerate(nums):
for i in range(j):
if nums[i] < nums[j]:
if lengths[i] >= lengths[j]:
lengths[j] = 1 + lengths[i]
counts[j] = counts[i]
elif lengths[i] + 1 == lengths[j]:
counts[j] += counts[i]
longest = max(lengths)
return sum(c for i, c in enumerate(counts) if lengths[i] == longest)
网友评论