程序在python中删除k个数字后查找相邻值的最大差

假设我们有一个称为nums的数字列表,并且它们按升序排序,我们必须从列表中删除k个值,以使任意两个相邻值之间的最大差值尽可能小,最后找到该差值。

因此,如果输入像nums = [15,20,30,400,1500] k = 2,那么输出将是10,就像我们删除[400,1500]以获得20和30的差一样。

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

  • abs_diff:=以num为单位的每个连续元素的差异列表

  • 定义一个功能dp()。这需要i,j,cnt

  • 如果cnt等于0,则

    • m:= m和abs_diff [k]的最大值

    • m:= 0

    • 对于范围i至j的k

    • 返回m

    • 返回dp(i + 1,j,cnt-1)和dp(i,j-1,cnt-1)的最小值

    • 从主要方法执行以下操作:

    • 返回dp(0,abs_diff的大小-1,k)

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

    例 

    class Solution:

       def solve(self, nums, k):

          abs_diff = [nums[i] - nums[i - 1] for i in range(1, len(nums))]

          def dp(i, j, cnt):

             if cnt == 0:

                m = 0

                for k in range(i, j + 1):

                   m = max(m, abs_diff[k])

                return m

             return min(dp(i + 1, j, cnt - 1), dp(i, j - 1, cnt - 1))

          return dp(0, len(abs_diff) - 1, k)

         

    ob = Solution()nums = [15, 20, 30, 400, 1500]

    k = 2

    print(ob.solve(nums, k))

    输入值

    [15, 20, 30, 400, 1500], 2

    输出结果

    10

    以上是 程序在python中删除k个数字后查找相邻值的最大差 的全部内容, 来源链接: utcz.com/z/343249.html

    回到顶部