Pythonでターゲットを作成するために列を反転する操作の最小数をカウントするプログラム

行と列の数が同じである行列Mとターゲット行列Tがあるとします。ここで、行列の特定の列を反転して、すべての1が0に変換され、すべての0が1に変換される操作を想定します。したがって、行列の行を無料で並べ替えることができる場合は、MをTに変換するために必要な操作の最小数を見つけます。解決策がない場合は、-1を返します。

したがって、入力がM =

T =

最初に行を-

次に、列1を次のように反転します-

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

• nums1：=新しいリスト、nums2：=新しいリスト

• 行列の各行について、次のようにします

  • ths：=0

  • 行が空でないときに、実行します

    • ths：=（ths * 2）+行の最後の要素、および行の最後の要素を削除

  • nums1の最後にthsを挿入します

• ターゲットの各行について、実行します

  • ths：=0

  • 行がゼロ以外の場合は、実行してください

  • ths：=（ths * 2）+行の最後の要素、および行の最後の要素を削除

  • nums2の最後にthsを挿入します

• ret：=無限大

• nums1の各numに対して、実行

  • cts：=nums1とその頻度に異なる要素を持つマップ

  • cts [num]：=cts [num]-1

  • my_xor：=num XOR nums2 [0]

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

    • 必要：=my_xor XOR nums2 [i]

    • cts [needed]がゼロの場合、

      • ループから出てきます

      • cts [needed]：=cts [needed]-1

    • それ以外の場合

    • ret：=retの最小値、およびmy_xorのセットビット数

    • retが無限大と同じでない場合はretを返し、そうでない場合は-1

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

例

class Solution:
   def solve(self, matrix, target):
      nums1 = []
      nums2 = []
      for row in matrix:
         ths = 0
         while row:
            ths = (ths<<1) + row.pop()
         nums1.append(ths)
      for row in target:
         ths = 0
         while row:
            ths = (ths<<1) + row.pop()
         nums2.append(ths)
      ret=float('inf')
      from collections import Counter
      for num in nums1:
         cts = Counter(nums1)
         cts[num] -= 1
         my_xor = num^nums2[0]
         for i in range(1,len(nums2)):
            needed = my_xor^nums2[i]
            if not cts[needed]:
               break
            cts[needed]-=1
         else:
            ret=min(ret,bin(my_xor).count('1'))
      return ret if ret!=float('inf') else -1
ob = Solution()
M = [
   [0, 0],
   [1, 0],
   [1, 1]
]
T = [
   [0, 1],
   [1, 0],
   [1, 1]
]
print(ob.solve(M,T))

入力

M = [[0, 0],[1, 0],[1, 1]] T = [[0, 1],[1, 0],[1, 1]]

出力

1