请选择 进入手机版 | 继续访问电脑版

LeetCode605:种花问题

[复制链接]
期待幸福 发表于 2021-1-2 12:16:32 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
传送门: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
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )