蓝桥杯入门即劝退（十七）最长重复子数组（dp问题）
admin
2024-04-26 15:11:50
0次
------持续更新蓝桥杯入门系列算法实例--------
如果你也喜欢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相关内容
热门资讯
【NIFD季报】美元指数走势变...
今天分享的是：【NIFD季报】美元指数走势变数加大 人民币有望温和升值——2025年年度人民币汇率分...
技术门槛降为零，Manus反击...
文 | 字母AI 就在OpenAI宣布招聘OpenClaw创始人皮特·斯坦伯格（Peter Ste...
“春捂秋冻”有道理吗
“春捂秋冻”源自先秦时期的四时养生思想，以“春夏养阳，秋冬养阴”为理论基础，强调顺应“春生夏长，秋收...
从断崖调整到价值重生，谁活下来...
《投资者网》刘亮 2025年，是白酒行业最艰难的一年。 史上最严禁酒令落地、产量连续九年下滑、六成产...
消费行业步入关键转折点，基金经...
春节期间，有券商策略团队连续7天路演，也有基金经理“下乡”实地调研。节后买什么、怎么投是他们最关注的...
原创 整...
近年来，欧洲各国的政治风云变幻，曾经在全球拥有强大影响力的欧洲大国，如今在选举中频频将领导权交给那些...
基金公司春节前后密集为债基配备...
近期，多家公募基金集中发布旗下债券型基金的基金经理增聘公告，一批擅长股票投资的基金经理被“空降”到债...
聚焦｜舌尖消费引爆年味经济
春节假期，各地的传统年货与新潮餐饮交融，各色美食荟萃飘香，“舌尖上的经济”持续释放蓬勃活力，一道道新...
苏翊鸣夺金后火速官宣恋情，赛后...
北京时间2月18日晚，米兰冬奥会单板滑雪男子坡面障碍技巧决赛，苏翊鸣凭借第一滑82.41分摘得金牌，...
金价大涨！有商场1000克金条...
2月18日晚，国际贵金属价格持续走高，现货黄金再度站上5000美元/盎司，日内涨幅超2.5%。 金...
国际油价18日显著上涨
国际油价2月18日显著上涨。截至当天收盘，纽约商品交易所3月交货的轻质原油期货价格上涨2.86美元，...
马斯克：X平台的“为你推荐”功...
每经AI快讯，2月19日，马斯克称X平台的“为你推荐”功能可能推迟至本周末发布。 每日经济新闻
英伟达清仓Arm股份，套现超1...
2月18日消息，据彭博社报道，英伟达（NVIDIA）公司已经清仓了其对于Arm公司的最后持股。 根据...
原创 特...
近日，一条消息在能源圈掀起了不小的波澜。美国能源部长透露，中国已经购买了部分美国政府出售的委内瑞拉石...
基石资本张维：投资于每个时代的...
过去一年，牛市重启，科技领航。 正如我在2024年10月所说的那样，“9·24”的行情并不是一个反弹...
上线仅数月，亚马逊仓库机器人“...
来源：市场资讯 （来源：IT之家） IT之家 2 月 19 日消息，亚马逊在其仓库中部署了数十万机器...
原创 新...
正当家家户户沉浸在2026年马年春节的团圆喜庆里，大年初一凌晨，外汇市场却传来了重磅消息，离岸人民币...
别只会说“想开点” 学会有效陪...
当下，焦虑、抑郁、内耗等情绪困扰很常见，身边亲友可能正深陷其中——沉默寡言、回避社交、难以自拔。“加...
原创 俄...
在俄乌战争的谈判桌上，欧洲是否正悄然退居局外？在今年的慕尼黑安全会议上，中国代表团的一句直白表态，直...
原创 恒...
春节期间一家科技公司的产品发布，竟被包装成港股下跌的“元凶”，一场精心策划的舆论围猎正在浮出水面。 ...