首页 > 代码库 > 605. Can Place Flowers

605. Can Place Flowers

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if nnew flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

 

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

 

Note:

  1. The input array won‘t violate no-adjacent-flowers rule.
  2. The input array size is in the range of [1, 20000].
  3. n is a non-negative integer which won‘t exceed the input array size.
     1 class Solution {
     2 public:
     3     bool canPlaceFlowers(vector<int>& flowerbed, int n) {
     4         int tmp_n = 0;
     5         int num_zero = 0;
     6         bool left_no_one = true;
     7         bool right_no_one = false;
     8         int count = flowerbed.size();
     9         for(int i=0;i<count;++i)
    10         {
    11             if(flowerbed[i] == 0)//记录0的个数
    12             {
    13                 num_zero++;
    14                 if(i == (count-1))//判断是不是最右侧没有1
    15                 {
    16                    right_no_one = true; 
    17                 }
    18             }
    19             else//遇到1之后开始算之前的零够能种多少花
    20             {
    21                 if(left_no_one == true)//先判断是最左侧没有1
    22                 {
    23                     if(num_zero >= 2)
    24                     {
    25                         if(num_zero%2 == 0)
    26                         {
    27                  
    28            num_zero += 1;
    29                         }
    30                         tmp_n += (((num_zero-3)/2)+1);
    31                     }
    32                     
    33                 }
    34                 else //左侧有1
    35                 {
    36                     if(num_zero >= 3)
    37                     {
    38                         if(num_zero%2 == 1)
    39                         {
    40                             num_zero +=1;
    41                         }
    42                         tmp_n += (((num_zero-4)/2)+1);
    43                     }
    44                 
    45                     
    46                 }
    47                 num_zero = 0; 
    48                 left_no_one = false;//清除左侧没有1的标志
    49             }
    50         }
    51         if(left_no_one == true && right_no_one == true)
    52         {
    53             if(num_zero >= 1)
    54             {
    55                 if(num_zero%2 == 1)
    57                 {
    58                     num_zero += 1;
    59                 }
    60                 tmp_n += (((num_zero-2)/2)+1);
    61             }
    62             
    63         }
    64         else
    65         {
    66             if(num_zero >= 2)
    67             {
    68                 if(num_zero%2 == 0)
    69                 {
    70                     num_zero += 1;
    71                 }
    72                 tmp_n += (((num_zero-3)/2)+1);
    73             }
    74         }
    75 
    76         if(tmp_n >= n)
    77         {
    78             return true;
    79 
    80         }
    81         else
    82         {
    83             return false;
    84         }
    85 
    86     }
    87 };

     

605. Can Place Flowers