1035. 不相交的线
1. 题目
1035. 不相交的线
2. 解题思路
题目一看是求最值,那就可以考虑用DP来做。
核心点就是确定DP数组的含义以及状态转移方程:
- dp数组含义:dp[i][j],nums1 前 i 个数和 nums2 前 j 个数的最大连线数
dp[i][j] = dp[i - 1][j - 1] + 1;可以在这两个元素之间画一条线,所以当前的最大线数等于dp[i-1][j-1] + 1。即在之前的最优解上多加一条新线。- 无法直接连接当前元素,当前状态的最大线数应该是从前面的状态转移过来,选择
dp[i-1][j]或dp[i][j-1]中较大的那个值(即两个数组中前面的最优解)。
3. 代码
3.1. 注意事项
[!NOTE] 1、DP数组的大小
因为DP的含义是前N个数,所以前0个数相当于没有啥用,所以要获取到最后题目要求的结果那就是要dp[m][n],所以初始化大小要初始化为int[m + 1][n + 1]
[!NOTE] 2、for循环边界
还是根据DP数组的含义,需要到达m和n,所以for循环需要能够等于数组长度
[!NOTE] 3、为什么for循环里面用
nums1[i - 1] == nums2[j - 1]而不用nums[i]来判断
因为动态规划数组f[i][j]的下标从1开始,而nums1和nums2的数组下标是从0开始的。通过使用i-1和j-1来索引nums1和nums2,可以正确对齐两个数组的元素与动态规划表的状态。
3.2. 完整代码
class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int m = nums1.length;int n = nums2.length;if (m == 0 || n == 0) {return 0;}//dp数组含义:dp[i][j],nums1 前 i 个数和 nums2 前 j 个数的最大连线数int[][] dp = new int[m + 1][n + 1];//初始化base case 默认dp[0][0]为0,即前0个数的最大连线数是0for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; 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[m][n];}
}
相关文章:
1035. 不相交的线
1. 题目 1035. 不相交的线 2. 解题思路 题目一看是求最值,那就可以考虑用DP来做。 核心点就是确定DP数组的含义以及状态转移方程: dp数组含义:dp[i][j],nums1 前 i 个数和 nums2 前 j 个数的最大连线数dp[i][j] dp[i - 1][j …...
1.pytest基础知识(默认的测试用例的规则以及基础应用)
一、pytest单元测试框架 1)什么是单元测试框架 单元测试是指再软件开发当中,针对软件的最小单位(函数,方法)进行正确性的检查测试。 2)单元测试框架 java:junit和testing python:un…...
Linux常见查看文件命令
目录 一、cat 1.1. 查看文件内容 1.2. 创建文件 1.3. 追加内容到文件 1.4. 连接文件 1.5. 显示多个文件的内容 1.6. 使用管道 1.7. 查看文件的最后几行 1.8. 使用 -n 选项显示行号 1.9. 使用 -b 选项仅显示非空行的行号 二、tac 三、less 四、more 五、head 六、…...
初识 performance_schema:轻松掌握MySQL性能监控
什么是 performance_schema performance_schema 是 MySQL 5.8 版本的一个强大功能,它就像是一个内置的**“性能侦探”**,专门用来监控和分析 MySQL 服务器的资源消耗和等待情况。有了它,数据库管理员和开发者就能实时了解服务器的运行状态&a…...
linux下top命令查看和解释
怎么看top结果: top - 10:20:48 up 8 days, 14:07, 2 users, load average: 6.04, 5.82, 4.73 Tasks: 11099 total, 1 running, 10916 sleeping, 0 stopped, 1 zombie %Cpu(s): 8.9 us, 4.6 sy, 0.0 ni, 86.1 id, 0.1 wa, 0.0 hi, 0.3 si, 0.0 st K…...
换个手机IP地址是不是不一样?
在当今这个信息爆炸的时代,手机已经成为我们生活中不可或缺的一部分。而IP地址,作为手机连接网络的桥梁,也时常引起我们的关注。你是否曾经好奇,换个手机,IP地址会不会也跟着变呢?本文将深入探讨这个问题&a…...
【从计算机的发展角度理解编程语言】C、CPP、Java、Python,是偶然还是应时代的产物?
参考目录 前言什么是"computer"?计算机的大致发展历程计算机系统结构阶段(1946~1981)计算机网络和视窗阶段(1982~2007)复杂信息系统阶段(2008~today)人工智能阶段 越新的语言是越好的吗、越值得学习吗? 前言 最近读了 《Python语言程序设计基础》 这本书…...
《Google软件测试之道》笔记
介绍 GTAC:Google Test Automation Conference,Google测试自动化大会。 本书出版之前还有一本《微软测试之道》,值得阅读。 质量不是被测试出来的,但未经测试也不可能开发出有质量的软件。质量是开发过程的问题,而不…...
实战讲稿:Spring Boot整合MyBatis
文章目录 实战讲稿:Spring Boot整合MyBatis课程目标课程内容1. 创建员工映射器接口1.1 创建子包1.2 创建接口 2. 测试员工映射器接口2.1 自动装配员工映射器2.2 测试按标识符查询员工方法2.3 测试查询全部员工方法2.4 测试插入员工方法2.5 测试更新员工方法2.6 测试…...
基于深度学习的眼部疾病检测识别系统
温馨提示:文末有 CSDN 平台官方提供的学长 QQ 名片 :) 1. 项目简介 眼部疾病的早期诊断对于防止视力下降乃至失明至关重要。然而,专业的医疗资源分布不均,尤其是在偏远地区,人们很难获得专业的眼科医生提供的及时诊断服务。本系统…...
curl格式化json之jq工具?
jq 是一个轻量级的命令行工具,用于解析、操作和格式化 JSON 数据。它类似于 sed 或 awk,但专门用于处理 JSON 格式。使用 jq,你可以从复杂的 JSON 数据中提取所需的信息,格式化输出,进行数据筛选,甚至修改 …...
百收SEO蜘蛛池
百收SEO蜘蛛池 网站搜索排名上不去?SSL证书来帮忙! #SSL证书#网站优化#搜索引擎优化 谷歌蜘蛛石的话有非常多的一个重要性,首先的话就是能够提升我们网站的一个输入,尤其是对于我们百收SEO蜘蛛池新站来说,我们在做独立…...
(娱乐)魔改浏览器-任务栏图标右上角加提示徽章
一、目标: windows中,打开chromium,任务栏中会出现一个chromium的图标。我们的目标是给这个图标的右上角,加上"有1条新消息"的小提示图标,也叫徽章(badge)注意:本章节纯属娱乐,有需要…...
JVM相关
1.JVM内存区域 一个运行起来的java进程就是一个Java虚拟机,就需要从操作系统中申请一大块内存。 内存中会根据作用的不同被划分成不同的区域: (1)栈:存储的内容是代码在执行过程中,方法之间的调用关系&a…...
9.18 微信小程序开发笔记
如何获取英语单词的发音,使其能在小程序界面通过点击外发? 1.通过外界API获取(例如有道API) 不下载音频文件,每次需要时直接API获取发音,存储压力小。但是一般的API都有使用次数限制,在背单词…...
dpdk课程学习之练习笔记八(dpvs的了解)
只是看到这个,跟着流程做一下练习,了解这个东东是干啥的,再就是搭建环境,基于dpdk的环境,顺手也就练习dpdk的环境搭建了。 0:总结 1:知道了lvs能实现的功能,挺强大。 2࿱…...
Linux标准IO-系统调用详解
1.1 系统调用 系统调用(system call)其实是 Linux 内核提供给应用层的应用编程接口(API),是 Linux 应用层进入内核的入口。不止 Linux 系统,所有的操作系统都会向应用层提供系统调用,应用程序通…...
LeetCode004-两个有序数组的中位数-最优算法代码讲解
最有帮助的视频讲解 【LeetCode004-两个有序数组的中位数-最优算法代码讲解】 https://www.bilibili.com/video/BV1H5411c7oC/?share_sourcecopy_web&vd_sourceafbacdc02063c57e7a2ef256a4db9d2a 时间复杂度 O ( l o g ( m i n ( m , n ) ) ) O(log(min(m,n))) O(log(min(…...
Unity携程Coroutine用法
一.携程概述 官方的解释是,携程允许你可以在多个帧中执行任务。在Unity中,携程是一个可以暂停并在后续帧中从暂停处继续执行的方法。 二.携程写法 下面示例使用携程和Update打印前5帧的时间间隔,展示了携程的基础写法 using System.Colle…...
腾讯百度阿里华为常见算法面试题TOP100(5):子串、堆
之前总结过字节跳动TOP50算法面试题: 字节跳动常见算法面试题top50整理_沉迷单车的追风少年-CSDN博客_字节算法面试题 子串 560.和为K的子数组...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
