3269：构建两个递增数组（★★）

Ian

2024-09-01 约 407 字预计阅读 1 分钟次阅读

力扣第 3269 题

题目

给定两个只包含 0 和 1 的整数数组 nums1 和 nums2，你的任务是执行下面操作后使数组 nums1 和 nums2 中最大可达数字 尽可能小。

将每个 0 替换为正偶数，将每个 1 替换为正奇数。在替换后，两个数组都应该递增并且每个整数至多被使用一次。

返回执行操作后最小的最大可达数字。

示例 1：

输入：nums1 = [], nums2 = [1,0,1,1]

输出：5

解释：

在替换之后， nums1 = [] 与 nums2 = [1, 2, 3, 5]。

示例 2：

输入：nums1 = [0,1,0,1], nums2 = [1,0,0,1]

输出：9

解释：

有最大元素 9 的一种替换方式， nums1 = [2, 3, 8, 9] 与 nums2 = [1, 4, 6, 7]。

示例 3：

输入：nums1 = [0,1,0,0,1], nums2 = [0,0,0,1]

输出：13

解释：

有最大元素 13 的一种替换方式，nums1 = [2, 3, 4, 6, 7] 与 nums2 = [8, 10, 12, 13]。

提示：

0 <= nums1.length <= 1000
1 <= nums2.length <= 1000
nums1 和 nums2 只包含 0 和 1。

分析

按最大的是 nums1 末尾还是 nums2 末尾递推即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def minLargest(self, nums1: List[int], nums2: List[int]) -> int:
        m,n = len(nums1),len(nums2)
        f = [[inf]*(n+1) for _ in range(m+1)]
        f[0][0] = 0
        for i in range(m+1):
            for j in range(n+1):
                if i:
                    x = f[i-1][j]
                    x += 2 if (x+1)&1^nums1[i-1] else 1
                    f[i][j] = min(f[i][j],x)
                if j:
                    x = f[i][j-1]
                    x += 2 if (x+1)&1^nums2[j-1] else 1
                    f[i][j] = min(f[i][j],x)
        return f[-1][-1]

2328 ms

目录

3269：构建两个递增数组（★★）

题目

分析

解答