LeetCode605:种花问题

传送门:605. 种花问题
  ## `形貌`

1. 假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花草不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给定一个花坛（体现为一个数组包罗0和1，此中0体现没种植花，1体现种植了花），和一个数 n 。能否在不冲破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

复制代码

示例I/O

1. 输入: flowerbed = [1,0,0,0,1], n = 1输出: True输入: flowerbed = [1,0,0,0,1], n = 2输出: False

复制代码

解题思路(贪心)

拿到这道题实在不难想出怎么去"种花",只要数组中任意位置一连出现3个0即可"种花",所以我们只需在遍历数组的时,观察是否有一连的3个0。但是难又难在这个任意位置的3个0,我们要思量差异的界限情况,最早写的代码特别冗余。品评区大佬的加"0"思路,让我豁然开朗,在flowerbed数组两头各增加1个0,就可以不消思量数组的界限情况,只要在任意位置出现3个0就可以"种花"。那么flowerbed数组左右界限加0的原理是什么呢,是因为左右界限不需要思量双方,只需要思量一边的情况即可,所以可以思量加0。
从左向右遍历花坛，在可以种花的地方就种一朵，能种就种（因为在任一种花时候，不种都不会得到更优解），就是一种贪心的思想。
  Code

1. class Solution {    public boolean canPlaceFlowers(int[] flowerbed, int n) {        //假设在数组左边添加0，以管理界限问题，令count初始为1        int num = 0,count = 1;          for (int i=0;i=n;    }}

复制代码

数学方法:跳格子

由于题目给我们的flowerbed数组已然是按照规则来摆放花的,所以我们只需遍历即可。在遍历时,如果遍历到index是1时,说明这个位置有花了,则说明它的前后1格都不是0,我们可以选择跳两格看index+2位置是否有大概可以种花。
而当我们遍历到index是0时,说明前一格index-1肯定是0,就要看它的下一格index+1是不是0或看index是否已经到了flowered数组的最后一个位置,如果能种花,则令n减1,然后index位置就按照1处理处罚,直接跳两格,若index+1是1,则说明这个位置(index)不能种花,且index+1,index+2都不能种花,直接跳3格。
当n减为0时,说明可以种n朵花,则可以直接退出遍历返回true,否则说明不能最多种n朵花,返回false。
  Code

[code]class Solution {    public boolean canPlaceFlowers(int[] flowerbed, int n) {        //遇到1跳2格        for (int i = 0; i < flowerbed.length; i += 2) {            if (flowerbed == 0) {                //index+1位置为0或已到数组尾                if (i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {                    n--;                } else {                    //否则跳3格                    i++;                }            }        }        return n