今天做了一道很有意思的題目，雖然是分屬于貪心算法的一個(gè)題目，但是解法多樣，十分有趣，且不是很難理解，所以想在這里分享給大家。

---

題目描述：

假設(shè)有一個(gè)很長的花壇，一部分地塊種植了花，另一部分卻沒有。可是，花不能種植在相鄰的地塊上，它們會(huì)爭(zhēng)奪水源，兩者都會(huì)死去。

給你一個(gè)整數(shù)數(shù)組??flowerbed 表示花壇，由若干 0 和 1 組成，其中 0 表示沒種植花，1 表示種植了花。另有一個(gè)數(shù)?n ，能否在不打破種植規(guī)則的情況下種入?n?朵花？能則返回 true ，不能則返回 false。

示例 1：

輸入：flowerbed = [1,0,0,0,1], n = 1
輸出：true
示例 2：

輸入：flowerbed = [1,0,0,0,1], n = 2
輸出：false

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/can-place-flowers

---

這個(gè)題目我在這里為大家講解兩種方法：跳格子和貪心算法，二者各有其優(yōu)勢(shì)。

---

方法一：貪心算法

思路分析：

首先為大家介紹貪心算法的一種解題步驟，這種方法在思路上其實(shí)更為簡單，我們只需要考慮當(dāng)前位置和相鄰位置是否都為0，若是，則修改相關(guān)數(shù)據(jù)。這種方法的代碼十分簡潔，一個(gè)遍歷數(shù)組嵌套一個(gè)判斷語句。

最需要注意的一個(gè)點(diǎn)就是關(guān)于邊界的判斷問題：當(dāng)判斷位置是開頭結(jié)尾時(shí)，是不存在左鄰點(diǎn)或右鄰點(diǎn)的，所以對(duì)于i==0的情況，我們不判斷左鄰點(diǎn)是否為0，而改為判斷是否當(dāng)前位置為初始點(diǎn)，末尾點(diǎn)同理。

代碼如下：

class Solution { public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int length=flowerbed.size();for(int i=0;i<length;i++){if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == length-1 || flowerbed[i+1] == 0)){flowerbed[i]=1;n--;}}return n<=0;} };

運(yùn)行結(jié)果展示：

可以看到這種方法的效率中規(guī)中矩，但是其思路十分簡單，代碼也十分的簡潔?。

---

方法二：跳格子

這種方法的思路相比于貪心算法更為的巧妙：

首先我們明確一個(gè)前提：已給數(shù)列中是不存在相鄰花朵的，以此為前提，我們從頭遍歷（用跳格子的方法甚至不需要完整遍歷一次數(shù)組）。

毫無疑問，每個(gè)位置只有0/1兩種情況。

當(dāng)位置為1的時(shí)候，是什么情況呢？

如果當(dāng)前位置已經(jīng)是1，說明什么？下一位必定是空位，而且必然不能種花（因?yàn)樽竺嬉呀?jīng)有一朵花了），因此我們可以直接跳到下下位（i+2）

當(dāng)位置為0的時(shí)候，又會(huì)是什么情況呢？

大家可以思考一下，我們是通過跳格子的方法來到這一位的，每次碰到1都會(huì)跳兩格，這意味著當(dāng)前位置前一位必定是0，因此我們只需要判斷下一位是否為0

若為0，則說明這個(gè)位置可以種花，我們將n減去一個(gè)數(shù)字，并且繼續(xù)跳兩位（因?yàn)榉N下以后當(dāng)前位置可以視為1，步驟就和第一種情況一樣了），

若為1，則說明下一位為1，且下下位為0，因此我們直接跳三步，繼續(xù)下一次判斷

在這里有一個(gè)注意點(diǎn)：我們要考慮是否到達(dá)邊界的情況，如果說跳到了最后一位，即length-1，則必然可以種下，因?yàn)橛颐鏇]有數(shù)字，而左面又為0，如果繼續(xù)按照之前的判斷方法(判斷下一位是否為0)的話，就會(huì)導(dǎo)致內(nèi)存溢出

代碼如下：

class Solution { public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int len=flowerbed.size(),i;for(i=0;i<len &&n!=0;){if(flowerbed[i]==1)i+=2;//判斷是否到達(dá)尾部必須放在前面，不然會(huì)內(nèi)存溢出報(bào)錯(cuò)else if(i==len-1 || flowerbed[i+1]==0){n--;i+=2;}elsei+=3;}return n==0;} };

運(yùn)行結(jié)果展示：

?

可以看到用跳格子的方法，時(shí)間效率很高，因?yàn)槲覀儧]有遍歷整個(gè)數(shù)組，還是挑選了其中最關(guān)鍵的一部分。?

---

?

以上便是對(duì)這個(gè)問題兩種解決方法的闡述，在leetcode的評(píng)論區(qū)中還有很多優(yōu)質(zhì)的解答，大家可以參考一下。歡迎大家在評(píng)論區(qū)積極評(píng)論和提問，我會(huì)盡最大能力去幫助大家結(jié)局。下面是該題目的網(wǎng)址。

力扣https://leetcode-cn.com/problems/can-place-flowers/

?

總結(jié)

以上是生活随笔為你收集整理的跳格子/贪心算法例题详解：LeetCode605.种花问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。