สามารถปลูกดอกไม้ได้หรือไม่ใน C++

ปัญหา

สมมติว่าเรามีแปลงดอกไม้ยาว ซึ่งบางแปลงปลูกแล้วและบางแปลงว่าง ตอนนี้มีข้อจำกัด คือ ไม่สามารถปลูกดอกไม้ในแปลงที่ติดกันได้ เพราะจะแข่งกันน้ำและทั้งคู่จะตาย ดังนั้น หากเรามีแปลงดอกไม้ แทนด้วยอาร์เรย์ที่มี 0 และ 1 โดย 0 แทนว่าง และ 1 แทนปลูกแล้ว และตัวเลข n ก็ถูกกำหนด เราต้องตรวจสอบว่าสามารถปลูกดอกไม้ใหม่ n ดอกได้หรือไม่โดยไม่ละเมิดกฎห้ามปลูกติดกัน

เช่น ถ้าผนวกเข้าเป็น flowerbed = [1,0,0,0,1], n = 1 ผลลัพธ์จะเป็น True

วิธีแก้ปัญหา

1. ถ้าขนาดของ flowerbed < n: คืนค่า false
2. ถ้าขนาดของ flowerbed เท่ากับ 1 และ flowerbed[0] เท่ากับ 0 และ n เท่ากับ 1: คืนค่า true
3. for i := 0 ถึง ขนาดของ flowerbed - 1 ทำ:
   • ถ้า n > 0:
     • ถ้า i เท่ากับ 0:
       • ถ้า flowerbed[i] เท่ากับ 0 และ flowerbed[1] เท่ากับ 0: flowerbed[0] := 1; ลด n ลง 1
     • มิฉะนั้นถ้า i เท่ากับ ขนาดของ flowerbed - 1:
       • ถ้า flowerbed[i] เท่ากับ 0 และ flowerbed[i - 1] ไม่เท่ากับ 1: flowerbed[i] := 1; ลด n ลง 1
     • มิฉะนั้นถ้า flowerbed[i] เท่ากับ 0 และ flowerbed[i + 1] เท่ากับ 0 และ flowerbed[i - 1] เท่ากับ 0:
       • flowerbed[i] := 1; ลด n ลง 1
   • ถ้า n เท่ากับ 0: คืนค่า true
4. ถ้า n เท่ากับ 0: คืนค่า true
5. คืนค่า false

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

#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(); i++) { 
            if (n > 0) { 
                if (i == 0) { 
                    if (flowerbed[i] == 0 && flowerbed[1] == 0) { 
                        flowerbed[0] = 1; 
                        n--; 
                    } 
                } else if (i == flowerbed.size() - 1) { 
                    if (flowerbed[i] == 0 && flowerbed[i - 1] != 1) { 
                        flowerbed[i] = 1; 
                        n--; 
                    } 
                } else if (flowerbed[i] == 0 && flowerbed[i + 1] == 0 && flowerbed[i - 1] == 0) { 
                    flowerbed[i] = 1; 
                    n--; 
                } 
            } 
            if (n == 0) { 
                return true; 
            } 
        } 
        if (n == 0) { 
            return true; 
        } 
        return false; 
    } 
}; 

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

อินพุต

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

เอาต์พุต

1