leetcode 1537. Get the Maximum Score(python)

語言: CN / TW / HK

「這是我參與11月更文挑戰的第30天,活動詳情檢視:2021最後一次更文挑戰

描述

You are given two sorted arrays of distinct integers nums1 and nums2.

A valid path is defined as follows:

  • Choose array nums1 or nums2 to traverse (from index-0).
  • Traverse the current array from left to right.
  • If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

The score is defined as the sum of uniques values in a valid path.Return the maximum score you can obtain of all possible valid paths. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].

Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].

Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].

Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

Note:

1 <= nums1.length, nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 and nums2 are strictly increasing.

解析

根據題意,給定兩個不同整數 nums1 和 nums2 的已經排序的陣列。有效路徑定義如下:

  • 選擇要遍歷的陣列 nums1 或 nums2(從索引 0 開始)。
  • 從左到右遍歷當前陣列。
  • 如果您正在讀取 nums1 和 nums2 中都存在的某個值,則可以將路徑更改為另一個數組。 (在有效路徑中只考慮一個重複值)。

分數定義為有效路徑中不同值的總和,返回您可以獲得的所有可能有效路徑的最大分數。 由於答案可能太大,將其取模 10^9 + 7 返回。

其實題意結合例子一還是很好理解的,兩個陣列的轉換位置正好是兩個陣列都有的數字,這樣可以保證有效路徑總是升序排列的。最粗暴的方法就是找出所有的可能的路徑然後找出擁有最大和的陣列。但是隻要有兩個陣列有相同的數字就會分出兩條路,這種時間複雜度為 O(2^n) ,肯定是超時的。

其實我們可以用貪心的思想,每當找到兩個陣列共同擁有的數字的時候,就計算兩個陣列各自在該數字之前的數字總和,比較之後得到一個較大的和,重複這個過程,如下所示有兩個字串 A 和 B ,其中的 O 表示相同的字元:

  • A : XXXXOZZZZOXXX
  • B : TTTOSSSSOPPP

現比較 XXXXO 和 TTTO 的各自總和,取最大的值作為找到第一個 O 時候的最大和 a ,然後比較 ZZZZO 和 SSSSO 的各自總和,取最大的值再加 a 作為找到第二個 O 時候的最大和 b ,然後再把各自剩餘的數字 XXX 和 PPP 加起來得到 s1 和 s2 ,取較大值即為結果。

解答

class Solution(object):
    def maxSum(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        i = j = s1 = s2 = 0
        m = len(nums1)
        n = len(nums2)
        while i<m or j<n:
            if i==m:
                s2 += nums2[j]
                j += 1
            elif j==n:
                s1 += nums1[i]
                i += 1
            elif nums1[i] < nums2[j]:
                s1 += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                s2 += nums2[j]
                j += 1
            elif nums1[i] == nums2[j]:
                s1 = max(s1+nums1[i], s2+nums2[j])
                s2 = s1
                i += 1
                j += 1
        return max(s1, s2)%(10**9+7)

執行結果

Runtime: 484 ms, faster than 88.46% of Python online submissions for Get the Maximum Score.
Memory Usage: 21.9 MB, less than 42.31% of Python online submissions for Get the Maximum Score.

原題連結:https://leetcode.com/problems/get-the-maximum-score/

您的支援是我最大的動力