2024-01-24：用go语言，已知一个n*n的01矩阵，只能通过通过行交换、或者列交换的方式调整矩阵，判断这个矩阵的对角

福大大架构师每日一题

发布于 2024-01-30 16:15:31

1200

发布于 2024-01-30 16:15:31

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

用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 = 0
n = 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)