当先锋百科网

首页 1 2 3 4 5 6 7

 

思路:

根据题目,可得出如下关键条件:

1.返回的这个二进制矩阵里面的元素不是0就是1;

2.colsum数组中的元素最大为2,最小为0;

3.返回的二进制矩阵只有两行,列数与colsum数组相同。

      根据所有的条件,我们可以采用贪心算法策略 + 两次扫描即可解决本问题,第一次扫描先填充colsum数组中元素为2的对应的列数,填充的同时需要依次将upper和lower减减。第二次扫描再满足colsum数组中元素为1的情况,upper更大就先填充第一行,否则填充第二行。两次遍历完后,如果这个二维矩阵是符合条件的,那么upper和lower都应为0,否则为无效答案,应该返回一个空数组。

TypeScript源代码:

function reconstructMatrix(upper: number, lower: number, colsum: number[]): number[][] {
   const len: number = colsum.length;
   const ans: number[][] = new Array(2).fill(0).map((item) => {return item = new Array(len).fill(0);});
   for(let i = 0; i < len; ++i) {
       if(colsum[i] === 2) {
          ans[0][i] = 1;
          ans[1][i] = 1;
          upper--;
          lower--;
       }
   }

   for(let i = 0; i < len; ++i) {
       if(ans[0][i] === 0 && ans[1][i] === 0
        && colsum[i] === 1) {
          if(upper > lower) {
             ans[0][i] = 1;
             upper--;
          } else {
             ans[1][i] = 1;
             lower--;
          }
       }
   }

   if(upper !== 0 || lower !== 0) {
      return [];
   }

  return ans;
};