题目描述
给出两个长度为 n 的整数序列,求它们的最长公共子序列(LCS)的长度,保证第一个序列中所有元素都不重复。
注意:
第一个序列中的所有元素均不重复。
第二个序列中可能有重复元素。
一个序列中的某些元素可能不在另一个序列中出现。
输入格式
第一行包含一个整数 n。
接下来两行,每行包含 n 个整数,表示一个整数序列。
输出格式
输出一个整数,表示最长公共子序列的长度。
数据范围
1≤n≤106,
序列内元素取值范围 [1,106]。
样例
输入样例1:
5
1 2 3 4 5
1 2 3 4 5
输出样例1:
5
输入样例2:
5
1 2 3 5 4
1 2 3 4 5
输出样例2:
4
算法1
(LCS->LIS 二分加速) $O()$
数组1中的元素不重复,则元素与index就有了一一对应的关系
数组2中的元素在数组1的下标找出来,组成nums数组
数组2中的序列要想在数组1中存在,必然对应的index是从左往右的(递增的)
LCS转化成了数组2中数字在数组1中的index的LIS问题
LIS两种解法
LC300题
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/cpython3-1dong-tai-gui-hua-dp-2tan-xin-h-mlyt/
我的C++死活过不了。一直TLE.放弃了
经过“代码搬运工”的提醒和指点。AC了。。
最后一轮优化竟然是把 cin >> ai 换成 scanf(“%d”, & ai);
时间复杂度
参考文献
python3 代码
import bisect
an = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
dic = dict()
for i, x in enumerate(a):
dic[x] = i
nums = [] #b中元素在a中的下标
for y in b:
if y in dic:
nums.append(dic[y])
#LIS最长上升子序列
n = len(nums)
rec = []
for x in nums:
idx = bisect.bisect_left(rec, x)
if idx == len(rec):
rec.append(x)
else:
rec[idx] = x
print(len(rec))
c++
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], nums[N], ID[N];
int main()
{
int n; cin >> n;
int ai;
for (int i = 1; i < n + 1; i ++)
{
scanf("%d", &ai);
ID[ai] = i;
}
int bi;
for (int i = 1; i < n + 1; i ++)
{
scanf("%d", & bi);
nums[i] = ID[bi];
}
//变成了LIS最长上升子序列问题
vector<int> rec;
for (int i = 1; i < n + 1; i ++)
{
if (nums[i] == 0)
continue;
int & x = nums[i];
if (rec.size() == 0 || rec.back() < x)
{
rec.push_back(x);
continue;
}
int idx = lower_bound(rec.begin(), rec.end(), x) - rec.begin();
rec[idx] = x;
}
cout << rec.size() << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
@代码搬运工。谢谢大佬指点。我写了好久,一直TLE。我现在去试试。
C++只能使用2个for循环,读取b数组的时候同时处理,另外不能用unordered_map记录a数组的下标,只能使用数组,这题时间卡的太紧了