leetcode 718. 最长重复子数组

package com.leetcode; /** * 718. 最长重复子数组 * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。 * 示例： * 输入： * A: [1,2,3,2,1] * B: [3,2,1,4,7] * 输出：3 * 解释： * 长度最长的公共子数组是 [3, 2, 1] 。 */ public class Main718 { public int findLength(int[] A, int[] B) { if(A.length == 0 || B.length == 0) { return 0; } int m = A.length + 1; int n = B.length + 1; int ans = 0; int[][] dp = new int[m][n]; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (A[i-1] == B[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; ans = Math.max(dp[i][j], ans); } } } return ans; } public static void main(String[] args) { int[] A = {1,2,3,2,1}; int[] B = {3,2,1,4,7}; Main718 m = new Main718(); System.out.println(m.findLength(A,B)); } }

leetcode 1143. 最长公共子序列

package com.leetcode; /** * 1143. 最长公共子序列 * 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。 * 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。 * 若这两个字符串没有公共子序列，则返回 0。 */ public class Main1143 { public int longestCommonSubsequence(String text1, String text2) { int len1 = text1.length(); int len2 = text2.length(); int[][] dp = new int[len1+1][len2+1]; for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; 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[len1][len2]; } public static void main(String[] args) { Main1143 m = new Main1143(); String text1 = "abcde", text2 = "ace"; System.out.println(m.longestCommonSubsequence(text1,text2)); } }

LeetCode 300. 最长上升子序列

package com.leetcode; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * 300. 最长上升子序列 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。 * 输入: [10,9,2,5,3,7,101,18] * 输出: 4 * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 */ public class Main300 { public int lengthOfLIS(int[] nums) { int len = nums.length; if (len < 2) { return len; } int[] dp = new int[len]; Arrays.fill(dp, 1); List<Integer> list = new ArrayList<>(); int pos = 0; int posDp = 0; int maxAns = 1; for (int i = 1; i < len; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); if (dp[i] >= maxAns) pos = i; } } maxAns = Math.max(maxAns, dp[i]); } posDp = maxAns; list.add(nums[pos]); for (int i = pos-1; i >= 0 ; i--) { if (dp[i] == posDp-1) { list.add(0, nums[i]); posDp -= 1; } } System.out.println(list); return maxAns; } public static void main(String[] args) { Main300 m = new Main300(); int[] nums = {10,9,2,5,3,7,18,118,1}; System.out.println(m.lengthOfLIS(nums)); } }

leetcode 5. 最长回文子串

/** * 5. 最长回文子串 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 * 输入: "babad" * 输出: "bab" * 注意: "aba" 也是一个有效答案。 */ public class Main5 { //dp[start][end] = dp[start+1][end-1] && s.charAt(start)==s.charAt(end) public String longestPalindrome(String s) { if(s == null || s.length() == 0) return s; int n = s.length(); boolean[][] dp = new boolean[n][n]; String res = ""; for(int len = 1; len <= n; len++) { for(int start = 0; start < n; start++) { int end = start + len - 1; if(end >= n) break; dp[start][end] = len == 1 || len == 2 && s.charAt(start) == s.charAt(end) || dp[start+1][end-1] && s.charAt(start) == s.charAt(end); if(dp[start][end] && len > res.length()) { res = s.substring(start, end + 1); } } } return res; } }