数组/字符串-子序列

2019-05-21
#Coding-Data View

数组/字符串-子序列

特点：

  1. 要保持相对顺序
  2. 不一定相邻

难点：

  • 不确定序列从哪里开始 ( 后缀思考，固定起点， 向后遍历所有 )
  • 不确定元素之间的间隔 ( 用题目性质来确定 )
  • 不确定序列在哪里结束 ( 前缀思考，固定终点， 向前遍历所有 )

所以就只能以遍历到当前状态来考虑,多用DP来解决

需要考虑的问题:

  • 在跨元素的情况下怎么保持关系？( 用题目性质来保持 )

题目

满足某种性质的子序列

这些性质将子序列的元素连接起来，在定义子问题的时候需要考虑组成这些性质的要素。

873. Length of Longest Fibonacci Subsequence

初始思路：

dp[i]: 以i为结尾的最长Fibonacci子序列个数

在跨元素的情况下怎么保持关系？

dp[i]和dp[i-1]之间的关系？

思路纠正：

dp[i]: 以i为结尾的最长Fibonacci子序列个数

这道题虽然是一个数组的问题，但是只考虑以i结尾的情况还不足以定义一个Fib序列。Fib序列至少需要两个元素才能构成，所以将子问题定义成以(i,j)结尾的情况。

子问题定义：dp[i][j]以i,j结尾的Fib子序列的最长的长度 (前缀思考方式)

在跨元素的情况下怎么保持关系？

子问题之间的联系: 根据Fib序列的定义，用A[j]-A[i]将另一个构成Fib序列的X找出来。但不确定这个X是否在原数组中，

  • 如果原数组中存在X，而且它的下标k在i之前 and k没有越界(k>=0)，那么(i,j)Fib序列就向前扩展到了k，增加了一个长度
  • 如果它不在，那么(i,j)构成的Fib序列只能是2

为了便于查询下标k，需要用一个map来保存Value->Key的映射。

怎么保证不漏掉序列？

j每往后走一次，为了不漏掉每一个扩充序列的可能，都要用i向前遍历一遍。

1
2
for j : 0 -> n-1
    for i : j-1 -> 0

最后的结果在哪里？

虽然dp[i][j]记录所有可能Fib序列长度，但结果不一定就是dp[n-2][n-1]，而应该是dp数组中最大的数: max(dp)

代码实现:

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
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int n = A.size();
        
        map<int, int> m; 
        for (int i = 0; i < n; i++) m[A[i]] = i;
        
        vector<vector<int>> dp(n, vector<int>(n, 2)); // corner case: 2
        
        int res = 0;
        for (int j = 1; j < n; j++) 
        {
            for (int i = j-1; i >= 0; i--) 
            {
                int k = A[j]-A[i];
                if (m.find(k) != m.end() && k < i)
    				dp[i][j] = max(dp[i][j], dp[k][i] + 1); // dp[k][i] + 1 extend to A[k] 
                res = max(res, dp[i][j]);
            }
        }
    	
    	
    	return res > 2 ? res : 0;
    }
};

1027. Longest Arithmetic Sequence

初始思路：

dp[i]: 以i为结尾的最长Arithmetic子序列个数

在跨元素的情况下怎么保持关系？

前缀

dp[i]和dp[i-1]之间的关系？

思路纠正：

子问题定义:

构成等差数列的要素有：一个元素a和公差d

需要记录以A[i]结尾的所有可能的公差的等差数列,最长的的长度

1
map<int, map<int, int> > dp

dp中第一个int表示以A[i]结尾中的i,然后这些序列中的公差d是不确定的，因为任何前后两个元素都可以形成一个潜在的等差数列，嵌套的map<int, int>中第一个int表示公差d，第二个int表示最多到下标i形成的等差数列的最长的长度。

在跨元素的情况下怎么保持关系？

子问题之间的联系:

当考察到下标为i的元素时，需要遍历i之前的每一个元素j。因为j之前的每一个元素A[j]都有可能与A[i]形成等差数列。

1
2
for i: 0 -> n-1
    for j: i-1 -> 0

根据等差数列的定义，求出A[i] - A[j]的公差d，然后查看到j为止，公差为d的等差数列的个数

  • 如果之前有值，那么因为A[i]的存在，扩展了这个等差数列，所以长度加1
  • 如果之前没有值，那么A[j] A[i]是第一个以d为公差的等差数列，A[j][d] = 2

选最大的A[i][j],继续下一个i

最后的结果在哪里？

dp最大元素是最终的结果，因为以最后一个元素截止的等差数列不一定最长

代码实现：

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
class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        
        unordered_map<int, unordered_map<int, int> > memo;
        int res = 2;
        int N = A.size();
        
        for(int i = 1; i < N; ++i)
        {
            for(int j = i - 1; j >= 0; --j)
            {
                int d = A[i] - A[j];
                
                int potential_to_i = memo[j].count(d) == 0 ? 2 : memo[j][d] + 1;
                
                memo[i][d] = max(memo[i][d], potential_to_i); //guarantee max so far
                
                res = max(res, memo[i][d]);
            }
        }
        
        return res;
        
    }
};

334. Increasing Triplet Subsequence 固定长度的递增子序列

子问题定义:

memo[k]以k结尾的递增子序列的最长度

子问题之间的联系:

如果当前元素A[i]大于之前的…

是不是还需要保存一个i-1之前最大的元素 ?

要不然怎么知道是是否扩充了序列，还是开启了一个新序列？

1
2
3
4
5
6
7
8
9
10
11
12
bool increasingTriplet(vector<int>& nums, int k = 3) {
    vector<int> inc(k - 1, INT_MAX);
    for (int i : nums) {
        auto p = lower_bound(inc.begin(), inc.end(), i);
        if (p == inc.end())
            return true;
        *p = i;
    }
    return false;
}
// https://leetcode.com/problems/increasing-triplet-subsequence/discuss/78997/Generalization-in-Python

300. Longest Increasing Subsequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> dp;
for (auto n : nums)
{
    auto iter = lower_bound(begin(dp), end(dp), n);
    if (iter == end(dp))
    {
        dp.push_back(n);
        continue;
    }
    if (*iter > n)
        *iter = n;
}
return dp.size();
// https://leetcode.com/problems/increasing-triplet-subsequence/discuss/79053/My-way-to-approach-such-a-problem.-How-to-think-about-it-Explanation-of-my-think-flow.

T: O(NlogN)
S: O(N)

376. Wiggle Subsequence (未完待续)

dual status 两个dp状态

dp[i]: 以i为结尾的最长wiggle子序列个数

在跨元素的情况下怎么保持关系？

递推关系？

1
2
[1  7  4   9  2  5]
[0  1 -1   1 -1  1]

需要一个变量来保存之前的大小关系吗? 需要

Comments: