LeetCode 392. Judging subsequences
given string s and t ，judge s Is it t subsequence. A subsequence of a string is a new string formed by removing some (or not) characters from the original string without changing the relative positions of the remaining characters. (E.g,"ace"Yes"abcde"a subsequence of , and"aec"no). Advanced: If there is a large amount of input S，called S1, S2, ... , Sk in k >= 10 billion, you need to check in turn whether they are T subsequence. In this case, how would you change the code? Example 1: enter: s = "abc", t = "ahbgdc" output: true Example 2: enter: s = "axc", t = "ahbgdc" output: false
double pointer
class Solution {
public boolean isSubsequence(String s, String t) {
int m = s.length();
int n = t.length();
int i = 0, j=0;
while(i<m&&j<n){
if(s.charAt(i)==t.charAt(j)){
i++;
j++;
}else{
j++;
}
}
return i==m;
}
}
dynamic programming
public boolean isSubsequence(String s, String t) {
int length1 = s.length(); int length2 = t.length();
int[][] dp = new int[length1+1][length2+1];
for(int i = 1; i <= length1; i++){
for(int j = 1; j <= length2; j++){
if(s.charAt(i-1) == t.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = dp[i][j-1];
}
}
}
if(dp[length1][length2] == length1){
return true;
}else{
return false;
}
}
LeetCode 115. Different Subsequences (Hard)
given a string s and a string t ，Calculated at s in the subsequence of t number of occurrences. A subsequence of a string is a new string formed by removing some (or not) characters without disturbing the relative positions of the remaining characters. (E.g,"ACE" Yes "ABCDE" a subsequence of , and "AEC" no) Item data guarantees that answers fit within the range of 32-bit signed integers. Example 1: enter: s = "rabbbit", t = "rabbit" output: 3 explain: As shown below, There are 3 types available from s get in "rabbit" plan. rabbbit rabbbit rabbbit Example 2: enter: s = "babgbag", t = "bag" output: 5 explain: As shown below, There are 5 available from s get in "bag" plan. babgbag babgbag babgbag babgbag babgbag
class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++)
dp[i][0] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (j > i)
continue;
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m][n];
}
}
LeetCode 53. Maximum Suborder Sum
gives you an array of integers nums ，Please find a contiguous subarray with the largest sum (the subarray contains at least one element) and return the largest sum. A subarray is a contiguous part of an array. Example 1: enter: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: Contiguous subarrays [4,-1,2,1] The sum of the maximum, for 6 . Example 2: enter: nums = [1] output: 1 Example 3: enter: nums = [5,4,-1,7,8] output: 23
greedy
class Solution {
public int maxSubArray(int[] nums) {
int result = Integer.MIN_VALUE;
int count = 0;
for(int i = 0;i<nums.length;i++){
count+=nums[i];
if(count>result){
result = count;
}
if(count <=0){
count =0;
}
}
return result;
}
}
dynamic programming
class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
dp[0] = nums[0];
int ans = dp[0];
for(int i = 1; i < len; i++) {
dp[i] = Math.max(nums[i],dp[i-1] + nums[i]);
ans = Math.max(ans,dp[i]);
}
return ans;
}
}
LeetCode 300. The length of the longest ascending subsequence
gives you an array of integers nums ，Find the length of the longest strictly increasing subsequence in it. subsequence is a sequence derived from an array that removes (or does not remove) elements from the array without changing the order of the remaining elements. E.g,[3,6,2,7] is an array [0,3,1,6,2,2,7] subsequence. Example 1: enter: nums = [10,9,2,5,3,7,101,18] output: 4 Explanation: The longest increasing subsequence is [2,3,7,101]，So the length is 4 . Example 2: enter: nums = [0,1,0,3,2,3] output: 4 Example 3: enter: nums = [7,7,7,7,7,7,7] output: 1
dynamic programming
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if(len < 2) return len;
int[] dp = new int[len];//length of longest increasing subsequence ending in i
int ans = 0;
Arrays.fill(dp, 1);
for(int i = 0; i < len; i++) {
for(int j = 0; j < i; j++) {
if(nums[j] < nums[i]) {//If this number is less than the number in this segment, then there is an increasing subsequence
if(dp[j] >= dp[i]) {
dp[i] = dp[j] + 1;
}
}
ans = Math.max(dp[i], ans);
}
}
return ans;
}
}
binary search
class Solution {
public int lengthOfLIS(int[] nums) {
int ans = 0;
int len = nums.length;
int[] dp = new int[len];
for(int i = 0; i < len; i++) {
int sit = Arrays.binarySearch(dp,0,ans,nums[i]);//Find the position of the element larger than nums[i]
sit = sit < 0 ? - sit - 1:sit;
dp[sit] = nums[i];//replace the first position larger than him
if(sit == ans) {//If exactly greater than all the numbers in the subsequence, then the longest increasing subsequence length is increased by one
ans++;
}
}
return ans;
}
}
LeetCode 673. The number of longest increasing subsequences
Given an unsorted array of integers nums ， Returns the number of longest increasing subsequences . Notice:This sequence must be strictly increasing. Example 1: enter: [1,3,5,4,7] output: 2 explain: There are two longest increasing subsequences, which are [1, 3, 4, 7] and[1, 3, 5, 7]. Example 2: enter: [2,2,2,2,2] output: 5 explain: The longest increasing subsequence has length 1, and there are 5 subsequences of length 1, so output 5
class Solution {
public int findNumberOfLIS(int[] nums) {
int len = nums.length;
if(len < 2) return len;
int[] lengths = new int[len];//Several cases of increasing subsequence
int[] dp = new int[len];//The number of each increasing subsequence
Arrays.fill(dp,1);
for(int i = 0; i < len; i++) {
for(int j = 0; j < i; j++) {
if(nums[j] < nums[i]) {
if(lengths[j] >= lengths[i]) {
lengths[i] = lengths[j] + 1;
dp[i] = dp[j];
}else if(lengths[j] + 1 == lengths[i]) {
dp[i] += dp[j];
}
}
}
}
int lengest = 0, ans = 0;
for(int length : lengths) {
lengest = Math.max(lengest,length);
}
for(int i = 0; i < len; i++) {
if(lengths[i] == lengest) {
ans += dp[i];
}
}
return ans;
}
}
LeetCode 674. The length of the longest continuously increasing subsequence
Given an unsorted array of integers, find the longest continuously increasing subsequence and return the length of the sequence. Continuously increasing subsequences can be subscripted by two l and r(l < r)OK, if for each l <= i < r，have nums[i] < nums[i + 1] ，then the subsequence [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] It is a continuously increasing subsequence. Example 1: enter: nums = [1,3,5,4,7] output: 3 Explanation: The longest continuous increasing sequence is [1,3,5], The length is 3. although [1,3,5,7] is also an ascending subsequence, But it's not contiguous because 5 and 7 are separated by 4 in the original array. Example 2: enter: nums = [2,2,2,2,2] output: 1 Explanation: The longest continuous increasing sequence is [2], length is 1.
brute force solution
class Solution {
public int findLengthOfLCIS(int[] nums) {
int len = nums.length;
int ans = 1;
int max = ans;
for (int i = 0; i < len - 1; i++) {
if (nums[i+1] <= nums[i]) max = 0;
ans = Math.max(++max, ans);
}
return ans;
}
}
dynamic programming
//version one
class Solution {
public int findLengthOfLCIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n+1];
Arrays.fill(dp,1);
for(int i = 1;i<n;i++){
if(nums[i]>nums[i-1])
dp[i] = Math.max(dp[i],dp[i-1]+1);
}
int max = 1;
for(int num:dp){
max = Math.max(max,num);
}
return max;
}
}
//optimization
class Solution {
public int findLengthOfLCIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n+1];
Arrays.fill(dp,1);
int res = 1;
for(int i = 1;i<n;i++){
if(nums[i]>nums[i-1])
dp[i] = dp[i-1]+1;
if(dp[i]>res) res = dp[i];
}
return res;
}
}
LeetCode 1218. Longest Fixed Difference Subsequence
gives you an array of integers arr and an integer difference，please find and return arr The length of the longest arithmetic subsequence in which the difference between adjacent elements in the subsequence is equal to difference . A subsequence is defined by removing some or none of the elements without changing the order of the remaining elements. arr derived sequence. Example 1: enter: arr = [1,2,3,4], difference = 1 output: 4 Explanation: The longest arithmetic subsequence is [1,2,3,4].
class Solution {
public int longestSubsequence(int[] arr, int difference) {
int ans = 1;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < arr.length; i++) {
int temp = map.getOrDefault(arr[i]-difference, 0) + 1;//Indicates that the arithmetic subsequence has occurred before
map.put(arr[i], temp);//new length
ans = Math.max(ans, temp);
}
return ans;
}
}
LeetCode 1143. Longest Common Subsequence
given two strings text1 and text2，Returns the length of the longest common subsequence of these two strings. Returns 0 if no common subsequence exists. a string subsequence Refers to such a new string: it is a new string formed by deleting some characters (or no characters) from the original string without changing the relative order of the characters. E.g,"ace" Yes "abcde" subsequence of , but "aec" no "abcde" subsequence. The common subsequence of two strings is the subsequence that both strings have in common. Example 1: enter: text1 = "abcde", text2 = "ace" output: 3 Explanation: The longest common subsequence is "ace" ，Its length is 3 . Example 2: enter: text1 = "abc", text2 = "abc" output: 3 Explanation: The longest common subsequence is "abc" ，Its length is 3 . Example 3: enter: text1 = "abc", text2 = "def" output: 0 Explanation: The two strings have no common subsequence, return 0 . hint: 1 <= text1.length, text2.length <= 1000 text1 and text2 Consists of lowercase English characters only.
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m=text1.length();
int n=text2.length();
int[][] dp=new int[m+1][n+1];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;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[m][n];
}
}
LeetCode 718. Longest Repeating Subarray
to two integer arrays nums1 and nums2 ，Returns the length of the longest subarray common to the two arrays . Example 1: enter: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] output: 3 Explanation: The longest common subarray is [3,2,1] . Example 2: enter: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] output: 5
1. Determine the dp array (dp table) and the meaning of the subscript
dp[i] [j] : A ending with subscript i - 1, and B ending with subscript j - 1, the longest repeating subarray length is dp[i] [j]. (Special note: "A ending with subscript i - 1" indicates that it must be a string ending with A[i-1] )
At this time, careful students should find out, what does dp[0][0] mean? It can't be an A array that ends with a subscript -1.
In fact, the definition of dp[i][j] also determines that i and j must start from 1 when we traverse dp[i][j].
Then a classmate asked, I defined dp[i][j] as A ending with subscript i, and B ending with subscript j, the longest repeating subarray length. can't you?
OK, OK! But it is a little more troublesome to implement. You can understand it by looking at the dp array state diagram below.
2. Determine the recurrence formula
According to the definition of dp[i][j], the state of dp[i][j] can only be deduced by dp[i - 1][j - 1].
That is, when A[i - 1] and B[j - 1] are equal, dp[i] [j] = dp[i - 1] [j - 1] + 1;
According to the recursion formula, it can be seen that traversing i and j starts from 1!
3. How to initialize the dp array
According to the definition of dp[i][j], dp[i][0] and dp[0][j] are actually meaningless!
But dp[i][0] and dp[0][j] need initial values, because for the convenience of recursive formula dp[i][j] = dp[i - 1] [j - 1] + 1;
So dp[i][0] and dp[0][j] are initialized to 0.
//version 1
class Solution {
public int findLength(int[] A, int[] B) {
int len1 = A.length;
int len2 = B.length;
int[][] dp = new int[len1+1][len2+1];
//initialization
for(int i = 0; i < len1; i++) {
dp[i][0] = 0;
}
for(int j = 0; j < len2; j++) {
dp[0][j] = 0;
}
int ans = 0;
//find longest common subarray
for(int i = 1; i <= len1; i++) {
for(int j = 1; j <= len2; j++) {
if(A[i-1] == B[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}else {
dp[i][j] = 0;
}
ans = Math.max(dp[i][j], ans);
}
}
return ans;
}
}
//Version 2
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int result = 0;
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
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;
result = Math.max(result, dp[i][j]);
}
}
}
return result;
}
}
LeetCode 516. Longest Palindromic Subsequence Return Length
gives you a string s ，Find the longest palindromic subsequence and return the length of that sequence. A subsequence is defined as a sequence formed by deleting some characters or not deleting any characters without changing the order of the remaining characters. Example 1: enter: s = "bbbab" output: 4 Explanation: A possible longest palindromic subsequence is "bbbb" . Example 2: enter: s = "cbbd" output: 2 Explanation: A possible longest palindromic subsequence is "bb" . hint: 1 <= s.length <= 1000 s Consists of lowercase English letters only
//version 1
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
if(len <= 1) return len;
int[][] dp = new int[len+1][len+1];
for(int i = 0; i < len; i++) {
dp[i][i] = 0;
}
char[] c = new char[len];
int k = 0;
for(int i = len-1; i >= 0; i--) {
c[k++] = s.charAt(i);
}
for(int i = 1; i <= len; i++) {
for(int j = 1; j <= len; j++) {
if(c[j-1] == s.charAt(i-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[len][len];
}
}
//Version 2
/*
**1.Determine the dp array (dp table) and the meaning of the subscript**
dp[i] [j]: The length of the longest palindromic subsequence of string s in the range [i, j] is dp[i][j].
**2.Determine the recursion formula**
In the question of judging palindrome substrings, the key logic is to see whether s[i] and s[j] are the same.
If s[i] is the same as s[j], then dp[i][j] = dp[i + 1][j - 1] + 2;
*/
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int[][] dp = new int[len + 1][len + 1];
for (int i = len - 1; i >= 0; i--) { // Traverse from back to front to ensure that the situation does not leak
dp[i][i] = 1; // initialization
for (int j = i + 1; j < len; 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], Math.max(dp[i][j], dp[i][j - 1]));
}
}
}
return dp[0][len - 1];
}
}
LeetCode 5. Longest Palindromic Substring
gives you a string s，turn up s The longest palindrome substring in . Example 1: enter: s = "babad" output:"bab" explain:"aba" Same answer. Example 2: enter: s = "cbbd" output:"bb"
brute force enumeration
public String longestPalindrome(String s) {
String res = "";
for(int i = 0; i < s.length(); i++) {
// When the longest palindrome substring is odd
String s_odd = palindrome(s, i-1, i+1);
// When the longest palindrome substring is even
String s_even = palindrome(s, i, i + 1);
// Compare the diffusion starting with i, the longest palindrome substring is odd and even, which one is longer
String curr = s_odd.length() > s_even.length() ? s_odd : s_even;
// Update the longest text substring
if(curr.length() > res.length()) res = curr;
}
return res;
}
private String palindrome(String s, int l, int r) {
while(l >= 0 && r < s.length()) {
// Diffusion to both ends to find the longest palindrome substring
if(s.charAt(l) == s.charAt(r)) {
l--;
r++;
}else break;
}
// Find the longest palindrome substring starting with l and r and return
return s.substring(l + 1, r);
}
dynamic programming
//version 1
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if(s == null || len < 1) return s;
int[][] dp = new int[len][len];
String ans = "";
int r = 1;
int l = 0;
String t = "";
for(int i = 1; i < len; i++) {
dp[i][i] = 1;
for(int j = 0; j < i; j++) {
if(s.charAt(i) == s.charAt(j)) {
if(i - j < 3) {
dp[j][i] = 1;
}else {
dp[j][i] = dp[j + 1][i - 1];
}
}else {
dp[j][i] = 0;
}
if(dp[j][i] == 1) {
int temp = i - j + 1;
if(temp > r) {
r = temp;
l = j;
}
}
}
}
return s.substring(l,r+l);
}
}
//Version 2
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if(len == 1) {
return s;
}
int maxLen = 1;
int start = 0;
boolean[][] dp = new boolean[len][len];
for(int j = 1; j < len; j++) {
for(int i = 0; i < j; i++) {
if(s.charAt(i) != s.charAt(j)) { // different characters on both sides
dp[i][j] = false; // must not be a palindrome
} else { // same characters on both sides
if(j - i < 3){ // Substring length is 2 or 3
dp[i][j] = true; // must be a palindrome substring
} else { // Substring length greater than 3
dp[i][j] = dp[i+1][j-1]; // relative to its preceding substring
}
}
if(dp[i][j] && (j-i+1 > maxLen)) {
maxLen = j - i + 1;
start = i;
}
}
}
return s.substring(start, start + maxLen);
}
LeetCode 1027. Longest Arithmetic Sequence
gives you an array of integers nums，return nums The length of the longest equidistant subsequence. Think back, nums A subsequence of is a list nums[i1], nums[i2], ..., nums[ik] ，and 0 <= i1 < i2 < ... < ik <= nums.length - 1. and if seq[i+1] - seq[i]( 0 <= i < seq.length - 1) are the same, then the sequence seq is equal. Example 1: enter: nums = [3,6,9,12] output: 4 explain: The entire array is an arithmetic progression with a tolerance of 3. Example 2: enter: nums = [9,4,7,2,10] output: 3 explain: The longest arithmetic subsequence is [4,7,10]. Example 3: enter: nums = [20,1,15,3,10,5,8] output: 4 explain: The longest arithmetic subsequence is [20,15,10,5].
brute force enumeration
class Solution {
public int longestArithSeqLength(int[] nums) {
//brute force enumeration every two values
int len=nums.length;int max=2;int max1=2;
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
int k=nums[i]-nums[j];int left=nums[j];
for(int x=j+1;x<len;x++){
if(left==nums[x]+k){
max++;
left=nums[x];
if(max>max1)max1=max;
}
}
max=2;
}
}
return max1;
}
}
dynamic programming
class Solution {
public int longestArithSeqLength(int[] nums) {
//The meaning of the dp[i][j] is the maximum index length of the element ending with index i with a tolerance of j
//Considering that the tolerance can be negative and the data range is [0,500] i.e. the tolerance range is [-500,500] so adding 500 before each tolerance is guaranteed to be an integer
int [][]dp = new int[nums.length][1001];
int ans = 1;
for(int i = 0; i < nums.length; i++)
{
for(int j = 0; j < i; j++)
{
int dif = nums[i] - nums[j] + 500;//Indicates the tolerance of the arithmetic sequence with i as the first-to-last number and j as the second-to-last number
dp[i][dif] = Math.max(dp[i][dif],dp[j][dif] + 1);
ans = Math.max(ans,dp[i][dif]);
}
}
return ans + 1;
}
}
LeetCode 873. The length of the longest Fibonacci subsequence
if the sequence X_1, X_2, ..., X_n If the following conditions are met, it is said to be Fibonacci of:
n >= 3
for all i + 2 <= n，have X_i + X_{i+1} = X_{i+2}
Given a strictly increasing array of positive integers to form a sequence arr ，turn up arr The length of the longest Fibonacci-like subsequence in . If one does not exist, return 0 .
(Recall that the subsequence is derived from the original sequence arr derived from , it is derived from arr deletes any number of elements (or none) from the list without changing the order of the remaining elements. E.g, [3, 5, 8] Yes [3, 4, 5, 6, 7, 8] a subsequence of )
Example 1:
enter: arr = [1,2,3,4,5,6,7,8]
output: 5
explain: The longest Fibonacci subsequence is [1,2,3,5,8] .
Example 2:
enter: arr = [1,3,7,11,12,14,18]
output: 3
explain: The longest Fibonacci subsequence has [1,11,12],[3,11,14] as well as [7,11,18] .
hint:
3 <= arr.length <= 1000
1 <= arr[i] < arr[i + 1] <= 10^9
//version 1
class Solution {
public int lenLongestFibSubseq(int[] A) {
int len = A.length;
if(len <= 2) return len;
int[][] dp = new int[len][len];//dp The length of the longest Fibonacci subsequence with A[i] as the last number
for(int i = 0; i < len; i++) {
Arrays.fill(dp[i], 2);//initialization
}
int ans = 0;
//Select two elements from the previous array, and increase the length by one if they are equal
int l = 0;
int r = 0;
for(int i = 1; i < len; i++) {
r = i - 1;
l = 0;
while(l < r) {
int sum = A[l] + A[r];
if(sum == A[i]) {
dp[r][i] = Math.max(dp[r][i], dp[l][r] + 1);
ans = Math.max(ans, dp[r][i]);
l++;
r--;
}else if(sum < A[i]){
l++;
}else {
r--;
}
}
}
return ans;
}
}
//Version 2
class Solution {
public int lenLongestFibSubseq(int[] A) {
//Start with i, the next is j
int max = 2;
for(int i = 0; i < A.length; i++){
for(int j = i + 1; j < A.length; j++){
int tmpI = A[i];
int tmpJ = A[j];
int sum = tmpI + tmpJ;
int cur = 2;
//exist
while(Arrays.binarySearch(A, sum) >= 0){
tmpI = tmpJ;
tmpJ = sum;
sum = tmpI + tmpJ;
cur++;
}
max = Math.max(max, cur);
}
}
return max < 3 ? 0 : max;
}
}