代码随想录算法训练营第四十三天 | leetcode:最长递增子序列,最长连续递增序列 ,最长重复子数组

300. 最长递增子序列

解题方法

  1. dp数组的含义:dp[i]:表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
  2. 状态转移方程:if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)
    位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
    注意这里不是要dp[i] 与 dp[j] + 1进行比较,而是我们要取dp[j] + 1的最大值
  3. 初始化dp数组:每一个i,对应的dp[i](即最长递增子序列)起始大小至少都是1.所以dp数组都需要初始化为1.
  4. 遍历顺序:i依赖于j, 而j<i 所以遍历顺序是从前往后。

code

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function lengthOfLIS($nums) {
        $len = count($nums);
        if($len == 1) return $len;
        $dp = array_fill(0,$len,1);
        $result = 0;
        for($i = 1; $i < $len; $i++){
            for($j = 0; $j < $i; $j++){
                if($nums[$j] < $nums[$i]){
                    $dp[$i] = max($dp[$i], $dp[$j] + 1);
                }
            }
            //收集dp数值里面最大的值
            if($dp[$i] > $result) $result = $dp[$i];
        }
        return $result;
    }
}

复杂度

时间复杂度

O(n^2)

空间复杂度

O(n)

674. 最长连续递增序列

解题方法

  1. dp数组的含义:dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]
  2. 确定递推公式:dp[i] = dp[i - 1] + 1;
    如果 nums[i] > nums[i - 1],那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1
  3. 初始化dp数组:以下标i为结尾的连续递增的子序列长度最少也应该是1,即就是nums[i]这一个元素。
    所以dp[i]应该初始1;
  4. 遍历顺序:dp[i + 1]依赖dp[i],所以一定是从前向后遍历。

code

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findLengthOfLCIS($nums) {
        $len = count($nums);
        if($len == 1) return $len;
        $dp = array_fill(0,$len,1);
        $res = 1;
        for($i = 1; $i < $len; $i++){
            if($nums[$i] > $nums[$i-1]){
                $dp[$i] = $dp[$i-1] + 1;
            }
            //收集dp数值里面最大的值
            if($dp[$i] > $res) $res = $dp[$i];
        }
        return $res;
    }
}

复杂度

时间复杂度

O(n)

空间复杂度

O(n)

718. 最长重复子数组

解题方法

  1. dp数组的含义:dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。
    (特别注意: “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 )
  2. 确定递推公式:dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。
    即当A[i - 1] 和B[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;
    根据递推公式可以看出,遍历i 和 j 要从1开始!
  3. 初始化dp数组:dp[i][0] 和dp[0][j]其实都是没有意义的!所以都初始化为0。其他值,因为会被覆盖,所以统一初始化为0
  4. 遍历顺序:外层for循环遍历nums1,内层for循环遍历nums2。

code

class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Integer
     */
    function findLength($nums1, $nums2) {
        $dp = [];
        $len1 = count($nums1);
        $len2 = count($nums2);
        //因为递推公式含义是i-1结尾,j-1结尾,所以循环要<=len不然遍历不到最后一个元素
        for($i = 0; $i <= $len1; $i++){
            for($j = 0; $j <= $len2; $j++){
                $dp[$i][$j] = 0;
            }
        }
        $res = 0;
        for($i = 1; $i <= $len1; $i++){
            for($j = 1; $j <= $len2; $j++){
                if($nums1[$i-1] == $nums2[$j-1]){
                    $dp[$i][$j] = $dp[$i-1][$j-1] + 1;
                }
                if($dp[$i][$j] > $res) $res = $dp[$i][$j];
            }
        }
        //print_r($dp);
        return $res;
    }
}

复杂度

时间复杂度

O(n × m),n 为nums1长度,m为nums2长度

空间复杂度

O(n × m)

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!