605. Can Place Flowers

• 问题描述

       假设你有一个长花圃，其中有些地块是种植的，有些则不是。 然而，花不能种植在相邻的地块 - 它们会争夺水，

       两者都会死 亡。给定 一个花坛（表示为包含0和1的数组，其中0表示空，1表示不为空）和数字n，如果可以在

       其中种植n个新花而不违反无邻花规则则返回。

       例子：

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

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

• 解题思路

      根据题意，元素1的左右两个元素值不能是1，题目给我们一个数组，只有1和0。在解题之前要考虑满足条件的

      可能性有哪 些：分为两个方面考虑：一个方面根据n的值，如果n=0时，无论数组什么情况条件都会满足；另一

      方面根据数组元素的情况，即怎么放才满足条件。这里分为两种情况：

    （1）【0,0,1 ......】或者【.....1,0,0】当要插入的1是数组的边界时满足条件；

    （2）第二种情况是【.......0,0,0.......】即要插入的元素的左右两边都是0的情况也满足条件；

     综合考虑要遍历整个数组，把每一个元素都当作可以插入的元素，判断是否满足上面的条件：

   （1）转化为代码    i-1<0,a[i]=0,a[i+1]=0  和  a[i-1]=0,a[i]=0,i+1=a.length

   （2）转化为代码 a[i-1]=0,a[i]=0,a[i+1]

 

• 代码

Java

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
		int i;
		boolean bool = false;
		int length = flowerbed.length;
		if (n == 0) {
		    bool = true;
		} else {
			for (i = 0; i < length; i++) {
				if (flowerbed[i] == 1) continue;
				if ((i - 1 < 0 || flowerbed[i - 1] == 0) && flowerbed[i] == 0
						&& (i + 1 >= length || flowerbed[i + 1] == 0)) {
					flowerbed[i] = 1;
					i=i+1;
					if (--n == 0)  bool = true;
				}
			}
		}
		return bool;
	}
}

• 代码优化

     （1）当数组开始时要先找到值为0的数，值为1的直接跳过，代码： if (flowerbed[i] == 1) continue;

     （2）当找到满足条件的元素组合比如0，0，0时，此时i指在第二个0，进行下一次的循环时，我们可以看到

        在第三个0一定不满足条件，一定不能作为插入的元素。所以我们跳过对这个元素的判断，代码：i=i+1;

• 总结

      1.在代码实现之前，必须对题意深入理解，要知道各种满足条件不满足条件，这样能省略实现代码的时间。

      2.对于数组遍历的题目，其总体思路是对数组遍历时判断满足题目的数组，在对其进行出路。

 

• 比较

     优化后代码的运行速度比较理想