解答

Leetcode上第605道题，我的解答：线下编译没错误，但是线上编译出错

  1. #include <iostream>
  2. #include<vector>
  3. using std::vector;
  4. using std::cout;
  5. using std::endl;
  6. class Solution 
  7. {
  8.     public:
  9.         int num_flag = 0;
  10.         bool canPlaceFlowers(vector<int>& flowerbed, int n) 
  11.         {
  13.             for (auto it = flowerbed.begin(); it != flowerbed.end(); ++it) 
  14.             {
  16.                 if (it == flowerbed.begin() || it == flowerbed.end())
  17.                 {
  18.                     if (it == flowerbed.begin())
  19.                     {
  20.                         if (*it==0 && *(it + 1) == 0)
  21.                         {
  22.                             *it = 1;
  23.                             num_flag = num_flag + 1;
  24.                         }
  26.                     }
  27.                     else
  28.                     {
  29.                         if (*it==0 && *(it - 1) == 0)
  30.                         {
  31.                             *it = 1;
  32.                             num_flag = num_flag + 1;
  33.                         }
  35.                     }
  36.                 }
  37.                 else 
  38.                 {
  39.                     if (*(it - 1) == 0 && *it == 0 && *(it + 1) == 0) 
  40.                     {
  41.                         *it = 1;
  42.                         num_flag = num_flag + 1;
  43.                     }
  45.                 }
  47.             }
  48.             if (num_flag >= n) {
  49.                 return true;
  50.             }
  51.             else {
  52.                 return false;
  53.             }
  54.         };
  55. };
  59. void main()
  60. {
  61.     vector<int> flbed = { 1,0,0,0,1,0,0};
  62.     int n = 2;
  63.     Solution solu;
  64.     bool result = solu.canPlaceFlowers(flbed, n);
  65.     if (result)
  66.     {
  67.         cout << "可以" << endl;
  68.     }
  69.     else
  70.     {
  71.         cout << "不可以" << endl;
  72.     }
  74. }

跳格子法

解题者提供的跳格子法，非常容易理解

题目要求是否能在不打破规则的情况下插入n朵花，与直接计算不同，采用“跳格子”的解法只需遍历不到一遍数组，处理以下两种不同的情况即可：

【1】当遍历到index遇到1时，说明这个位置有花，那必然从index+2的位置才有可能种花，因此当碰到1时直接跳过下一格。
【2】当遍历到index遇到0时，由于每次碰到1都是跳两格，因此前一格必定是0，此时只需要判断下一格是不是1即可得出index这一格能不能种花，如果能种则令n减一，然后这个位置就按照遇到1时处理，即跳两格；如果index的后一格是1，说明这个位置不能种花且之后两格也不可能种花（参照【1】），直接跳过3格。

当n减为0时，说明可以种入n朵花，则可以直接退出遍历返回true；如果遍历结束n没有减到0，说明最多种入的花的数量小于n，则返回false。