資料結構與演算法-LeetCode 種花問題(No.605)
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.最快的範例
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