数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python程序：根据行和列的总和查找有效的矩阵
假设我们有两个数组 `rowSum` 和 `colSum`，它们包含非负值，其中 `rowSum[i]` 包含第 i 行元素的总和，`colSum[j]` 包含第 j 列元素的总和。我们需要找到一个大小为 ( `rowSum` 大小 x `colSum` 大小) 的具有非负值的矩阵，以满足给定的 `rowSum` 和 `colSum` 值。
因此，如果输入类似于 `rowSum = [13,14,12]`，`colSum = [9,13,17]`，则输出将是……
| 9 | 4 | 0 |
| 0 | 9 | 5 |
| 0 | 0 | 12 |
为了解决这个问题，我们将遵循以下步骤：
- matrix := 创建一个空矩阵
- visited := 一个新的集合
- 定义一个函数 `minimum()`。它将接收 r, c 作为参数。
- min_total := 无穷大
- type := 空字符串
- 对于范围从 0 到 r 的大小 - 1 的 i，执行：
- 如果 r[i] < min_total，则：
- index := i
- type := 'row'
- min_total := r[i]
- 如果 r[i] < min_total，则：
- 对于范围从 0 到 c 的大小 - 1 的 i，执行：
- 如果 c[i] < min_total，则：
- min_total := c[i]
- type := 'col'
- index := i
- 如果 c[i] < min_total，则：
- 如果 type 等于 'row'，则：
- r[index] := 无穷大
- 对于范围从 0 到 c 的大小 - 1 的 i，执行：
- 如果 c[i] 不等于无穷大且 c[i] >= min_total，则：
- c[i] := c[i] - min_total
- matrix[index, i] := min_total
- 跳出循环
- 如果 c[i] 不等于无穷大且 c[i] >= min_total，则：
- 如果 type 等于 'col'，则：
- c[index] := 无穷大
- 对于范围从 0 到 r 的大小 - 1 的 i，执行：
- 如果 r[i] 不等于无穷大且 r[i] >= min_total，则：
- r[i] := r[i] - min_total
- matrix[i, index] := min_total
- 跳出循环
- 如果 r[i] 不等于无穷大且 r[i] >= min_total，则：
- 将 (index, type) 对插入 visited
- 在主方法中执行以下操作：
- 当 visited 的大小不等于 r 的大小 + c 的长度时，执行：
- minimum(r, c)
- 返回 matrix
示例
让我们看看下面的实现来更好地理解：
def solve(r, c):
matrix = [[0]*len(c) for _ in range(len(r))]
visited = set()
def minimum(r,c):
min_total = float('inf')
type = ''
for i in range(len(r)):
if(r[i] < min_total):
index = i
type = 'row'
min_total = r[i]
for i in range(len(c)):
if(c[i] < min_total):
min_total = c[i]
type = 'col'
index = i
if(type == 'row'):
r[index] = float('inf')
for i in range(len(c)):
if(c[i] != float('inf') and c[i] >= min_total):
c[i] -= min_total
matrix[index][i] = min_total
break
if(type == 'col'):
c[index] = float('inf')
for i in range(len(r)):
if(r[i] != float('inf') and r[i] >= min_total):
r[i] -= min_total
matrix[i][index] = min_total
break
visited.add((index,type))
while len(visited) != len(r)+len(c):
minimum(r,c)
return matrix
rowSum = [13,14,12]
colSum = [9,13,17]
print(solve(rowSum, colSum))输入
[13,14,12], [9,13,17]
输出
[[9, 4, 0], [0, 9, 5], [0, 0, 12]]
更新于：2021年10月4日
249 次查看
广告