首页 > 编程语言 >代码随想录算法训练营第49天 | 300.最长递增子序列 、674. 最长连续递增序列 、718. 最长重复子数组

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

时间:2024-06-30 19:42:52浏览次数:28  
标签:nums max 递增 number 序列 最长 dp

300.最长递增子序列

今天开始正式子序列系列,本题是比较简单的,感受感受一下子序列题目的思路。
视频讲解:https://www.bilibili.com/video/BV1ng411J7xP
https://programmercarl.com/0300.最长上升子序列.html

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    const dp = new Array(nums.length).fill(1);
    let max = 1;
    for (let i=1;i<nums.length;i++) {
        for (let j=0;j<i;j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j]+1);
            }
            if (dp[i] > max) {
                max = dp[i];
            }
        }
    }

    return max;
};
  1. 最长连续递增序列

本题相对于昨天的动态规划:300.最长递增子序列 最大的区别在于“连续”。 先尝试自己做做,感受一下区别
视频讲解:https://www.bilibili.com/video/BV1bD4y1778v
https://programmercarl.com/0674.最长连续递增序列.html

比上一题简单
/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
 const dp = new Array(nums.length).fill(1);
    let max = 1;
    for (let i=1;i<nums.length;i++) {
        if (nums[i] > nums[i-1]) {
            dp[i] = dp[i-1] + 1;
        }
        if (dp[i] > max) {
            max = dp[i];
        }
    }

    return max;
};
  1. 最长重复子数组

稍有难度,要使用二维dp数组了
视频讲解:https://www.bilibili.com/video/BV178411H7hV
https://programmercarl.com/0718.最长重复子数组.html

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function(nums1, nums2) {
    const dp = new Array(nums1.length+1).fill(0).map(()=>new Array(nums2.length+1).fill(0));
    let max = 0;
     for (let i=1;i<=nums1.length;i++) {
        for (let j=1;j<=nums2.length;j++) {
            if (nums1[i-1] === nums2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            if (dp[i][j] > max) {
                max = dp[i][j];
            }
        }
     }

     return max;
};

标签:nums,max,递增,number,序列,最长,dp
From: https://www.cnblogs.com/yuanyf6/p/18276843

相关文章

  • AI数据分析013:根据时间序列数据生成动态条形图
    文章目录一、介绍二、输入内容三、输出内容一、介绍动态条形竞赛图(BarChartRace)是一种通过动画展示分类数据随时间变化的可视化工具。它通过动态条形图的形式,展示不同类别在不同时间点的数据排名和变化情况。这种图表非常适合用来展示时间序列数据的变化,能够直......
  • C语言 | Leetcode C语言题解之第187题重复的DNA序列
    题目:题解:#defineMAXSIZE769/*选取一个质数即可*/typedefstructNode{charstring[101];intindex;structNode*next;//保存链表表头}List;typedefstruct{List*hashHead[MAXSIZE];//定义哈希数组的大小}MyHashMap;List*......
  • 给定一个实数序列,设计一个最有效的算法,找到一个总和最大的区间
    这个问题是经典的最大子数组和问题,也称为Kadane算法。我们可以使用动态规划的方法来高效地解决它。以下是解决方案的C++实现:classSolution{public:vector<int>maxSubArray(vector<double>&nums){if(nums.empty())return{};doub......
  • python json反序列化为对象
    在Python中,将JSON数据反序列化为对象通常意味着将JSON格式的字符串转换为一个Python的数据结构(如列表、字典)或者一个自定义的类实例。虽然Python的标准库json模块不提供直接将JSON数据映射到类的实例的功能,但我们可以通过一些技巧来实现这个需求。以下是一个详细的示例,展示了如何......
  • 面试官:告诉我为什么static和transient关键字修饰的变量不能被序列化?
    一、写在开头在上一篇学习序列化的文章中我们提出了这样的一个问题:“如果在我的对象中,有些变量并不想被序列化应该怎么办呢?”当时给的回答是:不想被序列化的变量我们可以使用transient或static关键字修饰;transient关键字的作用是阻止实例中那些用此关键字修饰的的变量序列化;当......
  • Go自定义数据的序列化流程
    ......
  • Leetcode 力扣 128. 最长连续序列 (抖音号:708231408)
    给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。示例1:输入:nums=[100,4,200,1,3,2]输出:4解释:最长数字连续序列是[1,2,3,4]。它的长度为4。示例2:输入:nums=......
  • AcWing 5726. 连续子序列
    5726.连续子序列-AcWing题库01trie的不错的练习题。题目说了求一段连续子序列的异或和,因为异或有结合律,所以我们可以直接预处理一个前缀异或和,即\(a[l,r]=sum[r]\operatorname{xor}sum[l-1]\)。然后求一段异或和就变成了求任意两个\(sum\)的异或和,而这就可以用到0......
  • Day 28 | 491.递增子序列 、46.全排列、 47.全排列 II
    491.递增子序列本题和大家刚做过的90.子集II非常像,但又很不一样,很容易掉坑里。https://programmercarl.com/0491.递增子序列.html视频讲解:https://www.bilibili.com/video/BV1EG4y1h78v给你一个整数数组nums,找出并返回所有该数组中不同的递增子序列,递增子序列中至少有两......
  • 树的序列化笔记
    \(dfs\)序以\(DFS\)(先根遍历)⾸次访问顺序将节点重新排列。特征:每个顶点在序列中出现恰好⼀次(废话)⽗节点排在⼦节点前⾯(废话)每棵⼦树都占据序列的⼀个区间欧拉序记录\(DFS\)递归/回溯时依次经过的所有点。特征:每个点出现次数=度数(根多1次)相邻点深度差1\(LCA(x,y)=\)......