สร้างเมทริกซ์ 2 แถวแบบไบนารีใหม่ใน C++

ให้เมทริกซ์ 2 แถว n คอลัมน์ ที่แต่ละเซลล์เป็น 0 หรือ 1 โดยมีเงื่อนไข:

• ผลรวมแถวบน (upper) = upper
• ผลรวมแถวล่าง (lower) = lower
• ผลรวมคอลัมน์ที่ i = colsum[i]

ต้องสร้างเมทริกซ์ที่ตรงเงื่อนไขทั้งหมด หากมีหลายคำตอบ ให้คำตอบไหนก็ได้ หากไม่มีคำตอบ ให้คืนอาร์เรย์ว่าง ตัวอย่าง: upper=2, lower=1, colsum=[1,1,1] → [[1,1,0],[0,0,1]]

ขั้นตอนการแก้ปัญหา (Greedy)

1. ตั้งค่า flag = true, สร้างเมทริกซ์ ans[2][n]
2. วนลูปทุกคอลัมน์ i:
   • ถ้า colsum[i] == 2: ใส่ 1 ทั้งสองแถว, ลด upper และ lower ลง 1 ถ้าติดลบ flag = false
   • ถ้า colsum[i] == 1: ใส่ 1 ในแถวที่เหลือมากกว่า (ถ้าเท่ากัน ใส่แถวบนก่อน) ลดค่าที่เหลือตามนั้น
   • ถ้า colsum[i] == 0: ไม่ทำอะไร
   • ค่าอื่น: flag = false
3. หลังลูป ถ้า flag==false หรือ upper!=0 หรือ lower!=0 ให้คืนอาร์เรย์ว่าง
4. มิฉะนั้นคืน ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int u, int l, vector<int>& c) {
        bool flag = true;
        int n = c.size();
        vector<vector<int>> ans(2, vector<int>(n));
        for (int i = 0; i < n; i++) {
            if (c[i] == 2) {
                u--; l--;
                if (u < 0 || l < 0) flag = false;
                ans[0][i] = 1; ans[1][i] = 1;
            } else if (c[i] == 1) {
                if (u > l) { u--; ans[0][i] = 1; }
                else if (u < l) { l--; ans[1][i] = 1; }
                else { if (u > 0) { u--; ans[0][i] = 1; } else if (l > 0) { l--; ans[1][i] = 1; } else flag = false; }
            } else if (c[i] == 0) {
                // nothing
            } else { flag = false; }
        }
        if (!flag || u != 0 || l != 0) return {};
        return ans;
    }
};

int main() {
    vector<int> v = {1,1,1};
    Solution ob;
    print_vector(ob.reconstructMatrix(2, 1, v));
}

Input

2 1 [1,1,1]

Output

[[1, 1, 0, ],[0, 0, 1, ],]