您现在的位置是:首页 >其他 >代码随想录算法训练营day52 | 300.最长递增子序列,674. 最长连续递增序列,718. 最长重复子数组网站首页其他
代码随想录算法训练营day52 | 300.最长递增子序列,674. 最长连续递增序列,718. 最长重复子数组
代码随想录算法训练营day52 | 300.最长递增子序列,674. 最长连续递增序列,718. 最长重复子数组
300.最长递增子序列
教程视频:https://www.bilibili.com/video/BV1ng411J7xP
解法一:动态规划
思路:
1、dp[i]含义:表示以nums[i]结尾的最长递增子序列的长度。
2、递推公式:dp[i]=Math.max(dp[j]+1,dp[i]);
3、dp数组初始化:全部初始化为1,dp[i]=1;
4、遍历顺序:外层 i 从前向后遍历,内层 j 正序倒序都可以。
5、打印验证。
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int result = 1;//因为外层for不是从dp[0]开始遍历,考虑单个元素情况下输出1。
for(int i=1;i<nums.length;i++){
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
dp[i]=Math.max(dp[j]+1,dp[i]);
}
}
result=Math.max(result,dp[i]);
}
return result;
}
}
674. 最长连续递增序列
教程视频:https://www.bilibili.com/video/BV1bD4y1778v
解法一:动态规划
思路:
1、dp[i]含义:表示以nums[i]结尾的最长连续递增子序列的长度。
2、递推公式:if(nums[i-1]<nums[i]) dp[i]=dp[i-1]+1;
3、dp数组初始化:全部初始化为1,dp[i]=1;
4、遍历顺序:外层 i 正序遍历,内层 无需遍历。
5、打印验证。
class Solution {
public int findLengthOfLCIS(int[] nums) {
int[] dp = new int[nums.length];
// Arrays.fill(dp,1);
for (int i = 0; i < dp.length; i++) {
dp[i] = 1;
}
int result = 1;
for(int i=1;i<nums.length;i++){
if(nums[i-1]<nums[i]){
dp[i]=dp[i-1]+1;
}
result = Math.max(result,dp[i]);
}
return result;
}
}
解法二:双指针法
class Solution {
public int findLengthOfLCIS(int[] nums) {
if(nums.length==1)return 1;
int maxLength=1;
for(int left=0;left<nums.length;left++){
int curLength=1;
for(int right=left+1;right<nums.length;right++){
if(nums[right-1]<nums[right]){
curLength++;
}else{
break;
}
}
maxLength=Math.max(maxLength,curLength);
}
return maxLength;
}
}
718. 最长重复子数组
教程视频:https://www.bilibili.com/video/BV178411H7hV
解法一:动态规划
思路:
1、dp[i][j]含义:以下标 i - 1为 结尾的nums1,和以下标 j - 1 为结尾的nums2,最长重复子数组长度为dp[i][j]。 这里-1是为了简化初始化过程。
2、递推公式:两个数组指针始终对齐,需要同时-1if(nums2[j]==nums1[i]){ dp[i][j]=dp[i-1][j-1]+1; }
3、dp数组初始化:dp[0][j]和dp[i][0]无实际意义,为了保证递推有意义,全部初始化为0,dp[i][j]=0;
4、遍历顺序:外层 遍历nums1,内层遍历nums2。正序倒序无影响。
5、打印验证。
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length+1][nums2.length+1];
int maxLength=0;
for(int i=1;i<=nums1.length;i++){
for(int j=1;j<=nums2.length;j++){
if(nums1[i-1]==nums2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
maxLength=Math.max(maxLength,dp[i][j]);
}
}
return maxLength;
}
}
//空间压缩
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int[] dp = new int[nums2.length+1];
int maxLength=0;
for(int i=1;i<=nums1.length;i++){
for(int j=nums2.length;j>=1;j--){
if(nums1[i-1]==nums2[j-1]){
dp[j]=dp[j-1]+1;
}else {
dp[j] = 0;//这里不能漏,否则上一阶段状态不能完全刷新
}
maxLength=Math.max(maxLength,dp[j]);
}
}
return maxLength;
}
}
总结
1、子数组相关题目要从尾部元素去定义dp数组;
2、两个不同序列比较时,递推公式需要考虑指针对齐的问题;
3、718. 最长重复子数组中dp[i][j]表示索引为i-1和j-1处的最长公共子序列,可以简化初始化状态。