Leetcode 1253. 重构 2 行二进制矩阵（DAY 131) ---- 贪心算法学习期

淩亂°似流年 2022-10-14 00:45 103阅读 0赞

## 原题题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]

--------------------

## 代码实现（首刷自解） ##

class Solution { 
    public:
        vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) { 
            int sum = 0,flag = 0;
            for(const auto& num:colsum) sum += num;
            vector<vector<int>> ret(2,vector<int>(colsum.size(),0)),temp;
            if(upper+lower != sum)  return temp;
    
            for(int i=0;i<colsum.size();++i)
            { 
                if(!colsum[i])  continue;
                flag = upper<lower;
                if(colsum[i] == 1)
                { 
                    ret[flag][i] = 1;
                    if(flag)    --lower;
                    else    --upper;
                }
                else
                { 
                    ret[0][i] = ret[1][i] = 1;
                    --lower;
                    --upper;
                }
                if(lower<0 || upper<0)  return temp;
                if(!lower && !upper)    break;
            }
            if(lower>0 || upper>0)  return temp;
            return ret;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]: /images/20221014/dd9b06b84e124f038ff4c7eebecee927.png