1605. 给定行和列的和求可行矩阵

https://leetcode-cn.com/contest/biweekly-contest-36/problems/find-valid-matrix-given-row-and-column-sums/

从数据量规模上看,这题肯定不是使用回溯方法,此外似乎也没有办法猜测每个元素,比如就没有方法猜测a[0][0]是什么。

这题解法还是通过保持不变量来不断修正剩余行/列上的元素的。假设 rowsum=[R0,R1,R2..Rn], colsum=[C0,C1,…Cm], 我们可以先初始化矩阵为下面这样。

R0 0 0 0
R1 0 0 0
R2 0 0 0
0 0 0
Rn 0 0 0

这个矩阵在每行上的和始终是满足rowsum要求的,假设我们就是要不断地修正列,但同时保证行和始终是rowsum.

如果我们分析第一列,假设R0+R1 < C0, 但是R0+R1+R2 > C0,因为要求每个元素都是非负整数,所以情况就会变成这样。

R0 0 0 0
R1 0 0 0
C0-R0-R1 R2-(C0-R0-R1) 0 0
0 R3 0 0
0 R4 0 0
0 0 0
0 Rn 0 0

这个时候第一列满足条件,并且行和也始终等于rowsum. 依次类推,接着我们调整剩余的列。

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        n = len(rowSum)
        m = len(colSum)
        ans = [[0] * m for _ in range(n)]

        # 保证行之和始终满足,开始调整列
        for i in range(n):
            ans[i][0] = rowSum[i]

        for j in range(m):
            acc = 0
            for i in range(n):
                acc += ans[i][j]
                if acc > colSum[j]:
                    delta = acc - colSum[j]
                    ans[i][j + 1] += delta
                    ans[i][j] -= delta
                    acc -= delta
        return ans