代码随想录算法训练营第52天 |300、674、718网站首页 学无止境

代码随想录算法训练营第52天 |300、674、718

somethingstrange 2024-06-27 12:01:03

简介代码随想录算法训练营第52天 |300、674、718

300. 最长递增子序列

题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例1：
输入： $n u m s = [10, 9, 2, 5, 3, 7, 101, 18]$
输出： $4$
示例2：
输入： $n u m s = [0, 1, 0, 3, 2, 3]$
输出： $4$
示例3：
输入： $n u m s = [7, 7, 7, 7, 7, 7, 7]$
输出： $1$

思路

子序列问题是动态规划中的经典问题，但我第一次做完全不知道应该咋写，直接上答案。
1、dp[i]的定义
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
2、状态转移方程
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列+1的最大值
dp[i] = max(dp[i],dp[j]+1)
3、dp[i]的初始化
每个都至少为1
4、遍历顺序
i从前到后，j从0到i-1

解法

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        for(int i = 0;i<dp.length;i++){
            for(int j = 0;j<i;j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res = 0;
        for(int i = 0;i<dp.length;i++){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

总结

本题是第一个子序列的动态规划应用，好好看，好好学。

674. 最长连续递增序列

题目描述

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。
连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
示例1：
输入： $n u m s = [1, 3, 5, 4, 7]$
输出： $3$
示例2：
输入： $n u m s = [2, 2, 2, 2, 2]$
输出： $1$

思路

1、dp[i]表示以下标i为结尾的连续递增子序列的长度为dp[i]
2、如果nums[i]>nums[i-1]则以i为结尾的连续递增子序列长度一定等于以i-1为结尾的连续递增子序列长度+1.
3、dp[i]初始化为1

解法

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        for(int i = 0;i<dp.length;i++){
            dp[i] = 1;
        }
        int res = 1;
        for(int i = 0;i<nums.length-1;i++){
            if(nums[i+1] > nums[i]){
                dp[i+1] = dp[i]+1;
            }
            res = res > dp[i+1] ? res : dp[i+1];
        }
        return res;
    }
}

总结

本题和上一题相比，区别在于必须要连续，那么其实就只需要比较nums[i]和nums[i-1]而不需要再遍历j了。

718. 最长重复子数组

题目描述

给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度。
示例1：
输入： $n u m s 1 = [1, 2, 3, 2, 1], n u m s 2 = [3, 2, 1, 4, 7]$
输出： $3$
示例2：
输入： $n u m s 1 = [0, 0, 0, 0, 0], n u m s 2 = [0, 0, 0, 0, 0]$
输出： $5$

思路

1、确定dp数组以及下标含义
dp[i][j]：表示以下标i-1为结尾的A和以下标j-1为结尾的B，最长重复子数组的长度为dp[i][j]
2、确定递推公式
当A[i-1]和B[j-1]相等的时候，dp[i][j] = dp[i-1][j-1]+1

解法

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int result = 0;
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        for(int i = 1;i<nums1.length+1;i++){
            for(int j = 1;j<nums2.length+1;j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                    result = Math.max(result,dp[i][j]);
                }
            }
        }
        return result;
    }
}