发表于 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 []

• LC 题目链接