加载中...
605-种花问题(Can Place Flowers)
发表于:2021-12-03 | 分类: 简单
字数统计: 306 | 阅读时长: 1分钟 | 阅读量:

原文链接: https://leetcode-cn.com/problems/can-place-flowers

英文原文

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

 

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

 

Constraints:

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

中文题目

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

给你一个整数数组  flowerbed 表示花坛,由若干 01 组成,其中 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 <= flowerbed.length <= 2 * 104
  • flowerbed[i]01
  • flowerbed 中不存在相邻的两朵花
  • 0 <= n <= flowerbed.length

通过代码

高赞题解

题解

题目要求是否能在不打破规则的情况下插入n朵花,与直接计算不同,采用“跳格子”的解法只需遍历不到一遍数组,处理以下两种不同的情况即可:

【1】当遍历到index遇到1时,说明这个位置有花,那必然从index+2的位置才有可能种花,因此当碰到1时直接跳过下一格。

【2】当遍历到index遇到0时,由于每次碰到1都是跳两格,因此前一格必定是0,此时只需要判断下一格是不是1即可得出index这一格能不能种花,如果能种则令n减一,然后这个位置就按照遇到1时处理,即跳两格;如果index的后一格是1,说明这个位置不能种花且之后两格也不可能种花(参照【1】),直接跳过3格。

当n减为0时,说明可以种入n朵花,则可以直接退出遍历返回true;如果遍历结束n没有减到0,说明最多种入的花的数量小于n,则返回false。

(感谢3kna1j提出的改进)

代码


public boolean canPlaceFlowers(int[] flowerbed, int n) {

	for (int i = 0, len = flowerbed.length; i < len && n > 0;) {

		if (flowerbed[i] == 1) {

			i += 2;

		} else if (i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {

			n--;

			i += 2;

		} else {

			i += 3;

		}

	}

	return n <= 0;

}

执行用时:1 ms, 在所有 Java 提交中击败了100%的用户

内存消耗:39.7 MB, 在所有 Java 提交中击败了88.08%的用户

统计信息

通过次数 提交次数 AC比率
114757 344887 33.3%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
提莫攻击 简单
行星碰撞 中等
上一篇:
601-体育馆的人流量(Human Traffic of Stadium)
下一篇:
606-根据二叉树创建字符串(Construct String from Binary Tree)
本文目录
本文目录