Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで最小グループの可能な最大値を見つけるプログラム


numsと呼ばれる数値のリストと別の値kがあるとします。リストをk個の連続したグループに分割する必要があります。最小のグループは、すべてのグループの中で合計が最小のグループです。したがって、最小のグループの可能な最大値を見つけます。

したがって、入力がnums =[2、6、4、5、8] k =3のような場合、リストを[2、6]、[4]のように3つのグループに分割できるため、出力は8になります。 、5]、[8]。したがって、最小グループの合計は8になります。

これを解決するには、次の手順に従います-

  • 関数is_divisible()を定義します。これはターゲットになります

  • ターゲットが<=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を返す

  • メインの方法から、次のようにします-

  • 左:=1

  • right:=(numsのすべての要素の合計)/ k + 1

  • 左<右-1、実行

    • mid:=(左+右)/ 2

    • is_divisible(mid)がtrueの場合、

      • 左:=中央

    • それ以外の場合

      • 右:=半ば

  • 左に戻る

例(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

  1. Pythonで指定された数値のセットを使用して式の可能な最大値を見つけるプログラム

    nums1とnums2という2つの配列があり、それらの要素数が同じNであるとします。ここで、1からNまでのN個の要素を持つ集合Sについて考えます。(nums1 [i1] + nums1[i2]+の値を見つける必要があります。 .. nums1 [ik])^ 2 +(nums2 [i1] + nums2 [i2] + ... nums2 [ik])^ 2ここで、{i1、i2、...ik}は集合Sの空でないサブセットです。 。 したがって、入力がnums1 =[-1、6] nums2 =[5、4]の場合、出力は106になります。 (-1)^ 2 +(5)^ 2 =26 (6)^ 2 +(4)

  2. Pythonで最大の建物の高さを見つけるプログラム

    値nと、制限と呼ばれるペアの別のリストがあるとします。都市にn棟の新しい建物を建てたいと思っています。ただし、制限はほとんどありません。私たちは一列に建てることができ、建物には1からnまでのラベルが付けられています。制限には2つのパラメーターがあるため、restrictions [i] =(id_i、max_height_i)は、id_iの高さがmax_height_i以下でなければならないことを示します。新しい建物の高さに関する市の制限は次のとおりです- 各建物の高さは0または正の値である必要があります。 最初の建物の高さは0でなければなりません。 隣接する2つの建物の高さ