Python程式：查詢最小分組的最大可能值

假設我們有一個名為nums的數字列表和另一個值k。我們必須將列表分成k個連續的組。最小組是所有組中和最小的組。因此，找到最小組的最大可能值。

例如，如果輸入類似於nums = [2, 6, 4, 5, 8] k = 3，則輸出將為8，因為我們可以將列表分成三個組，例如：[2, 6]，[4, 5]，[8]。因此，最小組的和為8。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式is_divisible()。這將接收目標值。

  • 如果目標值target ≤ 1，則

    • 返回True

  • num_chunks := 0, current_sum := 0

  • 對於nums中的每個x，執行：

    • current_sum := current_sum + x

    • 如果current_sum ≥ target，則

      • current_sum := 0

      • num_chunks := num_chunks + 1

      • 如果num_chunks等於k，則

        • 返回True

  • 返回False

  • 在主方法中執行以下操作：

  • left := 1

  • right := (nums中所有元素的總和) / k + 1

  • 當left < right - 1時，執行：

    • mid := (left + right) / 2

    • 如果is_divisible(mid)為True，則

      • left := mid

    • 否則，

      • right := mid

  • 返回left

示例 (Python)

讓我們看看下面的實現來更好地理解：

 線上演示

class Solution:
   def solve(self, nums, k):
      def is_divisible(target):
         if target <= 1:
            return True
         num_chunks = 0
         current_sum = 0
         for x in nums:
            current_sum += x
            if current_sum >= target:
               current_sum = 0
               num_chunks += 1
               if num_chunks == k:
                  return True
         return False
      left = 1
      right = sum(nums) // k + 1
      while left < right - 1:
         mid = (left + right) // 2
         if is_divisible(mid):
            left = mid
         else:
            right = mid
      return left
ob = Solution()
nums = [2, 6, 4, 5, 8]
k = 3
print(ob.solve(nums, k))

輸入

[2, 6, 4, 5, 8], 3

輸出

8

更新於：2020年12月22日

207 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告