1253. 重構(gòu) 2 行二進(jìn)制矩陣
題目描述
給你一個(gè) 2 行 n 列的二進(jìn)制數(shù)組：
矩陣是一個(gè)二進(jìn)制矩陣，這意味著矩陣中的每個(gè)元素不是 0 就是 1。
第 0 行的元素之和為 upper。
第 1 行的元素之和為 lower。
第 i 列（從 0 開(kāi)始編號(hào)）的元素之和為 colsum[i]，colsum 是一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組。
你需要利用 upper，lower 和 colsum 來(lái)重構(gòu)這個(gè)矩陣，并以二維整數(shù)數(shù)組的形式返回它。
如果有多個(gè)不同的答案，那么任意一個(gè)都可以通過(guò)本題。
如果不存在符合要求的答案，就請(qǐng)返回一個(gè)空的二維數(shù)組。
示例 1：
輸入：upper = 2, lower = 1, colsum = [1,1,1]
輸出：[[1,1,0],[0,0,1]]
解釋：[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正確答案。
示例 2：
輸入：upper = 2, lower = 3, colsum = [2,2,1,1]
輸出：[]
示例 3：
輸入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
輸出：[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]
提示：
1 <= colsum.length <= 10^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2
解題思路
思路：貪心算法。構(gòu)造一個(gè)2行n列的二維矩陣，其元素均初始化為0。遍歷colsum數(shù)組：如果當(dāng)前數(shù)組元素為2，則表明上下兩行元素均為1；如果當(dāng)前數(shù)組元素為0，則表明上下兩行元素均為0；如果當(dāng)前數(shù)組元素為1，則表明上下兩行中有一個(gè)為1有一個(gè)為0，此時(shí)我們選擇upper和lower中較大的那個(gè)賦值為1而剩余一個(gè)賦值為0。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-526560.html
vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum)
{
int n=colsum.size();
vector<vector<int>> ans(2,vector<int>(n,0));
for(int i=0;i<n;i++)
{
if(colsum[i]==2)
{
ans[0][i]=1;
ans[1][i]=1;
upper--;
lower--;
}
else if(colsum[i]==1)
{
if(upper>lower)
{
upper--;
ans[0][i]=1;
}
else
{
lower--;
ans[1][i]=1;
}
}
if(upper<0||lower<0)
break;
}
return upper||lower?vector<vector<int>>():ans;
}
總結(jié)：如果當(dāng)前數(shù)組元素為1，則表明上下兩行中有一個(gè)為1有一個(gè)為0，此時(shí)我們選擇upper和lower中較大的那個(gè)賦值為1而剩余一個(gè)賦值為0，這樣能夠最大限度內(nèi)避免upper或者lower不夠用的情況。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-526560.html
到了這里，關(guān)于【每日一題】1253. 重構(gòu) 2 行二進(jìn)制矩陣的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
