leetcode 1035 不相交的线

简介: leetcode 1035 不相交的线

不相交的线

91d83ee20a1e4f59a770ae75fe3f48d8.png

动态规划

本题说是求绘制的最大连线数,其实就是求两个字符串的最长公共子序列的长度!

那么本题就和我们刚刚讲过的这道题目动态规划:1143.最长公共子序列 就是一样一样的了。

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1 , vector<int>(nums2.size()+1,0));
        for(int i=0 ; i<nums1.size();i++)
        {
            for(int j=0 ; j<nums2.size();j++)
            {
               if(nums1[i]==nums2[j])
                    dp[i+1][j+1] = dp[i][j]+1;
               else
                    dp[i+1][j+1] = max(dp[i+1][j] , dp[i][j+1]);
            }
        }
        // for(int i=0 ; i<nums1.size();i++)
        // {
        //     for(int j=0 ; j<nums2.size();j++)
        //     {
        //         cout<<dp[i][j]<<' ';
        //     }
        //     cout<<endl;
        // }
        return dp[nums1.size()][nums2.size()];
    }
};

二刷

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1 , 0));
        int result = 0;
        for(int i=1 ; i<=nums1.size() ;i++)
        {
            for(int j=1 ; j<=nums2.size() ; j++)
            {
                if(nums1[i-1] == nums2[j-1]) 
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
            }
        }
        // for(int i=1 ; i<=nums1.size() ;i++)
        // {
        //     for(int j=1 ; j<=nums2.size() ; j++)
        //         cout<<dp[i][j]<<' ';
        //     cout<<endl;
        // }
        return dp[nums1.size()][nums2.size()];
    }
};
相关文章
|
6月前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
46 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
6月前
|
Go
golang力扣leetcode 160.相交链表
golang力扣leetcode 160.相交链表
48 0
|
6月前
leetcode-1035:不相交的线
leetcode-1035:不相交的线
35 0
|
6月前
|
C++ Python
leetcode-160:相交链表
leetcode-160:相交链表
47 0
LeetCode | 160. 相交链表
LeetCode | 160. 相交链表
|
3月前
|
存储 Python
【Leetcode刷题Python】1496.判断路径是否相交
Leetcode第1496题"判断路径是否相交"的Python代码实现,通过使用字典存储方向和集合记录访问过的坐标点来检测路径是否与自身相交。
42 2
|
3月前
|
算法 Python
【Leetcode刷题Python】106.相交链表
采用双指针法来找出两个链表的相交起始节点,并详细解释了算法的时间和空间复杂度。
24 1
|
5月前
|
存储 算法 数据可视化
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
|
6月前
|
C++
[leetcode 链表] 反转链表 vs 链表相交
[leetcode 链表] 反转链表 vs 链表相交
|
6月前
|
C语言 C++ 索引
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表