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

Pythonですべての1をグループ化するための最小スワップ

バイナリ配列データがあるとすると、配列に格納されているすべての1を配列内の任意の場所にグループ化するために必要なスワップの最小数を見つける必要があります。したがって、配列が[1,0,1,0,1,0,0,1,1,0,1]のような場合、可能な解決策は[0,0,0,0、 0,1,1,1,1,1,1]

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

  • 1つ設定：=0、n：=データ配列の長さ
  • サイズnの配列の合計を作成し、これを0で埋め、summ [0]：=data [0]
    • を設定します。
  • one：=one + data [0]
  • 1からn–1の範囲のiの場合
    • summ [i]：=summ [i-1] + data [i]
    • one：=one + data [i]
  • ans：=one
  • 左：=0、右：=1 – 1
  • 正しい間
  • 左が0の場合、temp：=summ [right]、それ以外の場合、temp：=summ [right] – summ [left-1]
  • ans：=最小ans、1 – temp
  • 左右を1つ増やします
  • 回答を返す
    • 例（Python）

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

    class Solution(object):
   def minSwaps(self, data):
      one = 0
      n = len(data)
      summ=[0 for i in range(n)]
      summ[0] = data[0]
      one += data[0]
      for i in range(1,n):
         summ[i] += summ[i-1]+data[i]
         one += data[i]
      ans = one
      left = 0
      right = one-1
      while right <n:
         if left == 0:
            temp = summ[right]
         else:
            temp = summ[right] - summ[left-1]
         ans = min(ans,one-temp)
         right+=1
         left+=1
      return ans
ob = Solution()
print(ob.minSwaps([1,0,1,0,1,0,0,1,1,0,1]))

    入力

    [1,0,1,0,1,0,0,1,1,0,1]

    出力

    3

    1. Pythonを使用してすべてのノードに到達するための頂点の最小数を見つけるプログラム

      n個の頂点とノードに0からn-1までの番号が付けられた有向非巡回グラフがあるとします。グラフはエッジリストで表されます。ここで、edges [i] =（u、v）はノードuからノードv。グラフ内のすべてのノードに到達できる頂点の最小セットを見つける必要があります。 （頂点は任意の順序で返すことができます）。 したがって、入力が次のような場合 これらの2つの頂点は他のどの頂点からも到達できないため、出力は[0,2,3]になります。したがって、それらから開始すると、すべてをカバーできます。 これを解決するには、次の手順に従います- n：=エッジのサイズ all_nodes：=

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

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