数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的无交叉线
假设我们在两条独立的水平线上写下了数组 A 和 B 的整数（按照给定的顺序）。现在，我们可以画连接线：一条连接两个数字 A[i] 和 B[j] 的直线，条件是 -
A[i] == B[j];
我们绘制的线不与任何其他连接线（非水平线）相交。
我们必须记住，连接线即使在端点处也不能相交 - 每个数字只能属于一条连接线。找到连接线的最大数量。因此，如果输入类似于 [1,4,2] 和 [1,2,4]，则输出将为 2。
| 1 | 4 | 2 |
| 1 | 2 | 4 |
我们可以在图中绘制 2 条无交叉线。我们无法绘制 3 条无交叉线，这是因为从 A[1]=4 到 B[2]=4 的线将与从 A[2]=2 到 B[1]=2 的线相交。
为了解决这个问题，我们将遵循以下步骤 -
定义一个名为 solve() 的方法，它将接收 i、j、数组 A、数组 B 和矩阵 dp
如果 i 超出数组 A 的范围，则返回 0
如果 j 超出数组 B 的范围，则返回 0
nj := j
当 nj < B 的大小且 B[nj] 不等于 A[i] 时
将 nj 增加 1
当 nj < B 的大小时，temp := 1，否则为 0
ret := (solve(i + 1, j, A, B, dp) 和 temp) 以及 solve(i + 1, nj + 1, A, B, dp) 的最大值
dp[i, j] := ret 并返回 ret
从主方法
n := A 的大小，m := B 的大小
创建一个大小为 n x m 的矩阵 dp，并将其填充为 – 1
调用 solve(0, 0, A, , dp)
让我们看看以下实现以获得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(int i, int j, vector <int>&A, vector <int>&B, vector <
vector <int> >& dp){
if(i >= A.size()) return 0;
if(j >= B.size()) return 0;
if(dp[i][j] != -1) return dp[i][j];
int nj = j;
while(nj < B.size() && B[nj] != A[i]) nj++;
int ret = max(solve(i + 1, j, A, B, dp), (nj < B.size() ? 1 :
0) + solve(i + 1, nj + 1, A, B, dp));
return dp[i][j] = ret;
}
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
int n = A.size();
int m = B.size();
vector < vector <int > > dp(n, vector <int>(m, -1));
return solve(0, 0, A, B, dp);
}
};
main(){
vector<int> v1 = {1,4,2};
vector<int> v2 = {1,2,4};
Solution ob;
cout << (ob.maxUncrossedLines(v1, v2));
}输入
[1,4,2] [1,2,4]
输出
2
更新于: 2020年4月30日
177 次查看
广告