数组 c++ 动态规划 + 滚动数组优化 附Java代码"/>
力扣第718题 最长重复子数组 c++ 动态规划 + 滚动数组优化 附Java代码
题目
718. 最长重复子数组
中等
相关标签
数组 二分查找 动态规划 滑动窗口 哈希函数 滚动哈希
给两个整数数组 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 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100
思路和解题方法
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
:创建一个二维数组dp
,用于记录最长公共子序列的长度。其中,第一维表示nums1
数组的长度加1,第二维表示nums2
数组的长度加1,初始值为0。int ans = 0;
:初始化最长公共子序列的长度为0。for (int i = 1; i <= nums1.size(); i++)
:从第二个元素开始遍历nums1
数组。for (int j = 1; j <= nums2.size(); j++)
:从第二个元素开始遍历nums2
数组。if (nums1[i - 1] == nums2[j - 1])
:如果当前元素相等,表示在最长公共子序列中,更新最长公共子序列的长度。此处的i-1
和j-1
是因为dp
数组从下标1开始计算,而nums1
和nums2
数组从下标0开始计算。dp[i][j] = dp[i - 1][j - 1] + 1;
:如果当前元素相等,在最长公共子序列的基础上再加1,更新最长公共子序列的长度。if (dp[i][j] > ans) ans = dp[i][j];
:更新最长公共子序列的长度。return ans;
:返回最长公共子序列的长度。
复杂度
时间复杂度:
O(n*m)
时间复杂度为O(n*m),其中n和m分别是给定数组nums1和nums2的长度。这是因为代码使用了两个嵌套的for循环来遍历nums1和nums2数组,对于每个元素的比较和更新操作都需要常数时间。
空间复杂度
O()
空间复杂度为O(n*m),其中n和m分别是给定数组nums1和nums2的长度。这是因为代码创建了一个二维数组dp,用于记录最长公共子序列的长度。dp数组的大小为(nums1.size() + 1) * (nums2.size() + 1),占用的空间与输入数组的大小成正比。
c++ 代码
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) { // 定义一个函数,接收两个vector<int>类型的参数nums1和nums2,返回一个int类型的值vector<vector<int>> dp(nums1.size()+1,vector<int> (nums2.size()+1,0)); // 创建一个大小为(nums1.size()+1)*(nums2.size()+1)的二维vector dp,用于存储最长公共子数组的长度,默认初值为0int ans = 0; // 初始化最长公共子数组长度为0for(int i = 1;i<=nums1.size();i++) // 遍历nums1,从第一个元素到最后一个元素for(int j = 1;j<=nums2.size();j++) // 遍历nums2,从第一个元素到最后一个元素{if(nums1[i-1] == nums2[j-1]) // 如果nums1[i-1]等于nums2[j-1],则可以将nums1[i-1]加入到最长公共子数组中dp[i][j] = dp[i-1][j-1] + 1; // 更新dp[i][j]的值,dp[i][j]表示以nums1[i-1]和nums2[j-1]结尾的最长公共子数组的长度if(dp[i][j]>ans) ans = dp[i][j]; // 更新最长公共子数组的长度}return ans; // 返回最长公共子数组的长度}
};
c++ 滚动数组 优化空间复杂度
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
:创建一个二维数组dp
,用于记录最长公共子序列的长度。其中,第一维表示nums1
数组的长度加1,第二维表示nums2
数组的长度加1,初始值为0。int ans = 0;
:初始化最长公共子序列的长度为0。for (int i = 1; i <= nums1.size(); i++)
:从第二个元素开始遍历nums1
数组,因为需要与上一个元素比较。for (int j = 1; j <= nums2.size(); j++)
:从第二个元素开始遍历nums2
数组,因为需要与上一个元素比较。if (nums1[i - 1] == nums2[j - 1])
:如果当前元素相等,表示在最长公共子序列中,更新最长公共子序列的长度。此处的i-1
和j-1
是因为dp
数组从下标1开始计算,而nums1
和nums2
数组从下标0开始计算。dp[i][j] = dp[i - 1][j - 1] + 1;
:如果当前元素相等,在最长公共子序列的基础上再加1,更新最长公共子序列的长度。if (dp[i][j] > ans) ans = dp[i][j];
:更新最长公共子序列的长度。return ans;
:返回最长公共子序列的长度。
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {// 创建一个二维数组dp,用于记录最长公共子序列长度vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0)); int ans = 0; // 初始化最长公共子序列长度为0for (int i = 1; i <= nums1.size(); i++) { // 遍历nums1数组for (int j = 1; j <= nums2.size(); j++) { // 遍历nums2数组if (nums1[i - 1] == nums2[j - 1]) { // 如果当前元素相等,表示在最长公共子序列中dp[i][j] = dp[i - 1][j - 1] + 1; // 更新最长公共子序列的长度}if (dp[i][j] > ans) ans = dp[i][j]; // 更新最长公共子序列的长度}}return ans; // 返回最长公共子序列的长度}
};
Java双代码
- 一动态规划:
- 定义一个函数findLength,接收两个int类型数组nums1和nums2,返回一个int类型的值。
- 初始化最长公共子数组长度为0。
- 创建一个大小为(nums1.length+1)*(nums2.length+1)的二维数组dp,用于存储最长公共子数组的长度,默认初值为0。
- 遍历nums1和nums2,从第一个元素到最后一个元素。如果nums1[i-1]等于nums2[j-1],则可以将nums1[i-1]加入到最长公共子数组中。此时,更新dp[i][j]的值,dp[i][j]表示以nums1[i-1]和nums2[j-1]结尾的最长公共子数组的长度。比较dp[i][j]和result的大小关系,更新最长公共子数组的长度。
- 最后,返回最长公共子数组的长度。
- 二滚动数组:
- 定义一个函数findLength,接收两个int类型数组nums1和nums2,返回一个int类型的值。
- 初始化最长公共子数组长度为0。
- 创建一个大小为nums2.length+1的一维数组dp,用于存储最长公共子数组的长度,默认初值为0。
- 遍历nums1和nums2,从第一个元素到最后一个元素。如果nums1[i-1]等于nums2[j-1],则可以将nums1[i-1]加入到最长公共子数组中。此时,更新dp[j]的值,dp[j]表示以nums1[i-1]和nums2[j-1]结尾的最长公共子数组的长度。比较dp[j]和result的大小关系,更新最长公共子数组的长度。如果nums1[i-1]不等于nums2[j-1],则以nums1[i-1]和nums2[j-1]结尾的最长公共子数组长度为0。
- 最后,返回最长公共子数组的长度。
//一 :动态规划
class Solution {public int findLength(int[] nums1, int[] nums2) { // 定义一个函数,接收两个int类型数组nums1和nums2,返回一个int类型的值int result = 0; // 初始化最长公共子数组长度为0int[][] dp = new int[nums1.length + 1][nums2.length + 1]; // 创建一个大小为(nums1.length+1)*(nums2.length+1)的二维数组 dp,用于存储最长公共子数组的长度,默认初值为0for (int i = 1; i < nums1.length + 1; i++) { // 遍历nums1,从第一个元素到最后一个元素for (int j = 1; j < nums2.length + 1; j++) { // 遍历nums2,从第一个元素到最后一个元素if (nums1[i - 1] == nums2[j - 1]) { // 如果nums1[i-1]等于nums2[j-1],则可以将nums1[i-1]加入到最长公共子数组中dp[i][j] = dp[i - 1][j - 1] + 1; // 更新dp[i][j]的值,dp[i][j]表示以nums1[i-1]和nums2[j-1]结尾的最长公共子数组的长度result = Math.max(result, dp[i][j]); // 更新最长公共子数组的长度}}}return result; // 返回最长公共子数组的长度}
}// 二: 滚动数组
class Solution {public int findLength(int[] nums1, int[] nums2) { // 定义一个函数,接收两个int类型数组nums1和nums2,返回一个int类型的值int[] dp = new int[nums2.length + 1]; // 创建一个大小为nums2.length+1的一维数组 dp,用于存储最长公共子数组的长度,默认初值为0int result = 0; // 初始化最长公共子数组长度为0for (int i = 1; i <= nums1.length; i++) { // 遍历nums1,从第一个元素到最后一个元素for (int j = nums2.length; j > 0; j--) { // 遍历nums2,从最后一个元素到第一个元素if (nums1[i - 1] == nums2[j - 1]) { // 如果nums1[i-1]等于nums2[j-1],则可以将nums1[i-1]加入到最长公共子数组中dp[j] = dp[j - 1] + 1; // 更新dp[j]的值,dp[j]表示以nums1[i-1]和nums2[j-1]结尾的最长公共子数组的长度result = Math.max(result, dp[j]); // 更新最长公共子数组的长度} else {dp[j] = 0; // 如果nums1[i-1]不等于nums2[j-1],则以nums1[i-1]和nums2[j-1]结尾的最长公共子数组长度为0}}}return result; // 返回最长公共子数组的长度}
}
觉得有用的话可以点点赞,支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
更多推荐
力扣第718题 最长重复子数组 c++ 动态规划 + 滚动数组优化 附Java代码
发布评论