代码随想录算法训练营第五十三天| 1143.最长公共子序列 ,1035.不相交的线,53. 最大子序和 动态规划

本文主要是介绍代码随想录算法训练营第五十三天| 1143.最长公共子序列 ,1035.不相交的线,53. 最大子序和 动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目与题解

1143.最长公共子序列

题目链接:1143.最长公共子序列

代码随想录题解:​​​​​​​1143.最长公共子序列

视频讲解:动态规划子序列问题经典题目 | LeetCode:1143.最长公共子序列_哔哩哔哩_bilibili

解题思路:

        一开始试图用四层循环暴力法来做,就超时了。

看完代码随想录之后的想法 

        这里主要是dp定义跟前面有点不一样,随之的递推公式也不一样。

        dp[i][j]:长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j],所以最后得到的公共子序列不一定要包含text1[i-1]和text2[i-1]。

        递推公式有两大情况: text1[i - 1] 与 text2[j - 1]相同,text1[i - 1] 与 text2[j - 1]不相同

如果text1[i - 1] 与 text2[j - 1]相同,那么找到了一个公共元素,所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 与 text2[j - 1]不相同,那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列,取最大的。

dp的第一行和第一列分别表示text1或text2和空字符串的最长公共子序列,必然初始化为0。

class Solution {public int longestCommonSubsequence(String text1, String text2) {int[][] dp = new int[text1.length()+1][text2.length()+1];int result = 0;for (int i = 1; i < text1.length()+1; i++) {for (int j = 1; j < text2.length()+1; j++) {if (text1.charAt(i-1) == text2.charAt(j-1)) {dp[i][j] = dp[i-1][j-1]+1;} else {dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}result = Math.max(result, dp[i][j]);}}return result;}
}

遇到的困难

        序列和连续序列的计算会有很多不一样,子序列要考虑的可能性更多。

1035.不相交的线

题目链接:1035.不相交的线

代码随想录题解:​​​​​​​1035.不相交的线

视频讲解:动态规划之子序列问题,换汤不换药 | LeetCode:1035.不相交的线_哔哩哔哩_bilibili

解题思路:

        没有思路看答案。

看完代码随想录之后的想法 

        直线不能相交,这就是说明在字符串A中 找到一个与字符串B相同的子序列,且这个子序列不能改变相对顺序,只要相对顺序不改变,链接相同数字的直线就不会相交。本题说是求绘制的最大连线数,其实就是求两个字符串的最长公共子序列的长度!        

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];int result = 0;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;} else {dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}result = Math.max(result, dp[i][j]);}}return result;}
}

遇到的困难

        题目翻译成最大相同子序列有点困难。

53. 最大子序和

题目链接:​​​​​​​53. 最大子序和

代码随想录题解:53. 最大子序和

视频讲解:看起来复杂,其实是简单动态规划 | LeetCode:53.最大子序和_哔哩哔哩_bilibili

解题思路:

        dp定义:对于nums[0]-nums[i]的序列,其子序列包含nums[i]时,最大子序和的值。

        递推公式:因为要求的是连续序列的和,所以可以根据dp[i-1]和nums[i]推出dp[i]的值。如果dp[i-1]+nums[i] > nums[i],说明nums[i]可以纳入dp[i-1]的子序列,dp[i]=dp[i-1]+nums[i] ,否则从nums[i]开始开启一个新的序列,dp[i]=nums[i]。

        初始化dp[0]为nums[0], 从前往后遍历即可。

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

看完代码随想录之后的想法 

        因为dp的依赖关系是只有前后两个相关,所以可以简化dp的空间占用。

//因为dp[i]的递推公式只与前一个值有关,所以可以用一个变量代替dp数组,空间复杂度为O(1)
class Solution {public int maxSubArray(int[] nums) {int res = nums[0];int pre = nums[0];for(int i = 1; i < nums.length; i++) {pre = Math.max(pre + nums[i], nums[i]);res = Math.max(res, pre);}return res;}
}

遇到的困难

        一开始result没有初始化为dp[0],而是初始化为Interger.MIN_VALUE,导致数组只有一个数字时返回的结果不对,还是要维持一下result的定义,提前初始化为dp[0]才对。

今日收获

        dp真是千变万化,思路需要非常清晰了。子序列的题目有点难。

这篇关于代码随想录算法训练营第五十三天| 1143.最长公共子序列 ,1035.不相交的线,53. 最大子序和 动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/944984

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL