1253. Reconstruct a 2-Row Binary Matrix¶
题目信息¶
- 题号:
1253
- 难度:
Medium
- 主题:
二进制矩阵、贪心、行列和
- 原题:
- 重点:
构造两行二进制矩阵,使两行元素和分别为
upper、lower,每列元素和等于colsum[i];无解返回空数组
题目重述¶
给定非负整数 upper、lower 和数组 colsum。需要构造一个 2 x n 的二进制矩阵,其中第一行元素和为 upper,第二行元素和为 lower,并且第 i 列两项之和恰好等于 colsum[i]。
若存在多种构造,可返回任意一种;若无法满足全部行列和约束,返回空数组。
1 <= colsum.length <= 10^5,0 <= upper, lower <= colsum.length,colsum[i] 为 0、1 或 2。
自建示例¶
列和为一的位置可以分配给任意一行:
输入:upper = 2, lower = 1, colsum = [1,1,1]
输出:[[1,1,0],[0,0,1]]
解释:两行元素和分别为 2 和 1,每一列的元素和都为 1。
行和总量与列和总量不一致时无解:
输入:upper = 1, lower = 1, colsum = [2,1]
输出:[]
解释:两行要求的总和为 2,但所有列和之和为 3。