Có thể trồng hoa không (Can Place Flowers) trong C++

Mô tả bài toán

Cho mảng flowerbed (0: trống, 1: đã trồng) và số n. Không được trồng 2 hoa liền kề. Kiểm tra có thể trồng thêm n hoa không.

Ví dụ: flowerbed = [1,0,0,0,1], n = 1 → True (trồng ở giữa).

Giải pháp (Tham lam duyệt một lần)

• Duyệt mảng, nếu flowerbed[i] == 0 và 2 bên (nếu có) đều là 0 → trồng hoa tại i (flowerbed[i] = 1), giảm n.
• Xử lý riêng 2 đầu mảng (chỉ kiểm tra 1 bên).
• Nếu n == 0 → true.

Ví dụ minh họa

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

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        if (flowerbed.size() < n) return false;
        if (flowerbed.size() == 1 && flowerbed[0] == 0 && n == 1) return true;
        for (int i = 0; i < flowerbed.size() && n > 0; i++) {
            if (flowerbed[i] == 0) {
                bool leftEmpty = (i == 0) || flowerbed[i-1] == 0;
                bool rightEmpty = (i == flowerbed.size()-1) || flowerbed[i+1] == 0;
                if (leftEmpty && rightEmpty) {
                    flowerbed[i] = 1;
                    n--;
                }
            }
        }
        return n == 0;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,0,0,0,1};
    cout << ob.canPlaceFlowers(v, 1);
    return 0;
}

Đầu vào

{1,0,0,0,1}, 1

Đầu ra

1