JZX轻语：简
LeetCode 1253 - 重构2行二进制矩阵
发表于2024年07月14日
可以使用贪心解决：首先直接将参数upper和lower视作为第一行和第二行待填充1的个数。从左到右遍历colsum，如果遇到2，则需要同时填充两行，并更新upper和lower；如果遇到1，即仅需填充一行，此时取upper和lower中剩余值较大的一个进行填充，并更新计数；如果遇到0，则不需要填充，直接跳过。最后，如果upper和lower都为0，则返回填充后的矩阵，否则返回空列表(题意表明可能存在不合法的参数，此时upper或lower存在小于0的情况)。
为什么需要取upper和lower中剩余值较大的一个进行填充呢？如果提前消耗掉其中的某一个，说不定后面会遇到2，导致另一个无法填充。因此，我们需要保证两行的填充尽量平衡，以便后续的填充。
class Solution:
def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
col_cnt = len(colsum)
ans = [[0] * col_cnt for _ in range(2)]
for i in range(col_cnt):
if colsum[i] == 2:
ans[0][i] = ans[1][i] = 1
upper -= 1
lower -= 1
elif colsum[i] == 1:
if upper >= lower:
ans[0][i] = 1
upper -= 1
else:
ans[1][i] = 1
lower -= 1
return ans if upper == lower == 0 else []