300. 最长递增子序列(中等)
// 二分法
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int res[] = new int[n];
int it = 0;
for(int num:nums){
int index = lower_bound(res,num,it);
if(index==it){
res[it++] = num;
}else{
res[index] = num;
}
}
return it;
}
public int lower_bound(int res[],int v,int it){
int left = 0;
int right = it;
while(left<right){
int mid = left+(right-left)/2;
if(res[mid] < v ){
left = mid+1;
}else {
right = mid;
}
}
return left;
}
}
// dp法: if(nums[i]>nums[j])dp[i]=dp[j]+1
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int dp[] = new int[n];
int max = 1;
Arrays.fill(dp,1);
for(int i=1;i<n;i++){
for(int j=i-1;j>=0;j--)
if(nums[j]<nums[i])
dp[i] = Math.max(dp[i],dp[j]+1);
if(dp[i]>max)max = dp[i];
}
return max;
}
}
674. 最长连续递增序列(简单)
class Solution {
public int findLengthOfLCIS(int[] nums) {
int n = nums.length;
int dp[] = new int[n];
Arrays.fill(dp,1);
int max = 1;
for(int i=1;i<n;i++){
if(nums[i]>nums[i-1])dp[i]=dp[i-1]+1;
if(dp[i]>max)max = dp[i];
}
return max;
}
}
718. 最长重复子数组(中等)
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int max = 0;
int dp[][] = new int[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<= m;j++){
if(nums1[i-1]==nums2[j-1]){
dp[i][j] = dp[i-1][j-1]+1;
}
max = Math.max(max,dp[i][j]);
}
}
return max;
}
}
1143. 最长公共子序列(中等)
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
int dp[][] = new int[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;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(Math.max(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1]);
}
}
}
return dp[n][m];
}
}
文章来源地址https://uudwc.com/A/XNG85
文章来源:https://uudwc.com/A/XNG85