searchusermenu
  • 发布文章
  • 消息中心
点赞
收藏
评论
分享
原创

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

2024-01-24 02:24:06
3
0
2024-01-24:用go语言,已知一个n*n的01矩阵,
 
只能通过通过行交换、或者列交换的方式调整矩阵,
 
判断这个矩阵的对角线是否能全为1,如果能返回true,不能返回false。
 
我们升级一下:
 
已知一个n*n的01矩阵,
 
只能通过通过行交换、或者列交换的方式调整矩阵,
 
判断这个矩阵的对角线是否能全为1,如果不能打印-1。
 
如果能,打印需要交换的次数,并且打印怎么交换。
 
 
答案2024-01-24:
 
 
# 大体步骤如下:
 
 
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完整代码如下:
 
```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代码如下:
 
```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)
 
```
 

 

0条评论
0 / 1000
3****m
116文章数
2粉丝数
3****m
116 文章 | 2 粉丝
原创

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

2024-01-24 02:24:06
3
0
2024-01-24:用go语言,已知一个n*n的01矩阵,
 
只能通过通过行交换、或者列交换的方式调整矩阵,
 
判断这个矩阵的对角线是否能全为1,如果能返回true,不能返回false。
 
我们升级一下:
 
已知一个n*n的01矩阵,
 
只能通过通过行交换、或者列交换的方式调整矩阵,
 
判断这个矩阵的对角线是否能全为1,如果不能打印-1。
 
如果能,打印需要交换的次数,并且打印怎么交换。
 
 
答案2024-01-24:
 
 
# 大体步骤如下:
 
 
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完整代码如下:
 
```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代码如下:
 
```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)
 
```
 

 

文章来自个人专栏
福大大架构师每日一题
116 文章 | 1 订阅
0条评论
0 / 1000
请输入你的评论
0
0