Leetcode 1187：使数组严格递增（超详细的解法！！！）

小小码 • 2023-11-07 13:30 • 未分类 • 阅读 96

大家好，我是考100分的小小码，祝大家学习进步，加薪顺利呀。今天说一说Leetcode 1187：使数组严格递增（超详细的解法！！！）,希望您对编程的造诣更进一步.

给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。

每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。

如果无法让 arr1 严格递增，请返回 -1。

示例 1：

输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
输出：1
解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。

示例 2：

输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1]
输出：2
解释：用 3 来替换 5，然后用 4 来替换 3，得到 arr1 = [1, 3, 4, 6, 7]。

示例 3：

输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
输出：-1
解释：无法使 arr1 严格递增。

提示：

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

解题思路

这个问题和之前的问题Leetcode 801：使序列递增的最小交换次数（超详细的解法！！！）非常类似。首先不难想到动态规划，对于这个问题arr1中的每个元素有两种状态：一种是原来的值，一种是arr2中的值。所以可以定义 $f(i_1,i_2,pre)$ 表示arr1中的 $i_1$ 位置，arr2中的 $i_2$ 位置，并且arr1[i1]之前的元素是pre时的最少交换此时，那么

$f(i_1,i_2,pre)=1+f(i_1+1,i_2,arr2[i_2])$
$f(i_1,i_2,pre)=f(i_1+1,i_2,arr1[i_1])$

这里还有一个小问题，就是arr2[i2]我们要怎么找？我们可以先对arr2排序，然后通过upper_bound()来找大于pre的第一个元素位置。关于upper_bound()可以看Leetcode 二分法问题总结（超详细！！！）

from functools import lru_cache
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        l1, l2 = len(arr1), len(arr2)
        arr2.sort()
        
        @lru_cache(None)
        def dfs(i1, i2, pre):
            if i1 >= l1:
                return 0
            i2 = bisect.bisect(arr2, pre)
            return min(1 + dfs(i1 + 1, i2, arr2[i2]) if i2 < l2 else l2+1,\
                       dfs(i1 + 1, i2, arr1[i1]) if pre < arr1[i1] else l2+1)
        
        res = dfs(0, 0, float("-inf"))
        return -1 if res > l2 else res

使用lru_cache已经是惯用伎俩了。使用记忆化搜索可以实现的问题，我们当然也可以通过动态规划来做。使用动态规划，无非就是存储之前的状态，前面已经讨论过状态是什么了，这里需要思考的是怎么存储它。我这里不使用数组存储，而是通过字典，这简化了我们操作。通过字典存储前一个位置的所有可能，key存储的是交换次数，value存储的是对应的前一个元素值。

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        l1, l2 = len(arr1), len(arr2)
        arr2.sort()
        
        dp = { 
   0: arr1[0], 1: arr2[0]}
        for i in range(1, l1):
            new_dp = { 
   }
            for k, v in dp.items():
                if arr1[i] > v and (k not in new_dp or new_dp[k] > arr1[i]):
                    new_dp[k] = arr1[i]
                j = bisect.bisect(arr2, v)
                if j < l2 and (k + 1 not in new_dp or new_dp[k + 1] > arr2[j]):
                    new_dp[k+1] = arr2[j]
            dp = new_dp
        if len(dp) == 0:
            return -1
        return min(dp.keys())

如果len(dp)是空那么自然就没有解，否则最后的结果就是min(dp.keys())。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/37369.html

Leetcode 1187：使数组严格递增（超详细的解法！！！）

相关推荐

发表回复