資料結構
網路
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 次檢視
廣告