您现在的位置是:首页 >其他 >代码随想录算法训练营day52 | 300.最长递增子序列,674. 最长连续递增序列,718. 最长重复子数组网站首页其他

代码随想录算法训练营day52 | 300.最长递增子序列,674. 最长连续递增序列,718. 最长重复子数组

小鲨鱼冲冲冲 2024-06-27 12:01:03
简介代码随想录算法训练营day52 | 300.最长递增子序列,674. 最长连续递增序列,718. 最长重复子数组

代码随想录算法训练营day52 | 300.最长递增子序列,674. 最长连续递增序列,718. 最长重复子数组


300.最长递增子序列

教程视频:https://www.bilibili.com/video/BV1ng411J7xP
在这里插入图片描述
在这里插入图片描述

解法一:动态规划

思路:
1、dp[i]含义:表示以nums[i]结尾的最长递增子序列的长度。
2、递推公式:dp[i]=Math.max(dp[j]+1,dp[i]);
3、dp数组初始化:全部初始化为1,dp[i]=1;
4、遍历顺序:外层 i 从前向后遍历,内层 j 正序倒序都可以。
5、打印验证。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int result = 1;//因为外层for不是从dp[0]开始遍历,考虑单个元素情况下输出1。
        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[j]+1,dp[i]);
                }
            }
            result=Math.max(result,dp[i]);
        }
        return result;
    }
}

674. 最长连续递增序列

教程视频:https://www.bilibili.com/video/BV1bD4y1778v
在这里插入图片描述

解法一:动态规划

思路:
1、dp[i]含义:表示以nums[i]结尾的最长连续递增子序列的长度。
2、递推公式:if(nums[i-1]<nums[i]) dp[i]=dp[i-1]+1;
3、dp数组初始化:全部初始化为1,dp[i]=1;
4、遍历顺序:外层 i 正序遍历,内层 无需遍历。
5、打印验证。

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        // Arrays.fill(dp,1);
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        int result = 1;
        for(int i=1;i<nums.length;i++){
            if(nums[i-1]<nums[i]){
                dp[i]=dp[i-1]+1;
            }
            result = Math.max(result,dp[i]);
        }
        return result;
    }
}

解法二:双指针法

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length==1)return 1;
        int maxLength=1;
        for(int left=0;left<nums.length;left++){
            int curLength=1;
            for(int right=left+1;right<nums.length;right++){
                if(nums[right-1]<nums[right]){
                    curLength++;
                }else{
                    break;
                }
            }
            maxLength=Math.max(maxLength,curLength);
        }
        return maxLength;
    }
}

718. 最长重复子数组

教程视频:https://www.bilibili.com/video/BV178411H7hV
在这里插入图片描述

解法一:动态规划

思路:
1、dp[i][j]含义:以下标 i - 1为 结尾的nums1,和以下标 j - 1 为结尾的nums2,最长重复子数组长度为dp[i][j]。 这里-1是为了简化初始化过程。
2、递推公式:两个数组指针始终对齐,需要同时-1if(nums2[j]==nums1[i]){ dp[i][j]=dp[i-1][j-1]+1; }
3、dp数组初始化:dp[0][j]和dp[i][0]无实际意义,为了保证递推有意义,全部初始化为0,dp[i][j]=0;
4、遍历顺序:外层 遍历nums1,内层遍历nums2。正序倒序无影响。
5、打印验证。

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

//空间压缩
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[] dp = new int[nums2.length+1];
        int maxLength=0;
        for(int i=1;i<=nums1.length;i++){
            for(int j=nums2.length;j>=1;j--){
                if(nums1[i-1]==nums2[j-1]){
                    dp[j]=dp[j-1]+1;
                }else {
                    dp[j] = 0;//这里不能漏,否则上一阶段状态不能完全刷新
                }
                maxLength=Math.max(maxLength,dp[j]);
            }
        }
        return maxLength;
    }
}

总结

1、子数组相关题目要从尾部元素去定义dp数组;
2、两个不同序列比较时,递推公式需要考虑指针对齐的问题;
3、718. 最长重复子数组中dp[i][j]表示索引为i-1和j-1处的最长公共子序列,可以简化初始化状态。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。