蓝桥杯入门即劝退(十七)最长重复子数组(dp问题)-创新互联
------持续更新蓝桥杯入门系列算法实例--------
成都创新互联致力于互联网网站建设与网站营销,提供网站设计制作、成都网站制作、网站开发、seo优化、网站排名、互联网营销、重庆小程序开发公司、公众号商城、等建站开发,成都创新互联网站建设策划专家,为不同类型的客户提供良好的互联网应用定制解决方案,帮助客户在新的全球化互联网环境中保持优势。如果你也喜欢Java和算法,欢迎订阅专栏共同学习交流!
你的点赞、关注、评论、是我创作的动力!
-------希望我的文章对你有所帮助--------
一、题目描述前言:今天又回顾了一部分之前写过的算法题,加深记忆和印象,不断思考总结才能够掌握算法题中的各种技巧和细节,失之毫厘谬以千里。今天的这道题目也挺有意思的,刚开始以为自己能够做出来,但总差点思路,研究一番后才醒悟。与你共享我的思考成果!
给两个整数数组 nums1
和 nums2
,返回两个数组中 公共的 、长度最长的子数组的长度 。
示例 1:
输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出:3 解释:长度最长的公共子数组是 [3,2,1] 。
示例 2:
输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] 输出:5
二、代码实现解题思路: 1、这题有些许类似前面题目中字符串最长公共前缀,但是总体更难一些,以为所求的子数组与子序列不同,在于必须是有序的。
2、例如数组 Array[8,4,7,6,4],其子数组必须是连续的,{8,4,6},{4,6}就不行,因为数组元素位置不可改变。
3、采用dp(动态规划)来完成,新建一个dp二维数组,且其大小为(A+1)*(B+1)A、B分别是两个数组的长度。
4、设置两个循环,对于两个数组中的元素遍历其比对,如果有相同位置的元素相同即dp[][]+1,最好手动去画一画,就能理解。(未赋值的元素默认是0)
5、最后,使用Math.max(),如果找到更长的数组长度,更新数据,最后return即可。
public int findLength(int[] nums1, int[] nums2) {
int Result=0;
int dp[][]=new int [nums1.length+1][nums2.length+1];
for(int i=1;i
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页名称:蓝桥杯入门即劝退(十七)最长重复子数组(dp问题)-创新互联
网页URL:http://myzitong.com/article/isidj.html