资讯专栏INFORMATION COLUMN

数据结构与算法-LeetCode 种花问题(No.605)

xuexiangjys / 2623人阅读

摘要:能否在不打破种植规则的情况下种入朵花能则返回,不能则返回。示例输入输出示例输入输出注意数组内已种好的花不会违反种植规则。输入的数组长度范围为。是非负整数,且不会超过输入数组的大小。

LeetCode 605. 种花问题

假设你有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花卉不能种植在相邻的地块上,它们会争夺水源,两者都会死去。

给定一个花坛(表示为一个数组包含0和1,其中0表示没种植花,1表示种植了花),和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花?能则返回True,不能则返回False。

示例 1:

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

示例 2:

输入: flowerbed = [1,0,0,0,1], n = 2
输出: False
注意:
数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数,且不会超过输入数组的大小。
我的思路
总的来讲,这道题在leetCode 中不算难的,关键就是要有思路。下面是我自己做题时的分析。
1. 在两边都是花 中间都是空地的情况下(关键前提) ,算出可以种花的最值。如[1,0,0,0,0,1]=>1
    连续空地数 可种花的最值
           0  => 0
           1  => 0
           2  => 0
           3  => 1
           4  => 1
           5  => 2
           6  => 2
           7  => 3

有感觉的老哥 ,估计已经有了想法,没错就是

parseInt((n - 1) / 2 ) = 可以种几颗 // (n为最近两个花 之间的空地数量)

得出了这个结论 就基本完成了 但是还有2种特殊情况,以下是完整代码(战胜84%的js提交)

let canPlaceFlowers = (flowerbed, n) => {
  let filedBegin = flowerbed[0] > 0 ? true : false;
  let filedEnd = flowerbed[flowerbed.length - 1] > 0 ? true : false;
  if (!filedBegin) {
    flowerbed.unshift(1, 0)
  }
  if (!filedEnd) {
    flowerbed.push(0, 1)
  }
  //上面步骤的原因
  // 遇到这两种情况[0, 0, 1, 0, 0]  或者[0]
  // 按照parseInt((n - 1) / 2)  规则得出的都是零 因为这种算法 是以  两边都是花的情况下的结果
  // 而上面这两种 0的两面 或者有一面 是没有花的 所以手动 给他们加上
  // [0, 0, 1, 0, 0]=> [1, 0, 0, 1, 0, 0, 0, 1]
  // [0]=> [1, 0, 0, 0, 1]
  // 这样就符合我们的规则了

  let size = 0  //最近两个花 之间的空地数量
  let canfiled = 0 //可以种植的数量
  for (let i = 1, len = flowerbed.length; i < len; i++) {
    if (flowerbed[i] > 0) {//
      if (size == 0) continue //说明 处在 1 1 相邻的情况 直接跳过
      let num = parseInt((size - 1) / 2) // 当前间隔最多可以种植的数量
      canfiled += num
      size = 0 //重置间隔数量
    } else {//当前是空地  空地数量+1
      size++
    }
  }
  return canfiled >= n
};
2.最快的范例 
这种思路是以每个循环的元素为核心 当 当前空地元素的前一个元素和后一个元素为空地 那么代表着能够种植,(当然 依然要考虑到目标数组的头尾为空地0的情况) 而且直接改变原数组 flowerbed[j] = 1 ->这是他逻辑中画龙点睛的步骤
var canPlaceFlowers = function (flowerbed, n) {
  // 定义一个sum = 0
  // 遍历花坛,找到这样一个位置,此位置空,&& 前后都为空,则sum+1
  // 判断sum与n大小比较
  [0, 1, 0]
  if (!n) return true;
  var sum = 0
  var length = flowerbed.length
  for (var j = 0; j < length; j++) {
    if (!flowerbed[j]) {//当前是 空地
      //对于右侧的限制条件 true 表示可以种植(仅对于左侧来讲)
      var leftVoid = j === 0 || flowerbed[j - 1] === 0
      //对于右侧的限制条件 true 表示可以种植(仅对于右侧来讲)
      var rightVoid = j === length - 1 || flowerbed[j + 1] === 0
      if (leftVoid && rightVoid) {
        // 可以种植
        flowerbed[j] = 1  //直接将改位置 种上花  让后面的判断顺利进行  比较关键
        sum++
        if (sum === n) {  //循环次数  可能少些 因为 sum的最大值是大于等于n 才能满足
          return true
        }
      }
    }
  }

  return false
}

如果喜欢LeetCode或者更多数据结构的内容,可以戳这里,欢迎star

扫一扫

往期文章

数据结构与算法-LeetCode 格雷编码(No.89)

数据结构与算法-LeetCode 种花问题(No.605)

LeetCode-电话号码的字母组合(No.17) 递归+hash

JavaScript 数据结构与算法 这题你会吗?

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/109442.html

相关文章

  • LeetCode-电话号码的字母组合(No.17) 递归+hash

    摘要:电话号码的字母组合给定一个仅包含数字的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下与电话按键相同。注意不对应任何字母。 LeetCode 17. 电话号码的字母组合 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下(与电话按键相同)。 注意 1 不对应任何字母。 showImg(https://user-gold-cdn.xit...

    周国辉 评论0 收藏0
  • 数据结构算法-LeetCode 格雷编码(No.89)

    摘要:例如,也是一个有效的格雷编码序列。示例输入输出解释我们定义格雷编码序列必须以开头。给定编码总位数为的格雷编码序列,其长度为。因此,当时,其格雷编码序列为。 LeetCode 89. 格雷编码 格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n,打印其格雷编码序列。格雷编码序列必须以 0 开头。第一个数与最后一位数 也只差以...

    Youngs 评论0 收藏0
  • 微信小程序中图片上传阿里云Oss

    摘要:微信小程序图片上传阿里云服务器也折腾了蛮久才解决的,所以特意去记录一下。上传失败第四步源码在这里如果觉得这面文章对你有帮助的话,可给我点个这里,谢谢最后,希望这篇文章对你有所帮助,真真确确是可以在微信小程序中上传图片到阿里云的。 本人今年6月份毕业,最近刚在上海一家小公司实习,做微信小程序开发。最近工作遇到一个小问题。 微信小程序图片上传阿里云服务器Oss也折腾了蛮久才解决的,所以特意...

    Yang_River 评论0 收藏0
  • 微信小程序中图片上传阿里云Oss

    摘要:微信小程序图片上传阿里云服务器也折腾了蛮久才解决的,所以特意去记录一下。上传失败第四步源码在这里如果觉得这面文章对你有帮助的话,可给我点个这里,谢谢最后,希望这篇文章对你有所帮助,真真确确是可以在微信小程序中上传图片到阿里云的。 本人今年6月份毕业,最近刚在上海一家小公司实习,做微信小程序开发。最近工作遇到一个小问题。 微信小程序图片上传阿里云服务器Oss也折腾了蛮久才解决的,所以特意...

    netmou 评论0 收藏0

发表评论

0条评论

xuexiangjys

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<