https://leetcode.com/problems/reconstruct-a-2-row-binary-matrix/
Given the following details of a matrix with
n columns and 2 rows :- The matrix is a binary matrix, which means each element in the matrix can be
0or1. - The sum of elements of the 0-th(upper) row is given as
upper. - The sum of elements of the 1-st(lower) row is given as
lower. - The sum of elements in the i-th column(0-indexed) is
colsum[i], wherecolsumis given as an integer array with lengthn.
Your task is to reconstruct the matrix with
upper, lower and colsum.
Return it as a 2-D integer array.
If there are more than one valid solution, any of them will be accepted.
If no valid solution exists, return an empty 2-D array.
Example 1:
Input: upper = 2, lower = 1, colsum = [1,1,1] Output: [[1,1,0],[0,0,1]] Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.
Example 2:
Input: upper = 2, lower = 3, colsum = [2,2,1,1] Output: []
Example 3:
Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1] Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]
If the column sum is
2 or 0, the choice is obvius.
If it's
1, we set the upper bit if upper is larger than lower, and lower bit otherwise.public List<List<Integer>> reconstructMatrix(int u, int l, int[] cs) {
boolean[][] res = new boolean[2][cs.length];
for (int i = 0; i < cs.length; ++i) {
res[0][i] = cs[i] == 2 || (cs[i] == 1 && l < u);
res[1][i] = cs[i] == 2 || (cs[i] == 1 && !res[0][i]);
u -= res[0][i] ? 1 : 0;
l -= res[1][i] ? 1 : 0;
}
return l == 0 && u == 0 ? new ArrayList(Arrays.asList(res[0], res[1])) : new ArrayList();
}https://www.cnblogs.com/onePunchCoder/p/11831345.html
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colums) { int sum = 0; int numof2 = 0; for (int colum : colums) { sum += colum; if (colum == 2) { numof2++; } } List<List<Integer>> result = new ArrayList<>(); if (sum != upper + lower || numof2 > Math.min(upper, lower)) { return result; } List<Integer> upperList = new ArrayList<>(); List<Integer> lowerList = new ArrayList<>(); result.add(upperList); result.add(lowerList); for (int colum : colums) { if (colum == 0) { upperList.add(0); lowerList.add(0); } else if (colum == 2) { upperList.add(1); upper--; lowerList.add(1); lower--; } else { if (upper > lower) { upperList.add(1); lowerList.add(0); upper--; } else { upperList.add(0); lowerList.add(1); lower--; } } } return result; }https://www.codetd.com/en/article/7811117
2, a brief translation:
Construction of a plurality of data rows two columns, and the first row of upper, and the second row of Lower, and to colsum [i] of the i-th column. If such an array does not exist returns NULL
3, code analysis:
- If the upper + lower does not mean colsum and then return empty.
- If the number 2 is greater than colsum in upper or lower, return null
- From left to right, a premise is inserted vertically keep balance. (When colums [i] == 1, if lower> = upper plug, the plug remaining cases)
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colums) {
int sum = 0;
int numof2 = 0;
for (int colum : colums) {
sum += colum;
if (colum == 2) {
numof2++;
}
}
List<List<Integer>> result = new ArrayList<>();
if (sum != upper + lower || numof2 > Math.min(upper, lower)) {
return result;
}
List<Integer> upperList = new ArrayList<>();
List<Integer> lowerList = new ArrayList<>();
result.add(upperList);
result.add(lowerList);
for (int colum : colums) {
if (colum == 0) {
upperList.add(0);
lowerList.add(0);
} else if (colum == 2) {
upperList.add(1);
upper--;
lowerList.add(1);
lower--;
} else {
if (upper > lower) {
upperList.add(1);
lowerList.add(0);
upper--;
} else {
upperList.add(0);
lowerList.add(1);
lower--;
}
}
}
return result;
}
- First, intialize both the rows as
0. Now, fill the indices where the vertical column sum is2(as they don't have a choice). So, now we only need to make choices for the columns with sum1. Find out the current sum of the first row. Compare it with the required amount. If the difference becomes negative, it means that there is no solution. Else, greedily fill the required1sin the top row and the remaining1sin the bottom row. Finally, check if the sum of the bottom row equalslower
We count the number of columns for which we need 1 in both rows(colsum[i] == 2), similarly we count the number of columns for which we need column-sum as 1 and column-sum as 0.
For the columns where we need the column-sum as 2, we definitely know that we need 1 in both the rows, similarly if the column-sum is 0 we know we need to place 0s in both the rows.
For the case where we need column-sum as 1, we need to see if we can have a 1 in row1 or do we have to have a 1 in row2.
For those cases I have done a precomputation and followed a somewhat greedy approach.
The number of columns where we need a 1 in row1 and 0 in row2 is say count1 (as mentioned in code).
We start assigning values to the two rows now by iterating over each value in the colsum array. If we encounter a colsum[i] == 2 or colsum[i] == 0, we assign 1s to both the rows and 0s to both the rows respectively.
For the cases where colsum[i] == 1, we check value of count1 variable which will tell us if we can assign a 1 to row1 or not. If value of count1 > 0, we can assign 1 to row1 and 0 to row2 and we simultaneously decrement count1. Else if count1 == 0, we assign a 0 to row1 and 1 to row2.
For those cases I have done a precomputation and followed a somewhat greedy approach.
The number of columns where we need a 1 in row1 and 0 in row2 is say count1 (as mentioned in code).
We start assigning values to the two rows now by iterating over each value in the colsum array. If we encounter a colsum[i] == 2 or colsum[i] == 0, we assign 1s to both the rows and 0s to both the rows respectively.
For the cases where colsum[i] == 1, we check value of count1 variable which will tell us if we can assign a 1 to row1 or not. If value of count1 > 0, we can assign 1 to row1 and 0 to row2 and we simultaneously decrement count1. Else if count1 == 0, we assign a 0 to row1 and 1 to row2.
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
int n = colsum.length;
int sum0 = 0; // no. of columns with colsum 0
int sum1 = 0; // no. of columns with colsum 1
int sum2 = 0; // no. of columns with colsum 2
for(int i = 0; i < n; i++){
if(colsum[i] == 0) sum0 ++;
else if(colsum[i] == 1) sum1 ++;
else sum2 ++;
}
int count1 = upper - sum2; // no. of columns with 1 in 1st row and 0 in 2nd row
int count2 = lower - sum2; // no. of columns with 0 in 1st row and 1 in 2nd row
// check if arrangement is possible or not
if(count1 < 0 || count2 < 0 || count1 + count2 != sum1) return new ArrayList<>();
List<List<Integer>> ans = new ArrayList<>();
for(int i = 0; i < 2; i++) ans.add(new ArrayList<>());
for(int i = 0; i < n; i++){
if(colsum[i] == 2){
ans.get(0).add(1);
ans.get(1).add(1);
}
else if(colsum[i] == 0){
ans.get(0).add(0);
ans.get(1).add(0);
}
else{
if(count1 > 0){
count1 --;
ans.get(0).add(1);
ans.get(1).add(0);
}
else{
ans.get(0).add(0);
ans.get(1).add(1);
}
}
}
return ans;
}
(贪心)
colsum为 0 或者 2 的列的值可以直接确定，根据情况，更新upper和lower，此时upper和lower记录当前行还需要多少个 1。如果这时候upper或lower小于 0，则直接返回空数组。- 接下来处理
colsum为 1 的列，如果upper大于 0，则这一列第一行填 0，第二行填 1，然后upper减 1。反之亦然。最后处理结束后，如果upper或lower仍大于 0，则返回空数组。
时间复杂度
- 每个位置仅遍历两次，故时间复杂度为 。
空间复杂度
- 答案需要额外 的空间。
vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
int n = colsum.size();
vector<vector<int>> res(2, vector<int>(n));
for (int i = 0; i < n; i++)
if (colsum[i] == 0) {
res[0][i] = res[1][i] = 0;
} else if (colsum[i] == 2) {
res[0][i] = res[1][i] = 1;
upper--; lower--;
if (upper < 0 || lower < 0)
return {};
}
for (int i = 0; i < n; i++)
if (colsum[i] == 1) {
if (upper > 0) {
res[0][i] = 1; res[1][i] = 0;
upper--;
} else if (lower > 0) {
res[0][i] = 0; res[1][i] = 1;
lower--;
} else {
return {};
}
}
if (upper > 0 || lower > 0)
return {};
return res;
}
