lamp网站开发项目文档,关于友谊的连接,网站做自签发证书,jsp网站维护300. 最长递增子序列
中等
给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,…300. 最长递增子序列
中等
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的 子序列。
思路以nums【i】为结尾的最长递增子序列的长度可以由 nums【0】为结尾的最长递增子序列长度、nums[1为结尾的最长长度、……nums【i-1】为结尾的最长长度 比较得到。因此需要双层for循环。
dp[i] 的含义
误解从 nums【0】 到 nums【i】 的数组其最长递增子序列为 dp【i】 正解从任意位置开始但以nums【i】元素作为结尾的所有 递增子序列中最长的子序列长度为 dp【i】
class Solution {public int lengthOfLIS(int[] nums) {int len nums.length;// dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度注意是包含nums[i]这个元素的// 不信的话给你一个数组{1,2,3,0,0,0},你会发现计算出来的dp[5] 1 // 所以结尾不能返回 return dp[len - 1];int[] dp new int[len]; Arrays.fill(dp, 1); // 请注意这里 每一个i对应的dp[i]即最长递增子序列起始大小至少都是1.int res 1; // 不能初始化为0防止只有一个元素的数组根本进不去for循环for (int i 1; i len; i) {for (int j 0; j i; j) {if (nums[i] nums[j]) { // 如果比前数大dp[i] Math.max(dp[i], dp[j] 1);} }res Math.max(res, dp[i]);}return res;}
}674. 最长连续递增序列
简单 给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp new int[nums.length]; // dp[i]以下标i为结尾的连续递增的子序列长度为dp[i]Arrays.fill(dp, 1);int res 1;for (int i 1; i nums.length; i) {if (nums[i] nums[i - 1]) {dp[i] dp[i - 1] 1;}res Math.max(res, dp[i]);}return res; // 不是 return dp[nums.length - 1];}
}718. 最长重复子数组
中等
提示 给两个整数数组 nums1 和 nums2 返回 两个数组中 公共的 、长度最长的子数组的长度 。
注意本题要求我们计算两个数组的最长公共子数组且子数组在原数组中连续。所以必须是连续的才可以用dp[i][j] dp[i - 1][j - 1] 1;
思路 讲解链接: 【LeetCode每日打卡.718.最长重复子数组】 https://www.bilibili.com/video/BV1eC4y187NR/?share_sourcecopy_webvd_source59d4002fe640642f48d7172733c88844
dp【i】【j】指数组下标以i-1为结尾的nums1和以j-1为结尾的nums2的最大重复子数组的长度。 // 如果在ij)这个位置是相同的那么就要去看i - 1, j - 1)有没有相同有相同的话就要加上ij)这一对即 1
class Solution {public int findLength(int[] nums1, int[] nums2) {// 如果在ij)这个位置是相同的那么就要去看i - 1, j - 1)有没有相同有相同的话就要加上ij)这一对即 1int[][] dp new int[nums1.length][nums2.length];int res 0;for (int i 0; i nums1.length; i) { // 两个for循环逐个两两比较数组中的元素for (int j 0; j nums2.length; j) {if (nums1[i] nums2[j]) { // 如果取出的两元素相等if (i 0 || j 0) {dp[i][j] 1; // 如果他俩有一个是开头元素那前面没有别的元素了它们又相同所以等于1} else { // 如果他俩都不是开头元素dp[i][j] dp[i - 1][j - 1] 1;}} else { // 如果取出的两元素不相等那以他们结尾的两个数组不可能存在公共数组dp[i][j] 0;}res Math.max(res, dp[i][j]);}}return res;}
}
