邯郸网站建设邯郸网站制作,网站建设视觉营销,怎么自己建立网站及建立网站方法,坚决把快准严细实要求落实到位其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 方法一#xff1a;贪心
2.2 贪心算法一般思路
三、代码
3.1 方法一#xf… 其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 方法一贪心
2.2 贪心算法一般思路
三、代码
3.1 方法一贪心
四、复杂度分析
4.1 方法一贪心 前言
这是力扣的 605 题难度为简单解题方案有很多种本文讲解我认为最奇妙的一种。
我的博客即将同步至腾讯云开发者社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code3ev3gir1q680g 一、题目描述
假设有一个很长的花坛一部分地块种植了花另一部分却没有。可是花不能种植在相邻的地块上它们会争夺水源两者都会死去。
给你一个整数数组 flowerbed 表示花坛由若干 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 flowerbed.length 2 * 104flowerbed[i] 为 0 或 1flowerbed 中不存在相邻的两朵花0 n flowerbed.length 二、题解
2.1 方法一贪心
思路与算法
题目要求是否能在不打破规则的情况下插入n朵花与直接计算不同采用“跳格子”的解法只需遍历不到一遍数组处理以下两种不同的情况即可
当遍历到index遇到1时说明这个位置有花那必然从index2的位置才有可能种花因此当碰到1时直接跳过下一格。当遍历到index遇到0时由于每次碰到1都是跳两格因此前一格必定是0此时只需要判断下一格是不是1即可得出index这一格能不能种花如果能种则令n减一然后这个位置就按照遇到1时处理即跳两格如果index的后一格是1说明这个位置不能种花且之后两格也不可能种花参照 1 直接跳过3格。
当n减为0时说明可以种入n朵花则可以直接退出遍历返回true如果遍历结束n没有减到0说明最多种入的花的数量小于n则返回false。
2.2 贪心算法一般思路
贪心算法的思路是从问题的某一个初始解出发然后通过一系列的贪心选择每一步都做出在当前看来最好的选择从而希望导致结果是整体最优的算法。这个算法并不会从整体最优上加以考虑它所做出的仅仅是在某种意义上的局部最优解。
具体来说贪心算法的步骤如下
建立数学模型来描述问题。把求解的问题分成若干个子问题。对每个子问题求解得到子问题的局部最优解。把子问题的解局部最优解合成原来解问题的一个解。
贪心算法的关键在于贪心选择性质和制定贪心策略其中贪心选择性质是指问题的最优解可以通过一系列局部最优的选择达到且每一步的选择依赖于以前作出的选择但不依赖于后面要作出的选择。而贪心策略则是为了达到问题的最优解或较优解而制定的策略。
需要注意的是贪心算法并不总是能够得到全局最优解因为它每一步都只考虑当前的最优选择而忽略了全局的情况。因此贪心算法适用于那些具有最优子结构性质和贪心选择性质的问题。 三、代码
3.1 方法一贪心
Java版本 class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {for (int i 0; i flowerbed.length 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;}
} C版本 class Solution {
public:bool canPlaceFlowers(vectorint flowerbed, int n) {for (int i 0; i flowerbed.size() n 0;) {if (flowerbed[i] 1) {i 2;} else if (i flowerbed.size() - 1 || flowerbed[i 1] 0) {n--;i 2;} else {i 3;}}return n 0;}
};Python版本 class Solution:def canPlaceFlowers(self, flowerbed, n):i 0while i len(flowerbed) and n 0:if flowerbed[i] 1:i 2elif i len(flowerbed) - 1 or flowerbed[i 1] 0:n - 1i 2else:i 3return n 0Go版本 package main import fmt func canPlaceFlowers(flowerbed []int, n int) bool { i : 0 for i len(flowerbed) n 0 { if flowerbed[i] 1 { i 2 } else if i len(flowerbed)-1 || flowerbed[i1] 0 { n - 1 i 2 } else { i 3 } } return n 0
} func main() { flowerbed : []int{1, 0, 0, 0, 1} n : 1 result : canPlaceFlowers(flowerbed, n) fmt.Println(result) // Output: true
} 四、复杂度分析
4.1 方法一贪心
时间复杂度O(m)其中 m 是数组 flowerbed 的长度。需要遍历数组一次。空间复杂度O(1)。额外使用的空间为常数。
