2024-01-24:用go语言,已知一个n*n的01矩阵, 只能通过通过行交换、或者列

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 = 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)

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
457
粉丝
21
喜欢
37
收藏
22
排名:465
访问:1.9 万
私信
所有博文
社区赞助商