使用 Python 查找排列二进制网格所需的最小交换次数的程序

假设我们有一个 n x n 的二进制矩阵。我们可以对其执行以下操作：一步操作中，我们选择两行相邻的行并交换它们。我们必须计算所需的最小交换次数，以便矩阵主对角线以上的所有节点都为 0。如果没有这样的解决方案，则返回 -1。

因此，如果输入如下所示：

则输出将为 2，因为 -

为了解决这个问题，我们将遵循以下步骤

• n := 矩阵的行数

• m := 创建一个大小为 n 的数组并填充 n

• 对于 i 的范围从 0 到 n - 1，执行

  • 对于 j 的范围从 n-1 到 0，递减 1，执行

    • 如果 matrix[i, j] 等于 1，则

      • m[i] := n-j-1

      • 退出循环

• t := 0，ans := 0

• 对于 i 的范围从 0 到 n - 1，执行

  • t := t + 1

  • flag := False

  • 对于 j 的范围从 i 到 n - 1，执行

    • 如果 m[j] >= n-t，则

      • ans := ans + j-i

      • flag := True

      • 退出循环

  • 如果 flag 为假，则

    • 返回 -1

  • 将 m[从索引 i+1 到 j] 更新为 m[从索引 i 到 j-1]

• 返回 ans

让我们看看以下实现以获得更好的理解 -

示例

 实时演示

def solve(matrix):
   n = len(matrix)
   m = [n] * n
   for i in range(n):
      for j in range(n-1,-1,-1):
         if matrix[i][j] == 1:
            m[i] = n-j-1
            break
   t,ans = 0,0
   for i in range(n):
      t += 1
      flag = False
      for j in range(i,n):
         if m[j] >= n-t:
            ans += j-i
            flag = True
            break
      if not flag: return -1
      m[i+1:j+1] = m[i:j]
   return ans
matrix = [[0,1,0],[0,1,1],[1,0,0]]
print(solve(matrix))

输入

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

输出

2

Arnab Chakraborty

更新于: 2021年5月29日

245 次查看

开启您的 职业生涯

通过完成课程获得认证

开始