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

Pythonでターゲットを取得するためにシンボルを配置する方法をいくつか見つけるプログラムはありますか?


numsと呼ばれる非負の数のリストがあり、整数のターゲットもあるとします。式がターゲットと等しくなるように、+と-をnumで配置する方法の数を見つける必要があります。

したがって、入力がnums =[2、3、3、3、2] target =9のようである場合、出力は2になります。これは、-2 + 3 + 3 + 3+2および2+3+を持つことができるためです。 3 + 3 –2。

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

  • s:=numsのすべての数値の合計

  • (s + target)mod 2が0と同じでない場合、またはtarget> sの場合、

    • 0を返す

  • W:=(s +ターゲット)の商/ 2

  • dp1:=サイズのリスト(W + 1)および0で埋める

  • dp1 [0]:=1

  • dp2:=サイズ(W + 1)のリストと0で埋める

  • 0からnumsのサイズの範囲のiの場合、実行します

    • 0からW+1の範囲のjの場合、実行

      • j> =nums [i]の場合、

        • dp2 [j]:=dp2 [j] + dp1 [j --nums [i]]

    • 0からW+1の範囲のjの場合、実行

      • dp1 [j]:=dp1 [j] + dp2 [j]

      • dp2 [j]:=0

  • dp1の最後の要素を返す

理解を深めるために、次の実装を見てみましょう。

class Solution:
   def solve(self, nums, target):
      s = sum(nums)
      if (s + target) % 2 != 0 or target > s:
         return 0
      W = (s + target) // 2
      dp1 = [0] * (W + 1)
      dp1[0] = 1
      dp2 = [0] * (W + 1)
      for i in range(len(nums)):
         for j in range(W + 1):
            if j >= nums[i]:
               dp2[j] += dp1[j - nums[i]]
            for j in range(W + 1):
               dp1[j] += dp2[j]
               dp2[j] = 0
         return dp1[-1]

ob = Solution()
nums = [2, 3, 3, 3, 2]
target = 9
print(ob.solve(nums, target))

入力

[2, 3, 3, 3, 2], 9

出力

2

  1. Pythonでお互いを攻撃できないようにn個のルークを配置する方法をいくつか見つけるプログラム

    サイズnxnのチェス盤を表す数nがあるとします。お互いに攻撃できないように、n個のルークを配置できる方法の数を見つける必要があります。ここでは、チェス盤の一部のセルが占有されている場合と、セルが占有されていない場合の2つの方法が異なると見なされます。 (ルークが同じ行または同じ列にある場合、ルークは互いに攻撃する可能性があることを私たちは知っています。) したがって、入力が3のような場合、出力は6になります これを解決するには、次の手順に従います- f=nの階乗 fを返す 理解を深めるために、次の実装を見てみましょう- 例 import math class Solution:

  2. Pythonで階段を上る方法をいくつ見つけるかをプログラムする

    n段の階段があり、一度に1段または2段の階段を上ることができるとします。階段を上るユニークな方法の数を返す関数を定義する必要があります。 ステップの順序は変更しないでください。そのため、ステップの異なる順序はそれぞれ1つの方法としてカウントされます。答えが非常に大きい場合は、結果を10 ^ 9+7で変更します したがって、入力がn =5のような場合、8つの固有の方法があるため、出力は8になります- 1、1、1、1、1 2、1、1、1 1、2、1、1 1、1、2、1 1、1、1、2 1、2、2 2、1、2 2、2、1 これを解決するには、次の手順に従いま