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

假设我们有两个数字列表,称为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

    回到顶部