代码随想录-刷题第五十三天

1143. 最长公共子序列

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

思路:动态规划五步曲:

  1. dp[i][j]:长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列的长度为dp[i][j]

  2. 递推公式:

    主要是两种情况: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[i][j] = max(dp[i - 1][j], dp[i][j - 1])。

  3. 初始化:统一初始为0。

    先看看dp[i][0]应该是多少呢?

    test1[0, i - 1]和空串的最长公共子序列自然是0,所以dp[i][0] = 0;

    同理dp[0][j]也是0。

    其他下标都是随着递推公式逐步覆盖,初始为多少都可以,那么就统一初始为0。

  4. 遍历顺序:从递推公式,可以看出,有三个方向可以推出dp[i][j],如图:

    1143.最长公共子序列

    那么为了在递推的过程中,这三个方向都是经过计算的数值,所以要从前向后,从上到下来遍历这个矩阵。

  5. 举例推导dp数组

    以输入:text1 = “abcde”, text2 = “ace” 为例,dp状态如图:

    1143.最长公共子序列1

    最后红框dp[text1.length()][text2.length()]为最终结果。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] arr1 = text1.toCharArray();
        char[] arr2 = text2.toCharArray();
        int[][] dp = new int[arr1.length + 1][arr2.length + 1];
        
        for (int i = 1; i <= arr1.length; i++) {
            for (int j = 1; j <= arr2.length; j++) {
                if (arr1[i - 1] == arr2[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]);
                }
            }
        }
        return dp[arr1.length][arr2.length];
    }
}

1035. 不相交的线

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

思路:绘制一些连接两个数字 A[i] 和 B[j] 的直线,只要 A[i] == B[j],且直线不能相交!

直线不能相交,这就是说明在字符串A中找到一个与字符串B相同的子序列,且这个子序列不能改变相对顺序,只要相对顺序不改变,连接相同数字的直线就不会相交。

本题说是求最大的连线个数,其实本质上就是求两个数列最长公共子序列长度。

动态规划分析过程与上一题完全相同。

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

53. 最大子序和

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

思路:动态规划五步曲:

  1. dp[i]:包括下标i(以nums[i]为结尾)的最大连续子序列和为dp[i]。

  2. 递推公式:dp[i] = max(dp[i - 1] + nums[i], nums[i])

    dp[i]只有两个方向可以推出来:

    ① dp[i - 1] + nums[i],即:nums[i]加入当前连续子序列和

    ② nums[i],即:从头开始计算当前连续子序列和

    一定是取最大的。

  3. 初始化:dp[0] = nums[0]

  4. 遍历顺序:递推公式中dp[i]依赖于dp[i - 1]的状态,需要从前向后遍历。

  5. 举例推导dp数组

    输入:nums = [-2,1,-3,4,-1,2,1,-5,4],对应的dp状态如下: 53.最大子序和(动态规划)

    注意最后的结果可不是dp[nums.length - 1]! 而是dp[6]。

    在回顾一下dp[i]的定义:包括下标i(以nums[i]为结尾)的最大连续子序列和为dp[i]。

    那么要找最大的连续子序列,就应该找每一个i为终点的连续最大子序列。

    所以在递推公式的时候,可以直接选出最大的dp[i]。

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

贪心算法解法代码:

class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            // 取区间累计的最大值(相当于不断确定最大子序终止位置)
            res = Math.max(res, sum);
            // 相当于重置最大子序起始位置,因为遇到连续和为负数一定是拉低总和
            if (sum <= 0) {
                sum = 0;
            }
        }
        return res;
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java学习,一文掌握Java之SpringBoot框架学习文集(6)

&#x1f3c6;作者简介&#xff0c;普修罗双战士&#xff0c;一直追求不断学习和成长&#xff0c;在技术的道路上持续探索和实践。 &#x1f3c6;多年互联网行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &#x1f389;欢迎 &#x1f44d;点赞✍评论…

