算法随想录第五十二天打卡|300.最长递增子序列 , 674. 最长连续递增序列 , 718. 最长重复子数组

300.最长递增子序列 

今天开始正式子序列系列,本题是比较简单的,感受感受一下子序列题目的思路。 

视频讲解:动态规划之子序列问题,元素不连续!| LeetCode:300.最长递增子序列_哔哩哔哩_bilibili

代码随想录

思路

我本来想的是先创建一个列表作为结果,如果比列表上的右边的值大就添加,不然就把最右边的值改为nums[i],结果思路不对。

class Solution(object):def lengthOfLIS(self, nums):dp=[1]*len(nums)  #表示包含nums[i]的最大数列长度result=1for i in range(1,len(nums)):for j in range(i):if nums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)result=max(result,dp[i])return result

总结

学到了还有包含nums[i]这种条件的dp数组,这样dp[-1]就不一定是最终结果了。

 674. 最长连续递增序列 

本题相对于昨天的动态规划:300.最长递增子序列 最大的区别在于“连续”。 先尝试自己做做,感受一下区别  

视频讲解:动态规划之子序列问题,重点在于连续!| LeetCode:674.最长连续递增序列_哔哩哔哩_bilibili

代码随想录

class Solution(object):def findLengthOfLCIS(self, nums):dp=[1]*len(nums)  #表示包含nums[i]的最大序列长度result=1for i in range(1,len(nums)):if nums[i]>nums[i-1]:dp[i]=dp[i-1]+1result=max(result,dp[i])return result

总结

上一道题它的第二层for循环是因为不连续才要遍历之前的序列找最大值,而这题要连续的,所以如果是小于就直接归零。

 718. 最长重复子数组 

稍有难度,要使用二维dp数组了

视频讲解:动态规划之子序列问题,想清楚DP数组的定义 | LeetCode:718.最长重复子数组_哔哩哔哩_bilibili

代码随想录

