1253. 重构 2 行二进制矩阵.md

1253. 重构 2 行二进制矩阵

• 贪心算法

function reconstructMatrix(upper: number, lower: number, colsum: number[]): number[][] {

    let colsumForSum: number = 0,
        twoSum: number = 0;

    for (const num of colsum) {
        if (num > 2) { // colsum上的数字大于2,这是无解的!
            return [];
        }
        if (num === 2) { // 统计2的数量
            ++twoSum;
        }
        colsumForSum += num;
    }

    if (
        upper + lower !== colsumForSum // 一定要相等
        || upper < twoSum // upper必须要贡献towSum个1
        || lower < twoSum // lower必须要贡献twoSum个1
    ) {
        return [];
    }

    const results: number[][] = new Array(2).fill(null).map(() => new Array(colsum.length).fill(0));

    let index: number = 0;

    while (upper > 0 || lower > 0) {

        if (results[0][index] + results[1][index] < colsum[index]) {
            if (colsum[index] === 2) {
                --upper;
                --lower;
                results[0][index] = results[1][index] = 1;
            } else if (upper > lower) { // 别把upper全花光了,留着对付2的情况
                --upper;
                results[0][index] = 1;
            } else {
                --lower;
                results[1][index] = 1;
            }
        }

        ++index;
    }

    return results;
};