目录

题目

解题思路

滑动窗口

​思路

代码

结果

DP

思路

代码

结果

今天下午休息&＃xff0c;合租的小伙伴陪女票出去玩了&＃xff0c;在家闲来无事就随便刷刷LeetCode每日一题吧&＃xff0c;结果推送给我的是一道难度中等的题&＃xff0c;这是在侮辱我的智商吗&＃xff1f;可后面的解题过程告诉我&＃xff0c;我智商不用它来侮辱也是负数。话不多说&＃xff0c;上题目。

题目

给两个整数数组 A 和 B &＃xff0c;返回两个数组中公共的、长度最长的子数组的长度。示例&＃xff1a;输入&＃xff1a;
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出&＃xff1a;3
解释&＃xff1a;
长度最长的公共子数组是 [3, 2, 1] 。提示&＃xff1a;
1 <&＃61; len(A), len(B) <&＃61; 1000
0 <&＃61; A[i], B[i] <100

 

解题思路

一看到这题&＃xff0c;我生锈的脑子第一反应就是暴力暴力暴力&＃xff0c;暴力的时间复杂度为O(n3)&＃xff0c;最后的提交结果也毫无意外地超时了。

言归正传&＃xff0c;再仔细阅读了一下题目&＃xff0c;“公共的”、“长度最长的”这几个字眼再结合本题&＃xff0c;不就在暗示我们用滑动窗口嘛。

滑动窗口

先上1张GIF图便于理解

DP

做完之后看了下题解&＃xff0c;发现也可以用动态规划&＃xff0c;而且这题用动态规划做还挺简单的&＃xff0c;状态转移方程简单得一腿。

思路

令 dp[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀&＃xff0c;那么答案即为所有 dp[i][j] 中的最大值。如果 A[i] &＃61;&＃61; B[j]&＃xff0c;那么 dp[i][j] &＃61; dp[i &＃43; 1][j &＃43; 1] &＃43; 1&＃xff0c;否则 dp[i][j] &＃61; 0。&＃xff08;这里借用了 Python 表示数组的方法&＃xff0c;A[i:] 表示数组 A 中索引 i 到数组末尾的范围对应的子数组。&＃xff09;

考虑到这里 dp[i][j] 的值从 dp[i &＃43; 1][j &＃43; 1] 转移得到&＃xff0c;所以我们需要倒过来&＃xff0c;首先计算 dp[len(A) - 1][len(B) - 1]&＃xff0c;最后计算 dp[0][0]。

以题目中的输入为例

A: [1,2,3,2,1]
B: [3,2,1,4,7]

状态转移方程为&＃xff1a;

若 A[i] !&＃61; B[j] &＃xff0c; dp[i][j] &＃61; 0
若 A[i] &＃61;&＃61; B[j] &＃xff0c; dp[i][j] &＃61; dp[i&＃43;1][j&＃43;1] &＃43; 1

动态规划矩阵如下表所示&＃xff1a;

结果即为矩阵中的最大值3

代码

public int findLength(int[] A, int[] B) { //动态规划int n &＃61; A.length, m &＃61; B.length;int[][] dp &＃61; new int[n &＃43; 1][m &＃43; 1];int ans &＃61; 0;for (int i &＃61; n - 1; i >&＃61; 0; i--) {for (int j &＃61; m - 1; j >&＃61; 0; j--) {dp[i][j] &＃61; A[i] &＃61;&＃61; B[j] ? dp[i &＃43; 1][j &＃43; 1] &＃43; 1 : 0;ans &＃61; Math.max(ans, dp[i][j]);}}return ans;}

结果

————————————————————————————————————————

烦躁啊&＃xff0c;被疫情搞得左右为难&＃xff0c;不知道怎么选择&＃xff0c;到底出国还是国内还是HK还是工作&＃xff0c;办CAS又被学校卡了&＃xff0c;说要提供之前KCL Summer Course的CEFR/RQF Level证明&＃xff0c;没有证明也要提供没有证明的证明&＃xff0c;英国人办事真的死板&＃xff0c;呵呵哒。。