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

Pythonを使用して配列を等しくするための最小操作を見つけるプログラム

値がnであると仮定し、n個の要素を持つ配列numを考えます。ここで、すべてのiに対してarr [i] =（2 * i）+1です。これで、1つの操作で、2つのインデックスxとyを選択できます。ここで、0 <=x、y

したがって、入力がn =4の場合、出力は4になります。nの場合、配列は[1,3,5,7]になります。最初の操作の後、[2,3,5,6]のような配列を作成できます。 ]、2番目の操作の後、[3,3,5,5]を作成し、次に3番目の[4,3,4,5]を作成し、最後に[4,4,4,4]を作成できます。これで、すべてが等しくなりました。

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

  • ans：=0

  • nが1と同じ場合、

    • ansを返す

  • q：=（n / 2）-1の商

  • j：=1

  • q> =0の場合、実行

    • ans：=ans +（n-j）

    • q：=q-1

    • j：=j + 2

  • ansを返す

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

例

def solve(n):
   ans=0
   if n==1:
      return ans
   q=(n//2)-1
   j=1
   while q>=0:
      ans=ans+(n-j)
      q-=1
      j+=2
   return ans
n = 4
print(solve(n))

入力

4

出力

4

  1. Pythonを使用してバイナリグリッドを配置するための最小スワップを見つけるプログラム

    nxnのバイナリ行列があるとします。 1つのステップで、隣接する2つの行を選択し、それらを入れ替えるような操作を実行できます。行列の主対角線より上のすべてのノードが0になるように、必要な最小スワップの数をカウントする必要があります。そのような解決策がない場合は、-1を返します。 したがって、入力が次のような場合 0 1 0 0 1 1 1 0 0 -であるため、出力は2になります。 これを解決するには、次の手順に従います。 n：=行列の行数 m：=サイズnの配列を作成し、nで埋めます 0からn-1の範囲のiの

  2. Pythonで1つの文字列を他の文字列のサブ文字列にするために必要な最小数の操作を見つけるプログラム

    2つの文字列sとtがあるとすると、sがtをsの部分文字列にするために必要な操作の最小量を見つける必要があります。これで、各操作で、s内の任意の位置を選択し、その位置の文字を他の任意の文字に変更できます。 したがって、入力がs =abbpqr、t =bbxyの場合、サブストリング bbpqを取得して、pをxに、qをに変更できるため、出力は2になります。 y。 これを解決するには、次の手順に従います- k：=tのサイズ、n：=sのサイズ ans：=10 ^ 10 0からn-kの範囲のiの場合、do ss：=s[インデックスiからi+k-1へ]の部分文字列 ans：=最小のans