六大算法之动态规划_动态规划100题

六大算法之动态规划_动态规划100题在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足:nums1[i] == nums2[j]且绘制的直线不与任何其他连线(非水平线)相交。请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。以这种方法绘制线条,并返回可以绘制的最大连线数。示例 1:输入:nums1 = [1,4,2], nums2 = [1,2,4]输出:2解释:可以画出两条不交叉的

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足:

nums1[i] == nums2[j]
且绘制的直线不与任何其他连线(非水平线)相交。
请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。

以这种方法绘制线条,并返回可以绘制的最大连线数。

示例 1:


输入:nums1 = [1,4,2], nums2 = [1,2,4]
输出:2
解释:可以画出两条不交叉的线,如上图所示。 
但无法画出第三条不相交的直线,因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
示例 2:

输入:nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出:3
示例 3:

输入:nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出:2
 

提示:

1 <= nums1.length <= 500
1 <= nums2.length <= 500
1 <= nums1[i], nums2[i] <= 2000

动态规划

const int N = 2010;
const int M = 510;
int Hash[N];
int f[M][M] = { 
   0};
class Solution { 
   
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) { 
   
        int n = nums1.size(),m = nums2.size();
        memset(Hash,0,sizeof Hash);
        for(int j = 1;j <= m;j ++){ 
   
            Hash[nums2[j - 1]] = j;
            for(int i = 1;i <= n;i ++){ 
   
                f[i][j] = f[i - 1][j];
                if(Hash[nums1[i - 1]] != 0){ 
   
                    f[i][j] = max(f[i][j],f[i - 1][Hash[nums1[i - 1]] - 1] + 1);
                }
            }
        }
        return f[n][m];
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169069.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • django drf jwt_django登录验证

    django drf jwt_django登录验证前言带着问题学习是最有目的性的,我们先提出以下几个问题,看看通过这篇博客的讲解,能解决问题吗?什么是JWT?为什么要用JWT?它有什么优势?JWT的认证流程是怎样的?JWT的工作原理?我们

  • 软件类网站源码(诱导类源码)

    /**====================================================================*LicensedtotheApacheSoftwareFoundation(ASF)underone*ormorecontributorlicenseagreements.SeetheNOTICEfile

  • jQuery 模板 tmpl 用法「建议收藏」

    jQuery 模板 tmpl 用法「建议收藏」昨晚无意中发现一个有趣的jQuery插件.tmpl(),其文档在这里。官方解释对该插件的说明:将匹配的第一个元素作为模板,render指定的数据,签名如下:.tmpl([data,][options])其中参数data的用途很明显:用于render的数据,可以是任意js类型,包括数组和对象。options一般情况下都是

  • jdk和jvm区别_java中集合和数组的区别

    jdk和jvm区别_java中集合和数组的区别最近翻看了java线程相关的东西,书中有一边专门讲到java内存模型,读完之后边回想起java虚拟机模型,那时心中便在思考java内存模型(以下简称jmm)和java虚拟机模型(以下简称jvm)之间的关系,下面将详细讲述。一jvm结构jvm的内部结构如下图所示,这张图很清楚形象的描绘了整个JVM的内部结构,以及各个部分之间的交互和作用。1ClassLoader(类加载器)就是…

  • cmd u盘修复命令_cmd命令提示符怎么打开

    cmd u盘修复命令_cmd命令提示符怎么打开U盘打不开,也无法格式化运行CMD,再输入CHKDSKG:/F(这里的G:就是你要修复的盘符)操作完后,u盘一切恢复正常

  • mysql之模糊查询的方法

    mysql之模糊查询的方法想起Mysql模糊查询正常情况下我们想到的一般都是like,但是使用like,格式正确了效率很快,当然这是在数据量比较小的情况下,问题是在数据量小的时候,不容易看出查询的效率,但在数据量达到百万级,千万级的时mysql查询的效率是很关键的,也是很重要的。一、一般情况下like模糊查询的写法:这个SQL语句,如果用explain解释的话,我们很容易就能发觉它是没有走索引搜索,而是对…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号