C语言可变参数输入

本博文源于笔者正在学习的可变参数输入&#xff0c;可变参数是c语言函数中的一部分&#xff0c;下面本文就以一个很小的demo演示可变参数的编写 问题来源 想要用可变参数进行多个整数相加 方法源码 #include<stdio.h> #include<stdlib.h> #include<stdarg.h…

10个提高 Python Web 开发效率的VS Code插件

VS Code具有灵活、便捷和丰富的可用插件库&#xff0c;是Web开发人员中非常受欢迎的代码编辑器。 本文介绍10个VS Code插件&#xff0c;它们可以提高你作为Web开发人员的工作效率。 1. Live Preview Live Preview插件支持在VS Code的小型浏览器中查看网站。因此&#xff0c;无…

【NI-DAQmx入门】LabVIEW中DAQmx同步

1.同步解释 1.1 同步基础概念 触发器&#xff1a;触发器是控制采集的命令。您可以使用触发器来启动、停止或暂停采集。触发信号可以源自软件或硬件源。 时钟&#xff1a;时钟是用于对数据采集计时的周期性数字信号。根据具体情况&#xff0c;您可以使用时钟信号直接控制数据采…

百度面经整理(2024最新)

百度 面经1 shiro的组件分布式一致性算法zookeeper那些能参与投票&#xff0c;leader能投票吗&#xff1f;netty零拷贝实现volatile&#xff0c;如何感知到变量变化的redis高可用http如何跨域&#xff1f;tcp如何长链接。http如何操作浏览器缓存。用过消息队列吗&#xff1f;…

vue前端开发自学demo-input标签数据双向绑定

vue前端开发自学demo-input标签数据双向绑定&#xff01;今天为大家 展示的内容是&#xff0c;前端开发常见的&#xff0c;form表单里面的&#xff0c;一些输入数据的元素&#xff0c;动态绑定数据的案例。比如input,以及checkbox的状态绑定案例。 首先&#xff0c;老规矩&…

Unity WebView 中文输入支持

使用版本&#xff1a;Vuplex 3D WebView for Windows v4.4&#xff1b; 测试环境&#xff1a;unity editor 2020.3.40f1c1、Windows&#xff1b; 1、打开脚本CanvasWebVie!wPrefab 2、找到_initCanvasPrefab方法&#xff0c;约略在459行附近 3、添加一行代码&#xff1a; …

大创项目推荐 深度学习手势检测与识别算法 - opencv python

文章目录 0 前言1 实现效果2 技术原理2.1 手部检测2.1.1 基于肤色空间的手势检测方法2.1.2 基于运动的手势检测方法2.1.3 基于边缘的手势检测方法2.1.4 基于模板的手势检测方法2.1.5 基于机器学习的手势检测方法 3 手部识别3.1 SSD网络3.2 数据集3.3 最终改进的网络结构 4 最后…

设计模式-策略模式+单例模式+工厂模式 减少 if else

目录 一. 需求一. 区分entity二. 接口三. 邮件发送类四. 邮件发送的聚合工厂类五. 模拟邮件发送 一. 需求 根据前台传入的code&#xff0c;后台发送不同平台的邮件&#xff0c;发送QQ邮件&#xff0c;163邮件&#xff0c;Gmail邮件等。 一. 区分entity public class MailKbn…

使用懒加载 + 零拷贝后,程序的秒开率提升至99.99%

目录 一、5秒钟加载一个页面的真相二、优化四步走1、“懒加载”2、线上显示 就读取一个文件&#xff0c;为什么会慢呢&#xff1f; 三、先从上帝视角&#xff0c;了解一下啥子是IO流四、写个栗子&#xff0c;测试一下1、通过字符输入流FileReader读取2、通过缓冲流BufferedRea…

Qt QPushButton按钮控件

