Medium
,Array
,DP
You are given two integer arrays nums1
and nums2
. We write the integers of nums1
and nums2
(in the order they are given) on two separate horizontal lines.
We may draw connecting lines: a straight line connecting two numbers nums1[i]
and nums2[j]
such that:
nums1[i]
== nums2[j]
, andNote that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).
Return the maximum number of connecting lines we can draw in this way.
Example 1:
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.
Example 2:
Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3
Example 3:
Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2
Constraints:
nums1.length
, nums2.length
<= 500nums1[i]
, nums2[j]
<= 2000讀完題目就覺得超像LCS,快速寫一個遞迴版本立刻TLE…
放上來給大家笑一下
function maxUncrossedLines(nums1, nums2) {
const m = nums1.length;
const n = nums2.length;
function LCS(i, j) {
if (i === m || j === n) return 0;
if (nums1[i] === nums2[j]) {
return LCS(i + 1, j + 1) + 1;
}
return Math.max(LCS(i + 1, j), LCS(i, j + 1));
}
return LCS(0, 0);
}
下面這個才會過
function maxUncrossedLines(nums1, nums2) {
const m = nums1.length;
const n = nums2.length;
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (nums1[i - 1] === nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
MarsgoatMay 11, 2023
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int counter = 0;
int start_y = 0;
for (int x = 0 ; x< nums1.size(); x++)
{
for (int y = start_y; y<nums2.size(); y++)
{
if (nums1[x] == nums2[y])
{
counter++;
start_y = y + 1;
break;
}
}
}
return counter;
}
};
上面這個會顯而易見的 Failed,我再想想
skylanlyMay 12, 2023