class Solution(object):def findLength(self, nums1, nums2):dp=[[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]result=0for i in range(1,len(nums1)+1):for j in range(1,len(nums2)+1):if nums1[i-1]==nums2[j-1]:dp[i][j]=dp[i-1][j-1]+1result=max(result,dp[i][j])return result   

总结

这道题没写出来,其实这道题用暴力法也好写。

感觉这种方法我之前在哪里见过,求重复子序列嘛, 下次二维子序列就这么画图了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2774255.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【python】绘制春节烟花

一、Pygame库春节烟花示例 下面是一个使用Pygame实现的简单春节烟花效果的示例代码。请注意,运行下面的代码之前,请确保计算机上已经安装了Pygame库。 import pygame import random import math from pygame.locals import *# 初始化pygame pygame.ini…

基于麻雀优化算法优化XGBoost参数的优化控制策略

目录 一、背景 二、算法流程图 三、附录 一、背景 为提高极端梯度提升(Extreme Gradient Boosting, XGBoost)集成算法在时间预测、信贷风险预测、工件参数预测、故障诊断预测等方面中的准确性,研究者提出了一种改进的麻雀算法(…

【我与Java的成长记】之String类详解

系列文章目录 能看懂文字就能明白系列 C语言笔记传送门 Java笔记传送门 🌟 个人主页:古德猫宁- 🌈 信念如阳光,照亮前行的每一步 文章目录 系列文章目录🌈 *信念如阳光,照亮前行的每一步* 前言一、字符串构…

深入浅出:Golang的Crypto/SHA256库实战指南

深入浅出:Golang的Crypto/SHA256库实战指南 介绍crypto/sha256库概览主要功能应用场景库结构和接口实例 基础使用教程字符串哈希化文件哈希化处理大型数据 进阶使用方法增量哈希计算使用Salt增强安全性多线程哈希计算 实际案例分析案例一:安全用户认证系…

【芯片设计- RTL 数字逻辑设计入门 13 -- generate_for 和 for】

文章目录 generate_forverilog codetestbench code仿真波形 for 循环verilog code仿真波形错误小结 generate_for 在某个module中包含了很多相似的连续赋值语句,请使用generata…for语句编写代码,替代该语句,要求不能改变原module的功能。 …

假设检验的过程

假设检验的核心思想是小概率事件在一次实验中不可能发生,假设检验就是利用小概率事件的发生进行反正。学习假设检验,有几个概念不能跳过,原假设、p值 1.原假设 假设检验的基本过程如下: 1)做出一个假设H0&#xff0c…

IEC 104电力规约详细解读(三) - 遥信

1.功能简述 遥信,、即状态量,是为了将断路器、隔离开关、中央信号等位置信号上送到监控后台的信息。遥信信息包括:反应电网运行拓扑方式的位置信息。如断路器状态、隔离开关状态;反应一次二次设备工作状况的运行信息,如…

豪掷770亿!华为员工集体“分红大狂欢”:至少14万人受益

豪掷770亿!华为员工集体“分红大狂欢”:至少14万人受益 近日,华为宣布了其2023年度分红计划,总金额高达770.85亿元,预计至少将惠及14万员工。这一消息引发了广泛关注和热议,成为业界的一大亮点。作为中国领…

如何构建一个高效的微服务治理闭环管理体系

随着企业业务的快速发展和数字化转型的推进,微服务架构因其高度的灵活性、可扩展性和可维护性而逐渐成为主流。然而,微服务架构的复杂性也带来了诸多治理挑战。为了有效应对这些挑战,构建一个微服务治理闭环至关重要。 1、微服务治理概述 微…

vue的8大生命周期

第072个 查看专栏目录: VUE ------ element UI 专栏目标 在vue和element UI联合技术栈的操控下,本专栏提供行之有效的源代码示例和信息点介绍,做到灵活运用。 提供vue2的一些基本操作:安装、引用,模板使用,computed&a…

L3HCTF 2024

Check in 输入一个1就获得flag

幻兽帕鲁服务器搭建最简单新手教程,10秒钟自动部署,一键开服(腾讯云)

以下教程是基于腾讯云轻量应用服务器搭建的,非常简单,无论搭建幻兽帕鲁还是其他的游戏或者应用,都能以非常快的速度部署好。而且稳定流畅,功能丰富。 下面就来一起看看如何搭建吧。 幻兽帕鲁腾讯云服务器购买与一键部署教程&…

【Git版本控制 03】远程操作

目录 一、克隆远程仓库 二、推送远程仓库 三、拉取远程仓库 四、忽略特殊文件 五、命令配置别名 一、克隆远程仓库 Git是分布式版本控制系统,同⼀个Git仓库,可以分布到不同的机器上。怎么分布呢? 找⼀台电脑充当服务器的⻆⾊&#xff…

Java ieda 抽风报错导致无法正常启动项目

Java ieda 抽风报错导致无法正常启动项目 问题描述:新建模块运行时出现下面报错,不能正常启动程序。 Error:Module 你的项目名 production: java.lang.ClassCastException: class org.jetbrains.jps.builders.java.dependencyView.TypeRepr$PrimitiveT…

031-安全开发-JS应用WebPack打包器第三方库JQuery安装使用安全检测

031-安全开发-JS应用&WebPack打包器&第三方库JQuery&安装使用&安全检测 #知识点: 1、三方库-JQuery-使用&安全 2、打包器-WebPack-使用&安全 演示案例: ➢打包器-WebPack-使用&安全 ➢第三方库-JQuery-使用&安全 #为什么…

神经网络基本原理

神经网络是一门重要的机器学习技术。它是目前最为火热的研究方向–深度学习的基础。 神经网络是一种模拟人脑的神经网络以期能够实现类人工智能的机器学习技术。人脑中的神经网络是一个非常复杂的组织。成人的大脑中估计有1000亿个神经元之多。 1 介绍 下面是一个包含三个层…

大华智慧园区综合管理平台/emap/devicePoint RCE漏洞

免责声明:文章来源互联网收集整理,请勿利用文章内的相关技术从事非法测试,由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失,均由使用者本人负责,所产生的一切不良后果与文章作者无关。该…

解决Windows程序与Mysql连接报错 [WinError 10048] 通常每个套接字地址(协议/网络地址/端口)只允许使用一次

问题解析 这是因为mysql与程序之间已经耗尽了动态范围内的端口,链接的开关过于频繁 解决方法 打开注册表编辑器,进入目录计算机\HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Tcpip\Parameters点击顶部菜单编辑->新建,或是右…

用于电机控制应用的动态制动电阻器了解下

大型直流和交流电机驱动器通常提供用于安装制动电阻器的端子。这些电阻器是什么,它们如何减慢机器的速度?必须考虑哪些危险和注意事项? 机械能 任何运动中的机器都具有动能。这种能量是一些储存的势能被“倾倒”到电机或执行器中的结果&…

在线音乐服务器测试报告

一、项目背景 在线音乐服务器采用前后端分离的方法来实现,同时使用了数据库来存储相关的数据,同时将其部署到云服务器上。前端主要有个页面构成:登录页、音乐列表页、收藏音乐页等,以上模拟实现了最简单的在线音乐服务器。其结合后…