子序列问题

[递增的三元子序列](334. 递增的三元子序列 - 力扣（LeetCode）)

最好的：时间复杂度O(n),空间复杂度O(1)

方法1：转换成最长递增子序列问题 时间复杂度为O(nlogn)

方法2：遍历中间元素，维护两个数组 leftNum[] rightNum[] 左边元素的最小值和右边元素的最大值 时间O(n) 空间O(1)

方法3：贪心

思想：为了找到递增的三元子序列，第一个数和第二个数要尽可能的小，这样找到递增的三元子序列的可能性更大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean increasingTriplet(int[] nums) {
    int n = nums.length;
    if(n<3){
        return false;
    }
    int first = nums[0];
    int second = Integer.MAX_VALUE;
    for(int i = 1;i < n;i++){
        if(nums[i]>second){
            return true;
        }else if(nums[i]>first){
            second=nums[i];
        }else{
            first = nums[i];
        }
    }
    return false;
}

最长公共子序列

1
text1 = "abcde", text2 = "face"  最长公共子序列为3

解法：动态规划

dp[i][j]:表示text1的前i个字符和text2的前j个字符的最长公共子序列

最长连续序列 要求O(n)时间复杂度

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

解法：哈希表，只枚举不存在x-1的数 【对于x,若有x-1，则跳过， 避免x,x+1,x+2,…,x+y,对x+1等数进行枚举，没有意义】

最长连续递增序列

1
2
3
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3

最长递增子序列 LIS

最好时间复杂度O(nlogn)

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]

方法1： 动态规划

dp[i] 表示以nums[i] 结尾的最长序列长度

dp[i]= max(dp[j]) +1 [nums[j] < nums[i] && j<i]

时间复杂度O(n^2) 空间复杂度O(n)

方法2：贪心+二分查找

维护一个数组dp[i]: 表示长度为i的上升子序列的末尾元素的最小值

对原序列进行遍历，将每位元素二分插入 dp 中。

  • 如果 dp 中元素都比它小，将它插到最后
  • 否则，用它覆盖掉比它大的元素中最小的那个（第一个和它相等的）。

这种方法：dp序列不一定对，但长度是对的。

1
2
3
4
5
6
nums = [0,8,4,12,2]
dp = [0]
dp = [0 8]
dp = [0 4]
dp = [0 4 12]
dp = [0 2 12]

二分查找第一个比target大于等于的

最长递增子序列个数

1
2
3
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

动态规划

dp[i] 表示以nums[i] 结尾的最长上升子序列的长度

cnt[i] 表示以nums[i] 结尾的最长上升子序列的个数

最后，

端午将至，祝大家端午安康，美好接粽而至！

润下