C++で花を配置できます

いくつかの区画が植えられ、いくつかが空である長い花壇があるとします。現在、制約があり、隣接する区画に花を植えることはできず、水を求めて競争し、両方が死んでしまいます。したがって、0と1を含む配列で表される花壇があり、0は空、1は塗りつぶしを示し、番号nも指定されている場合、no-に違反せずにn個の新しい花を植えることができるかどうかを確認する必要があります。隣接する花が支配するかどうか。

したがって、入力がflowerbed =[1,0,0,0,1]、n =1の場合、出力はTrueになります

これを解決するには、次の手順に従います-

• 花壇のサイズが

  • falseを返す

• 花壇のサイズが1、flowerbed [0]が0、nが1の場合、-

  • trueを返す

• 初期化i：=0の場合、i <花壇のサイズの場合、更新（iを1増やします）、実行-

  • n> 0の場合、-

    • iが0と同じ場合、-

      • Flowerbed [i]が0と同じで、flowerbed [1]が0と同じ場合、-

        • 花壇[0]：=1

        • （nを1減らします）

    • それ以外の場合、iが花壇のサイズと同じである場合-1、次に-

      • flowerbed [i]が0と同じで、flowerbed [i-1]が1に等しくない場合、-

        • 花壇[i]：=1

        • （nを1減らします）

    • それ以外の場合、flowerbed [i]が0と同じで、flowerbed [i + 1]が0と同じで、flowerbed [i-1]が0と同じである場合、-

      • 花壇[i]：=1

      • （nを1減らします）

  • nが0と同じ場合、-

    • trueを返す

• nが0と同じ場合、-

  • trueを返す

• falseを返す

例

理解を深めるために、次の実装を見てみましょう-

#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;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,0,0,0,1};
   cout << (ob.canPlaceFlowers(v, 1));
}

入力

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

出力

1