文章目录 1 属性和方法1.1 文本1.2 图标1.3 样式表1.4 信号 2 实例2.1 布局2.2 添加图标2.3 添加样式表2.4 代码实现 1 属性和方法 按钮除了可以设置显示文本之外&#xff0c;还可以设置图标 1.1 文本 可以获取和设置按钮上显示的文本 // 获取和设置按钮的文本 QString tex…

Apache ActiveMQ RCE CNVD-2023-69477 CVE-2023-46604

漏洞简介 Apache ActiveMQ官方发布新版本&#xff0c;修复了一个远程代码执行漏洞&#xff0c;攻击者可构造恶意请求通过Apache ActiveMQ的61616端口发送恶意数据导致远程代码执行&#xff0c;从而完全控制Apache ActiveMQ服务器。 影响版本 Apache ActiveMQ 5.18.0 before 5.1…

四次挥手的详细过程以及个人见解

SYN同步SYN表示进行一个连接请求 ACK确认位ACK1确认有效ACKO确认无效 ack确认号&#xff0c;客户端的序列号(seq)1 seq序列号&#xff0c;序列号是随机生成的随机数 FIN表示断开连接并且会停止向服务端发数据 详细过程如图&#xff1a; 第一次:客户端向服务器发出关闭请求…

构建中国人自己的私人GPT

创作不易&#xff0c;请大家多鼓励支持。 在现实生活中&#xff0c;很多人的资料是不愿意公布在互联网上的&#xff0c;但是我们又要使用人工智能的能力帮我们处理文件、做决策、执行命令那怎么办呢&#xff1f;于是我们构建自己或公司的私人GPT变得非常重要。 先看效果 一、…

YOLOv8改进 | 检测头篇 | 利用DynamicHead增加辅助检测头针对性检测(四头版本)

一、本文介绍 本文给大家带来的改进机制是针对性的改进,针对于小目标检测增加P2层,针对于大目标检测增加P6层利用DynamicHead(原版本一比一复现,全网独一份,不同于网上魔改版本)进行检测,其中我们增加P2层其拥有更高的分辨率,这使得模型能够更好地捕捉到小尺寸目标的细节…

element ui el-table展示列表,结合分页+过滤功能

vueelement-ui实现的列表展示&#xff0c;列表分页&#xff0c;列表筛选功能 1&#xff0c;分页器 el-table模块下面是分页器代码 <el-pagination></el-pagination> <el-table></el-table> <!-- 分页器 --><div class"block" st…

IO进程线程day5

1.实现互斥机制 #include <head.h>char buf[128]; //全局数组&#xff0c;临界资源//1、创建一个互斥锁 pthread_mutex_t mutex;//定义分支线程 void *task(void *arg) {while(1){//3、获取锁资源pthread_mutex_lock(&mutex);printf("分支线程中&…

论文阅读《Generalizing Face Forgery Detection with High-frequency Features》

高频噪声分析会过滤掉图像的颜色内容信息。 本文设计了三个模块来充分利用高频特征&#xff0c; 1.多尺度高频特征提取模块 2.双跨模态注意模块 3.残差引导空间注意模块&#xff08;也在一定程度上体现了两个模态的交互&#xff09; SRM是用于过滤图像的高频噪声 输入的图…

AlexNet论文精读

1:该论文解决了什么问题&#xff1f; 图像分类问题 2&#xff1a;该论文的创新点&#xff1f; 使用了大的深的卷积神经网络进行图像分类&#xff1b;采用了两块GPU进行分布式训练&#xff1b;采用了Relu进行训练加速&#xff1b;采用局部归一化提高模型泛化能力&#xff1b;…

Linux 基于 rsync 实现集群分发脚本 xsync

一、rsync 简介 rsync&#xff08;remote synchronize&#xff09;是 Liunx/Unix 下的一个远程数据同步工具。它可以通过 LAN/WAN 快速同步多台主机间的文件和目录&#xff0c;并适当利用 rsync 算法&#xff08;差分编码&#xff09;以减少数据的传输。 rsync 算法并不是每一次…