贵阳做网站好的公司,腾讯建设网站视频视频视频,深圳市保障性住房官网,wordpress安装主题后找不到后台入口代码随想录算法训练营第五十二天 | 300.最长递增子序列 、674. 最长连续递增序列 、718. 最长重复子数组
300.最长递增子序列
题目链接#xff1a;300. 最长递增子序列 - 力扣#xff08;LeetCode#xff09;
class Solution {public int lengthOfLIS(int[] nums) {int l…代码随想录算法训练营第五十二天 | 300.最长递增子序列 、674. 最长连续递增序列 、718. 最长重复子数组
300.最长递增子序列
题目链接300. 最长递增子序列 - 力扣LeetCode
class Solution {public int lengthOfLIS(int[] nums) {int len nums.length, res 1;int[] dp new int[len];Arrays.fill(dp ,1);for(int i 1; i len; i) {for(int j 0; j i; j) {if(nums[i] nums[j]) dp[i] Math.max(dp[j] 1, dp[i]); }res Math.max(res, dp[i]);}return res;}
}674. 最长连续递增序列
题目链接674. 最长连续递增序列 - 力扣LeetCode
// 贪心法
// 这里回忆一下贪心法保证每次单次最优 - 总的最优
// 这道题的单词最优就是遇到nums[i] nums[i - 1]的情况count就否则count为1
class Solution {public int findLengthOfLCIS(int[] nums) {int res 1, count 1;for(int i 1; i nums.length; i) {if(nums[i] nums[i-1]) {count;} else {count 1;}res Math.max(res, count);}return res;}
}718. 最长重复子数组
题目链接718. 最长重复子数组 - 力扣LeetCode
class Solution {public int findLength(int[] nums1, int[] nums2) {int result 0;// dp[i][j] 表示分别以nums1[i-1] 和 nums2[j-1] 结尾的两个数组对应的最长公共子数组的长度// 这样就无需初始化 dp[i][0] 和 dp[0][j] 的情况了// 其实题目要求的是连续子数组// 那么递推公式就是 dp[i][j] dp[i - 1][j - 1] 1;int[][] dp new int[nums1.length 1][nums2.length 1];for (int i 1; i nums1.length 1; i) {for (int j 1; j nums2.length 1; j) {if (nums1[i - 1] nums2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;result Math.max(result, dp[i][j]);}}}return result;}
}总结 今天的题目比较难想到的是300. 最长递增子序列 - 力扣LeetCode因为其要求的递增子序列是不一定是要连续的所以双层循环第一层确定nums[i] 作为尾部第二层遍历[0, i)寻找满足nums[j] nums[i]严格递增的数组索引j这样以为nums[j] 为尾部对应的dp[j]就可以加上新的尾部nums[i]递推公式为dp[i] Math.max(dp[i], dp[j] 1) 674. 最长连续递增序列 - 力扣LeetCode 相对来说比较简单可以留意贪心的做法 718. 最长重复子数组 - 力扣LeetCode 难点在于 确定dp数组dp table以及下标的含义
dp[i][j]长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i] [j]
