首页 > itarticle > subsequence

subsequence

admin 11月 13, 2020 0

Subsequence problems are always also dp problems.

LC 392. Is Subsequence

Example 1:
s = “abc”, t = “ahbgdc”

Return true.

Example 2:
s = “axc”, t = “ahbgdc”

Return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
bool isSubsequence(string s, string t) {
       if(s == "")
           return true;
       int ind = 0;
       for(int i = 0; i < t.length(); i++){
           if(t[i] == s[ind]){
               ind++;
               if(ind == s.length())
                   return true;
           }
       }
       return false;
   }

LC 727. Minimum Window Subsequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
string (string S, string T) {
       int sl = S.length();
       int tl = T.length();
       vector<vector<int>> dp(sl, vector<int>(tl, -1));
       for(int i = 0; i < sl; i++){
           if(S[i] == T[0])
               dp[i][0] = i;
           else{
               if(i != 0)
                   dp[i][0] = dp[i-1][0];
           }
       }
       for(int i = 1; i < tl; i++){
           for(int j = 0; j < sl; j++){
               if(S[j] == T[i]){
                   if(j > 0)
                       dp[j][i] = dp[j-1][i-1];
               }else {
                   if(j > 0)
                       dp[j][i] = dp[j-1][i];
               }
           }
       }

       int len = INT_MAX;
       string res = "";
       for(int i = 0; i < sl; i++){
           if(dp[i][tl-1] != -1){
               if(len > i-dp[i][tl-1]+1){
                   len = i-dp[i][tl-1]+1;
                   res = S.substr(dp[i][tl-1], len);
               }
           }
       }
       return res;
   }

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
class Solution {
public:
    /*
    The count array is the dp structure that store the number of  increasing subsequence starts from the current number
    traverse all numbers behind the current number, assume the index of a number behind the current number is j, the index of the current number is i
    if nums[i] is smaller than nums[j] and the count[j] is largest in the numbers which are behind the current number, then count[i] is added by the count[j]
    The result is the largest one in the count array.
    */

  int lengthOfLIS(vector<int>& nums) {
      if(nums.size() == 0)
          return 0;
    vector<int> counts(nums.size(), 1);

    for(int i = (int)nums.size() - 2; i >= 0; i
        int iLargest = 0;
        for(int j = i + 1; j < nums.size(); j++){
            if(nums[i] < nums[j] && iLargest < counts[j]){
                iLargest = counts[j];
            }
        }
        if(iLargest > 0)
            counts[i] += iLargest;
    }
    int largest = counts[0];
    for(int i = 1; i < counts.size(); i++){
        if(largest < counts[i])
            largest = counts[i];
    }
    return largest;
}


};

354. Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Note:
Rotation is not allowed.

Example:

Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
class Solution {
public:
   static bool comp(pair<int, int> e1, pair<int, int> e2){
    if(e1.first == e2.first)
        return e1.second > e2.second;
    return e1.first < e2.first;
}


int maxEnvelopes(vector<pair<int, int>>& envelopes) {
    if(envelopes.size() == 0)
        return 0;
    sort(envelopes.begin(), envelopes.end(), comp);
    vector<int> dp(envelopes.size(), 1);
    for(int i = envelopes.size()-2; i >= 0; i--){
        int curLargest = 0;
        for(int j = i+1; j < envelopes.size(); j++){
            if(envelopes[j].second > envelopes[i].second && dp[j] > curLargest)
                curLargest = dp[j];
        }
        if(curLargest > 0)
            dp[i] += curLargest;
    }
    int largest = dp[0];
    for(int i = 1; i < dp.size(); i++){
        if(dp[i] > largest)
            largest = dp[i];
    }
    return largest;
}

};
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能