Re: [閒聊] 每日LeetCode

[pandix (麵包屌)]

1035. Uncrossed Lines

兩個 integer array nums1, nums2

如果 nums1[i] == nums2[j] 就可以在他們中間畫一條線

問你最多能畫幾條不交叉的線


Example 1:
https://assets.leetcode.com/uploads/2019/04/26/142.png
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 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


思路:
1.假設畫出來的線的值是 nums3 好了

nums3 會是 nums1 的 subsequence  同時也會是 nums2 的 subsequence

題目就等於說要找最長的共同 subsequence

蛤 LCS!


class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(1,m+1):
            for j in range(1,n+1):
                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])

        return dp[-1][-1]


--

蛤?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.252.3.181 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1683826413.A.B35.html
推 Ericz7000: 大師
推 Rushia: 我的超人