使用 Python 查詢排列二進位制網格所需的最小交換次數的程式

假設我們有一個 n x n 的二進位制矩陣。我們可以對其執行以下操作：一步操作中，我們選擇兩行相鄰的行並交換它們。我們必須計算所需的最小交換次數，以便矩陣主對角線以上的所有節點都為 0。如果沒有這樣的解決方案，則返回 -1。

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

010
011
100

則輸出將為 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

更新於: 2021年5月29日

245 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始
廣告