605. Planting flowers

Address ：

Power button https://leetcode-cn.com/problems/can-place-flowers/

subject ：

Suppose there's a very long flower bed , Part of the plot is planted with flowers , The other part didn't . But , Flowers cannot be planted on adjacent plots , They compete for water , Both will die .

Give you an array of integers flowerbed Indicates a flower bed , By a number of 0 and 1 form , among 0 No flowers ,1 It means flowers are planted . There's another number n , Can it be planted without breaking the planting rules n A flower ？ Energy returns true , If not, return false.

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

Tips ：

1 <= flowerbed.length <= 2 * 104 flowerbed[i] by 0 or 1 flowerbed There are no two adjacent flowers 0 <= n <= flowerbed.length

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/can-place-flowers
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

Consider calculating the current maximum number of new plants , Last sum n Compare , If the maximum number < n , It can't be planted

For one 3 Combination of elements , Possible 1 or 0 New species of , such as ：[1,0,0] or [0,1,0] or [0,0,1]

The easiest thing to think of is to look at the current element value ：

1. [i] == 1, Possible locations [1,0,0], therefore Subscript +2

2. [i] == 0, Possible locations [0,0,0],[0,0,1], So subscript +2

         If [i+1] == 1,[0,1,0] impossible , So subscript +1, +2 

3. The last processing of the end element may not be 3 Tuples

        [0],[0,0] You need to consider [i-1] Is it 0, If it is 0, that [1],[1,0]

        [0,1] Don't have to consider , Because the first two cases 1 The location of has been handled

Method 1 、 Traverse

bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n){
	int maxSize = 0;
	
	if(flowerbedSize == 1)
	{
		if(flowerbed[0] == 0)
			maxSize++;
			
		if(maxSize < n)
			return false;
		else
			return true;	
	}
	
	for(int i=0; i<flowerbedSize; )
	{
		// [i] == 1
		if(flowerbed[i] == 1)
		{
			i+=2;
			continue;
		}
		
		// [i] == 0
		if(flowerbed[i] == 0)
		{
			if(i+1 < flowerbedSize)
			{
				if(flowerbed[i+1] == 0)
				{
					maxSize++;
					i+=2;
					continue;
				}
				i++; 
				i+=2; // new start
				
				continue;
			}
			else if(flowerbed[i-1] != 1)
			{
				maxSize++;
				i++;
			}
		}
	}
	
	if(maxSize < n)
		return false;
	else
		return true;
}

See more brush notes