一、子序列/子數(shù)組問題

子序列：按原數(shù)組的順序排列，不一定是原數(shù)組中的相鄰元素組成的。即子序列可以是不連續(xù)的。
子數(shù)組：原數(shù)組中連續(xù)的幾個元素組成的數(shù)組。

1. 300【最長遞增子序列】

• 題目：
  給你一個整數(shù)數(shù)組 nums ，找到其中最長嚴格遞增子序列的長度。
  子序列 是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。
• 代碼：

class Solution {public int lengthOfLIS(int[] nums) {//dp表示以數(shù)組中第i個元素為結尾的最長嚴格遞增子序列的長度//dp[i] = max(dp[j])+1,其中nums[j]是nums[i]左邊小于nums[i]的元素//dp[0] = 1int[] dp = new int [nums.length];dp[0] = 1;int max = 1;for(int i=1;i<nums.length;i++){int tmp = 0;for(int j=0;j<i;j++){if(nums[j]<nums[i]){tmp = Math.max(tmp,dp[j]);}}dp[i] = tmp + 1;max = Math.max(dp[i],max);}return max;}
}

2. 72【編輯距離】

• 題目： 給你兩個單詞 word1 和 word2， 請返回將 word1 轉換成 word2 所使用的最少操作數(shù) 。
  你可以對一個單詞進行如下三種操作：
  • 插入一個字符
  • 刪除一個字符
  • 替換一個字符
• 代碼：

class Solution {public int minDistance(String word1, String word2) {//兩個字符串的操作，使用雙指針，i指向word1，j指向word2//dp[i][j]表示由左向右操作到word1的第i個位置，word2的第j個位置需要的最少操作數(shù)。//dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)//dp[0][j] = j,dp[i][0] = iint m = word1.length();int n = word2.length();if(n==0) return m;if(m==0) return n;int[][] dp = new int [m+1][n+1];for(int i=0;i<=m;i++){dp[i][0] = i;}for(int i=0;i<=n;i++){dp[0][i] = i;}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(word1.charAt(i-1)==word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = minDp(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;}}}return dp[m][n];}public int minDp(int a,int b,int c){int tmp = Math.min(a,b);tmp = Math.min(tmp,c);return tmp;}
}

3. 53【最大子數(shù)組的和】

• 題目： 給你一個整數(shù)數(shù)組 nums ，請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。
  子數(shù)組是數(shù)組中的一個連續(xù)部分。
• 代碼：

class Solution {public int maxSubArray(int[] nums) {//dp[i]表示以nums[i]為結尾的最大子數(shù)組的和//dp[i] = max(dp[i-1]+nums[i],nums[i])//dp[0] = nums[0]int[] dp = new int [nums.length];dp[0] = nums[0];int max = nums[0];for(int i=1;i<nums.length;i++){dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);max = Math.max(dp[i],max);}return max;}
}

4. 674【最長連續(xù)自增序列】

• 題目： 給定一個未經(jīng)排序的整數(shù)數(shù)組，找到最長且 連續(xù)遞增的子序列，并返回該序列的長度。
  連續(xù)遞增的子序列 可以由兩個下標 l 和 r（l < r）確定，如果對于每個 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是連續(xù)遞增子序列。
• 代碼：

//方法一：雙指針
class Solution {public int findLengthOfLCIS(int[] nums) {//雙指針法，固定左指針，移動右指針，//直到右指針所指元素不滿足條件,將左指針指向右指針int i=0;int max = 1;for(int j=1;j<nums.length;j++){if(nums[j-1]<nums[j]){max = Math.max(max,j-i+1);}else{i = j;}}return max;}
}
//方法二：動態(tài)規(guī)劃
class Solution {public int findLengthOfLCIS(int[] nums) {//dp[i]表示以第i個元素結尾的最長連續(xù)遞增子序列的長度//dp[i]=1 or dp[i-1]+1//dp[0]=1int[] dp = new int[nums.length];dp[0] = 1;int max=1;for(int i=1;i<nums.length;i++){if(nums[i-1]<nums[i]){dp[i] = dp[i-1]+1;}else{dp[i] = 1;}max = Math.max(max,dp[i]);}return max;}
}

5. 718【最長重復子數(shù)組】

• 題目： 給兩個整數(shù)數(shù)組 nums1 和 nums2 ，返回 兩個數(shù)組中 公共的 、長度最長的子數(shù)組的長度。
• 代碼：

class Solution {public int findLength(int[] nums1, int[] nums2) {//dp[i][j]表示以nums1[i],nums2[j]結尾的最長的公共子數(shù)組長度//dp[i][j] = dp[i-1][j-1]+1 (nums1[i]==nums2[j])//dp[0][0] = 0(nums1[i-1]!=nums2[j-1]) or 1(nums1[i-1]==nums2[j-1])int n = nums1.length;int m = nums2.length;int[][] dp = new int[n][m];int max=0;for(int i=0;i<n;i++){if(nums1[i]!=nums2[0]){dp[i][0] = 0;}else{dp[i][0] = 1;}max = Math.max(dp[i][0],max);}for(int i=0;i<m;i++){if(nums1[0]!=nums2[i]){dp[0][i] = 0;}else{dp[0][i] = 1;}max = Math.max(dp[0][i],max);}for(int i=1;i<n;i++){for(int j=1;j<m;j++){if(nums1[i] == nums2[j]){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = 0;}max = Math.max(dp[i][j],max);}}return max;}
}

6. 1143【最長公共子序列】

• 題目： 給定兩個字符串 text1 和 text2，返回這兩個字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ，返回 0 。
  一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。
  例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
  兩個字符串的 公共子序列 是這兩個字符串所共同擁有的子序列。
• 代碼：

class Solution {public int longestCommonSubsequence(String text1, String text2) {//dp[i][j]表示以text1[i],text2[j]為結尾的最長公共子序列長度//dp[i][j] = dp[i-1][j-1]+1(text1[i]==text2[j]) or//dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])//dp[i][0] = 0(text1[0]!=text2[0]) or 1(text1[0]==text2[0])//dp[0][i] = 0(text1[0]!=text2[0]) or 1(text1[0]==text2[0])int n = text1.length();int m = text2.length();int[][] dp = new int[n][m];boolean flag = false;for(int i=0;i<n;i++){if((text1.charAt(i) == text2.charAt(0))||flag==true){dp[i][0] = 1;flag = true;}else {dp[i][0] = 0;}}int max=0;if(flag){max = 1;}flag = false;for(int i=0;i<m;i++){if((text1.charAt(0)==text2.charAt(i))||flag==true){dp[0][i] = 1;flag = true;}else{dp[0][i] = 0;}   }for(int i=1;i<n;i++){for(int j=1;j<m;j++){if(text1.charAt(i) == text2.charAt(j)){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = maxNum(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);}max = Math.max(max,dp[i][j]);}}return max;}public int maxNum(int a,int b,int c){int tmp = Math.max(a,b);return Math.max(tmp,c);}
}

7. 647【回文子串】

• 題目： 給你一個字符串 s ，請你統(tǒng)計并返回這個字符串中 回文子串 的數(shù)目。回文字符串 是正著讀和倒過來讀一樣的字符串。子字符串 是字符串中的由連續(xù)字符組成的一個序列。具有不同開始位置或結束位置的子串，即使是由相同的字符組成，也會被視作不同的子串。
• 代碼：

class Solution {public int countSubstrings(String s) {//dp[i][j]表示在substring(i,j+1)是否是回文串//dp[i][j] = true(s[i]==s[j]) or false(s[i]!=s[j])//因為i由i+1決定，j由j-1決定，所以需要從左下角開始遍歷//dp[][0]=false or true,dp[n-1][]=false or trueint n = s.length();boolean[][] dp = new boolean[n][n];int ans = 0;for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s.charAt(i)==s.charAt(j)){if(j-i<=1){dp[i][j] = true;ans++;}else if(dp[i+1][j-1]){dp[i][j] = true;ans++;}}}}return ans;}
}

8. 5【最長回文子串】

• 題目： 給你一個字符串 s，找到 s 中最長的回文子串。
  如果字符串的反序與原始字符串相同，則該字符串稱為回文字符串。
• 代碼：

class Solution {public String longestPalindrome(String s) {//dp[i][j]表示substring(i,j+1)是否是回文串//dp[i][j] = true(s[i]==s[j]) or false(s[i]!=s[j])//dp[i][j] = true(s[i]==s[j] and j-i<=1 or dp[i+1][j-1])int n = s.length();boolean[][] dp = new boolean[n][n];int maxLen = 0;int index = 0;for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s.charAt(i) == s.charAt(j)){if(j-i<=1){dp[i][j] = true;}else if(dp[i+1][j-1]){dp[i][j] = true;}if(dp[i][j] && (maxLen < j-i+1)){maxLen = j-i+1;index = i;}}}}return s.substring(index,index+maxLen);}
}