程序以查找严格制作列表所需的最少操作数python中增加

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有两个数字列表，称为A和B，它们的长度相同。现在考虑我们可以执行一个可以交换数字A [i]和B [i]的操作。我们必须找到使两个列表严格增加所需的操作数。

因此，如果输入像A = [2，8，7，10] B = [2，4，9，10]，那么输出将为1，因为我们可以在A中交换7而在B中交换9。列表将类似于A = [2，8，9，10]和B = [2，4，7，10]，它们都是严格增加的列表。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个功能dp()。这需要我，prev_swapped

  • 如果A的大小与i相同，则

    • 返回0

  • 否则当我等于0时

    • 返回dp（i + 1，False）和1 + dp（i + 1，True）的最小值

  • 除此以外，

    • ans：= dp（i + 1，False）

    • 如果A [i]> prev_B和B [i]> prev_A，则

    • 返回ans

    • ans：= ans的最小值，1 + dp（i + 1，True）

    • 返回1 + dp（i + 1，真）

    • 交换prev_A和prev_B

    • prev_A：= A [i-1]

    • prev_B：= B [i-1]

    • 如果prev_swapped为True，则

    • 如果A [i] <= prev_A或B [i] <= prev_B，则

    • 除此以外，

    • 从主方法调用函数dp(0,False)并返回其值作为结果

    让我们看下面的实现以更好地理解：

    范例程式码

    class Solution:
       def solve(self, A, B):
          def dp(i=0, prev_swapped=False):
             if len(A) == i:
                return 0
             elif i == 0:
                return min(dp(i + 1), 1 + dp(i + 1, True))
             else:
                prev_A = A[i - 1]
                prev_B = B[i - 1]
                if prev_swapped:
                   prev_A, prev_B = prev_B, prev_A
                if A[i] <= prev_A or B[i] <= prev_B:
                   return 1 + dp(i + 1, True)
                else:
                   ans = dp(i + 1)
                if A[i] > prev_B and B[i] > prev_A:
                   ans = min(ans, 1 + dp(i + 1, True))
                return ans
             return dp()ob = Solution()A = [2, 8, 7, 10]
    B = [2, 4, 9, 10]
    print(ob.solve(A, B))

    输入值

    [2, 8, 7, 10], [2, 4, 9, 10]

    输出结果

    1

    以上是 程序以查找严格制作列表所需的最少操作数python中增加 的全部内容， 来源链接： utcz.com/z/334701.html

    回到顶部