2024-01-24：用 go 语言，已知一个 n*n 的 01 矩阵，只能通过通过行交换、或者列交换的方式调整矩阵，判断这个矩阵的对角线是否能全为 1，如果能返回 true，不能返回 false。我们升级一下:

作者：福大大架构师每日一题

2024-01-24
北京
本文字数：2879 字
阅读完需：约 9 分钟

2024-01-24：用 go 语言，已知一个 n*n 的 01 矩阵，

只能通过通过行交换、或者列交换的方式调整矩阵，

判断这个矩阵的对角线是否能全为 1，如果能返回 true，不能返回 false。

我们升级一下:

已知一个 n*n 的 01 矩阵，

只能通过通过行交换、或者列交换的方式调整矩阵，

判断这个矩阵的对角线是否能全为 1，如果不能打印-1。

如果能，打印需要交换的次数，并且打印怎么交换。

来自网易。

答案 2024-01-24：

来自左程云。

灵捷3.5

大体步骤如下：

1.遍历矩阵的每一行和每一列，统计每行和每列的 1 的个数。

2.如果某一行或某一列的 1 的个数超过 n/2（n 为矩阵的大小），则无法通过交换操作使得对角线上的元素全为 1，直接输出-1。

3.创建一个长度为 n 的数组 rowOnes 和 colOnes，分别存储每行和每列的 1 的个数。

4.创建一个长度为 n 的二维数组 swap，用于记录交换操作。

5.从第一行开始，逐行遍历矩阵，对于每一行，检查是否需要进行交换：

如果该行的 1 的个数小于 n/2，则说明需要进行行交换，找到一行与其交换，并更新 swap 数组。

6.接着从第一列开始，逐列遍历矩阵，对于每一列，检查是否需要进行交换：

如果该列的 1 的个数小于 n/2 且当前行没有进行过行交换，则说明需要进行列交换，找到一列与其交换，并更新 swap 数组。

7.最后，检查矩阵的对角线是否全为 1：

逐行遍历矩阵，如果某一行的对角线元素不为 1，则说明无法满足条件，输出-1。

8.如果能够满足条件，则输出交换次数 k 和交换操作：

遍历 swap 数组，输出每次交换的行号和列号。

总的时间复杂度为 O(n^2)，其中 n 为矩阵的大小。

总的额外空间复杂度为 O(n)，用于存储 rowOnes、colOnes 和 swap 数组。

go 完整代码如下：

package main
import (  "fmt")
var out [1000][2]int
func main() {
  inputs := []int{2,    0, 1,    1, 0,    2,    1, 0,    1, 0}  ii := 0  n := inputs[ii]  ii++
  graph := make([][]int, n)  for i := 0; i < n; i++ {    graph[i] = make([]int, n)    for j := 0; j < n; j++ {      graph[i][j] = inputs[ii]      ii++    }  }
  t := km(graph)  fmt.Println(t)  for i := 0; i < t; i++ {    fmt.Printf("R %d %d\n", out[i][0]+1, out[i][1]+1)  }
}
func km(graph [][]int) int {  N := len(graph)  lx := make([]int, N)  ly := make([]int, N)  match := make([]int, N)  x := make([]bool, N)  y := make([]bool, N)  slack := make([]int, N)  invalid := int(1e9)
  for i := 0; i < N; i++ {    match[i] = -1    lx[i] = -invalid    for j := 0; j < N; j++ {      lx[i] = max(lx[i], graph[i][j])    }    ly[i] = 0  }
  for from := 0; from < N; from++ {    for i := 0; i < N; i++ {      slack[i] = invalid    }    fillBoolSlice(x, false)    fillBoolSlice(y, false)
    for !dfs(from, x, y, lx, ly, match, slack, graph) {      d := invalid      for i := 0; i < N; i++ {        if !y[i] && slack[i] < d {          d = slack[i]        }      }      for i := 0; i < N; i++ {        if x[i] {          lx[i] -= d        }        if y[i] {          ly[i] += d        }      }      fillBoolSlice(x, false)      fillBoolSlice(y, false)    }  }
  ans := 0  for i := 0; i < N; i++ {    ans += (lx[i] + ly[i])  }  if ans < N {    return -1  }
  t := 0  for i := 0; i < N; i++ {    u, v := match[i], i    if u != v {      out[t][0] = v      out[t][1] = u      for j := i + 1; j < N; j++ {        if match[j] == v {          match[j] = u        }      }      t++    }  }
  return t}
func dfs(from int, x, y []bool, lx, ly, match, slack []int, graph [][]int) bool {  N := len(graph)  x[from] = true  for to := 0; to < N; to++ {    if !y[to] {      d := lx[from] + ly[to] - graph[from][to]      if d != 0 {        slack[to] = min(slack[to], d)      } else {        y[to] = true        if match[to] == -1 || dfs(match[to], x, y, lx, ly, match, slack, graph) {          match[to] = from          return true        }      }    }  }  return false}
func fillBoolSlice(arr []bool, value bool) {  for i := 0; i < len(arr); i++ {    arr[i] = value  }}
func max(a, b int) int {  if a > b {    return a  }  return b}
func min(a, b int) int {  if a < b {    return a  }  return b}

复制代码

python 代码如下：

# -*-coding:utf-8-*-def km(graph):    N = len(graph)    lx = [-float('inf')] * N    ly = [0] * N    match = [-1] * N    x = [False] * N    y = [False] * N    slack = [float('inf')] * N    invalid = int(1e9)
    for i in range(N):        lx[i] = max(graph[i])
    for from_ in range(N):        for i in range(N):            slack[i] = invalid        x = [False] * N        y = [False] * N
        while not dfs(from_, x, y, lx, ly, match, slack, graph):            d = invalid            for i in range(N):                if not y[i] and slack[i] < d:                    d = slack[i]            for i in range(N):                if x[i]:                    lx[i] -= d                if y[i]:                    ly[i] += d            x = [False] * N            y = [False] * N
    ans = 0    for i in range(N):        ans += (lx[i] + ly[i])    if ans < N:        return -1
    t = 0    out = [[0, 0]] * N    for i in range(N):        u, v = match[i], i        if u != v:            out[t][0] = v            out[t][1] = u            for j in range(i + 1, N):                if match[j] == v:                    match[j] = u            t += 1
    return t, out

def dfs(from_, x, y, lx, ly, match, slack, graph):    N = len(graph)    x[from_] = True    for to in range(N):        if not y[to]:            d = lx[from_] + ly[to] - graph[from_][to]            if d != 0:                slack[to] = min(slack[to], d)            else:                y[to] = True                if match[to] == -1 or dfs(match[to], x, y, lx, ly, match, slack, graph):                    match[to] = from_                    return True    return False

inputs = [2, 0, 1, 1, 0, 2, 1, 0, 1, 0]ii = 0n = inputs[ii]ii += 1
graph = [[0] * n for _ in range(n)]for i in range(n):    for j in range(n):        graph[i][j] = inputs[ii]        ii += 1
t, out = km(graph)print(t)for i in range(t):    print("R", out[i][0] + 1, out[i][1] + 1)