516. 最长回文子序列
516. 最长回文子序列
dp[i][j]表示下标i-j的子字符串的最长回文子序列
class Solution {public int longestPalindromeSubseq(String s) {int n=s.length();if(n==1||n==0) return n;int[][] dp=new int[n][n];for(int i=0;i<n;i++){dp[i][i]=1;}for(int i=n-2;i>=0;i--){for(int j=i+1;j<n;j++){if(s.charAt(i)==s.charAt(j)) dp[i][j]=dp[i+1][j-1]+2;else dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);}}return dp[0][n-1];}}
最长递增子序列
300. 最长递增子序列
找到最优子结构
dp[i]表示以nums[i]结尾的最长递增子序列的长度，那么numsj如果大于nums[i]，那么这个子序列的长度就是dp[i]+1,遍历获得以nums[j]结尾的最长递增子序列长度，每次遍历结束更新返回结果。
题解
class Solution {public int lengthOfLIS(int[] nums) {int n=nums.length;if(n==0) return 0;int[] dp=new int[n];Arrays.fill(dp,1);int res=0;for(int i=0;i<n;i++){for(int j=0;j<i;j++){if(nums[j]<nums[i]){dp[i]=Math.max(dp[i],dp[j]+1);}}res=Math.max(res,dp[i]);}return res;}}
还可以用二分查找法解决，思路如下：
- dp[i]表示长度为i+1的递增子序列的尾值最小为dp[i]
if(maxL==0||(maxL>0&&dp[maxL-1]<nums[i]))直接插入- 否则，说明nums[i]小于等于当前dp数组中已有的数字，需要找到他应该在的位置，二分法找。
比如：dp[]=[1,3,4,8,9]，nums[i]=7，那么修改后的结果为dp[]=[1,3,4,7,9]
- 正是因为有上面的修改，才能不断更新maxL
class Solution {public int lengthOfLIS(int[] nums) {int n=nums.length;int[] dp=new int[n];int maxL=0;for(int i=0;i<n;i++){if(maxL==0||(maxL>0&&dp[maxL-1]<nums[i])){maxL++;dp[maxL-1]=nums[i];}else{int l=0, r=maxL-1;while(l<=r){int mid=l+(r-l)/2;if(dp[mid]<nums[i]){l=mid+1;}else{r=mid-1;}}dp[l]=nums[i];}}return maxL;}}
354. 俄罗斯套娃信封问题
是最长递增子序列的进阶
死板的思路就是加一个排序
class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes,(a,b)->{
if(a[0]>b[0]) return 1;
else if(a[0]==b[0]) return a[1]-b[1];
else return -1;
});
int n=envelopes.length;
int[] dp= new int[n];
Arrays.fill(dp,1);
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(envelopes[i][0]>envelopes[j][0]&&envelopes[i][1]>envelopes[j][1]){
dp[i]=Math.max(dp[j]+1,dp[i]);
}
}
res=Math.max(res,dp[i]);
}
return res;
}
}
一个优化的思路
排序的时候，假设envelope[宽][长]，按照宽升序排列，长降序排列，这样在后面遍历的时候只需要比较宽就可以了。
这个解法的关键在于，对于宽度 w 相同的数对，要对其高度 h 进行降序排序。因为两个宽度相同的信封不能相互包含的，逆序排序保证在 w 相同的数对中最多只选取一个。
class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes,(a,b)->{
if(a[0]>b[0]) return 1;
else if(a[0]==b[0]) return b[1]-a[1];
else return -1;
});
int n=envelopes.length;
int[] dp= new int[n];
Arrays.fill(dp,1);
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(envelopes[i][1]>envelopes[j][1]){
dp[i]=Math.max(dp[j]+1,dp[i]);
}
}
res=Math.max(res,dp[i]);
}
return res;
}
}
最长递增子序列的进阶
NC91 最长递增子序列
public class Solution {
/**
* retrun the longest increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型一维数组
*/
public int[] LIS (int[] arr) {
// write code here
int n=arr.length;
int[] dp=new int[n]; //dp[i]表示以arr[i]结尾的递增序列的长度
int[] ls=new int[n]; //ls[i]表示长度为i+1的递增子序列中，尾数最小为ls[i]
int maxL=0; //递增序列的最大长度
for(int i=0;i<n;i++){
if(maxL==0||(maxL>0&&ls[maxL-1]<arr[i])){
maxL++;
ls[maxL-1]=arr[i]; //直接加入序列
dp[i]=maxL;
}else{
int l=0, r=maxL-1;
//找ls中第一个 >= arr[i]的（必定存在，因为保证ls的最后一个 >= arr[i]）
while(l<=r){
int mid=l+(r-l)/2;
if(arr[i]>ls[mid]){
l=mid+1;
}else{
r=mid-1;
}
}
ls[l]=arr[i]; //找到位置后替换掉
dp[i]=l+1;
}
}
//最后的子序列和ls无关
//倒着遍历，找到满足长度的dp就记录，然后更新。（即同样值的dp，选尽量靠右边的）
int[] ans=new int[maxL];
int i=maxL-1, j=n-1;
while(i>=0&&j>=0){
if(dp[j]==i+1){
ans[i]=arr[j];
i--;
j--;
}else{
j--;
}
}
return ans;
}
}
53. 最大子序和
题目：53. 最大子序和
因为子序要连续，所以dp[i]表示以nums[i]结尾的最大子序和
class Solution {
public int maxSubArray(int[] nums) {
int max=nums[0];
int n=nums.length;
int[] dp=new int[n];
dp[0]=nums[0];
for(int i=1;i<n;i++){
dp[i]=dp[i-1]>0?dp[i-1]+nums[i]:nums[i];
max=Math.max(max,dp[i]);
}
return max;
}
}
最长公共子序列
1143. 最长公共子序列
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char[] arr1=text1.toCharArray();
char[] arr2=text2.toCharArray();
int m=arr1.length;
int n=arr2.length;
int[][] dp=new int[m+1][n+1];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(arr1[i]==arr2[j]){
dp[i+1][j+1]=dp[i][j]+1;
}else{
dp[i+1][j+1]=Math.max(dp[i+1][j],dp[i][j+1]);
}
}
}
return dp[m][n];
}
}
583. 两个字符串的删除操作
583. 两个字符串的删除操作
和最长公共子序列一毛一样
删除字母使得两个字符串最终相等，找到最长公共子序列，其他的都是需要删掉的。
class Solution {
public int minDistance(String word1, String word2) {
int len1=word1.length();
int len2=word2.length();
int[][] dp=new int[len1+1][len2+1];
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(word1.charAt(i-1)==word2.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]);
}
}
}
int len=dp[len1][len2];
return len1+len2-2*len;
}
}
NC127 最长公共子串
链接
和最长公共子序列不一样的，这个要求“连续”
dp[i][j] 表示 str1中以第i个字母结尾，str2中以第j个字母结尾，最长公共子串是多少
如果 str1.charAt(i-1)!=str2.charAt(j-1) ，这种情况下长度为0
public class Solution {
/**
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public String LCS (String str1, String str2) {
// write code here
int[][] dp=new int[str1.length()+1][str2.length()+1];
int len=Integer.MIN_VALUE;
int index=-1;
for(int i=1;i<=str1.length();i++){
for(int j=1;j<=str2.length();j++){
if(str1.charAt(i-1)==str2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
if(dp[i][j]>len){
len=dp[i][j];
index=i;
}
}
}
}
String ans=str1.substring(index-len,index);
return ans;
}
}
1312. 让字符串成为回文串的最少插入次数
思路和最长公共子序列类似
比如s=”mbadm”
s的逆序 s1=”mdabm”
s和s1的最长公共子序列=3
5-3=2为不同的字符数，就是需要进行插入的地方的个数。
class Solution {
public int minInsertions(String s){
char[] arr=s.toCharArray();
int n=arr.length;
int[][] dp=new int[n+1][n+1];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(arr[i]==arr[n-1-j]){
dp[i+1][j+1]=dp[i][j]+1;
}else{
dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);
}
}
}
return s.length()-dp[n][n];
}
}
有的面试题会要求把修改后的字符串打印出来
public class T1312 {
public static void main(String[] args) {
T1312 t = new T1312();
String input = "mbadm";
int insertions = t.minInsertions(input);
System.out.println("min insertions: " + insertions);
String after = t.afterInsertions(input, insertions);
System.out.println("after insertions: " + after);
}
public int minInsertions(String s) {
char[] arr = s.toCharArray();
int n = arr.length;
int[][] dp = new int[n + 1][n + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i] == arr[n - 1 - j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
} else {
dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
}
}
}
int ans = n - dp[n][n];
return ans;
}
public String afterInsertions(String s, int insertions) {
char[] arr = s.toCharArray();
int n = arr.length;
char[] ans = new char[insertions + n];
int l = 0, r = n - 1;
int i = 0, j = ans.length - 1;
while (l <= r) {
ans[i++] = arr[l];
ans[j--] = arr[l];
if (arr[l] != arr[r]) {
ans[i++] = arr[r];
ans[j--] = arr[r];
}
l++;
r--;
}
return String.valueOf(ans);
}
}
718. 最长重复子数组
注意：要求连续
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int m=nums1.length;
int n=nums2.length;
int[][] dp=new int[m+1][n+1];
int ans=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(nums1[i-1]==nums2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
ans=Math.max(ans,dp[i][j]);
}
}
return ans;
}
}
若有收获，就点个赞吧
0 人点赞
