Day45

300.最长递增子序列

力扣题目链接

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

思路

• dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

• if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

• 每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1

代码

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp,1);//初始化dp数组为1，最小长度也是1for (int i = 1; i < nums.length; i++){for (int j = 0; j < i; j++){if (nums[i] > nums[j]){//如果i处元素比j大，就可能进行更新dp[i] = Math.max(dp[i], dp[j] + 1);}}}int res = 1;for (int i : dp) {res = Math.max(i, res);//遍历dp数组，res为最大值}return res;}
}

674. 最长连续递增序列

力扣题目链接

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

• 输入：nums = [1,3,5,4,7]

• 输出：3

• 解释：最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

思路

• 和上一个题的区别是要求必须连续递增

• 连续，就是nums[i] 要大于nums[i - 1] 才进行更新

• 大致想到思路之后手动打印一下

• 贪心也能做，空间复杂度为O(1)，遍历数组，如果比前一个元素大，count++，小就count = 1；没查询一个元素更新res值

代码

class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp, 1);for (int i = 1; i < nums.length; i++) {if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;//递推公式}int res = 1;for (int i : dp) {res = Math.max(res, i);}return res;}
}class Solution1 {public int findLengthOfLCIS(int[] nums) {int count = 1;int res = 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. 最长重复子数组

力扣题目链接

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

思路

• dp[i] [j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i] [j]。

• 当A[i - 1] 和B[j - 1]相等的时候，dp[i] [j] = dp[i - 1] [j - 1] + 1

代码

class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length + 1][nums2.length + 1];int res = 0;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;res = Math.max(res,dp[i][j]);}}}return res;}
}

1143.最长公共子序列

力扣题目链接

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。

思路

• dp[i] [j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i] [j]

• 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i] [j] = dp[i - 1] [j - 1] + 1;

• 如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。

即：dp[i] [j] = max(dp[i - 1] [j], dp[i] [j - 1]);

代码

class Solution {public int longestCommonSubsequence(String text1, String text2) {int[][] dp = new int[text1.length() + 1][text2.length() + 1];for (int i = 1; i < text1.length() + 1; i++){for (int j = 1; j < text2.length() + 1; j++){if (text1.charAt(i - 1) == text2.charAt(j - 1))dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}return dp[text1.length()][text2.length()];}
}