摘要:能否在不打破種植規則的情況下種入朵花能則返回,不能則返回。示例輸入輸出示例輸入輸出注意數組內已種好的花不會違反種植規則。輸入的數組長度范圍為。是非負整數,且不會超過輸入數組的大小。
LeetCode 605. 種花問題
假設你有一個很長的花壇,一部分地塊種植了花,另一部分卻沒有??墒?,花卉不能種植在相鄰的地塊上,它們會爭奪水源,兩者都會死去。
給定一個花壇(表示為一個數組包含0和1,其中0表示沒種植花,1表示種植了花),和一個數 n 。能否在不打破種植規則的情況下種入 n 朵花?能則返回True,不能則返回False。
示例 1:
示例 2:
我的思路
連續空地數 可種花的最值 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 數據結構與算法 這題你會嗎?
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/109442.html
摘要:電話號碼的字母組合給定一個僅包含數字的字符串,返回所有它能表示的字母組合。給出數字到字母的映射如下與電話按鍵相同。注意不對應任何字母。 LeetCode 17. 電話號碼的字母組合 給定一個僅包含數字 2-9 的字符串,返回所有它能表示的字母組合。給出數字到字母的映射如下(與電話按鍵相同)。 注意 1 不對應任何字母。 showImg(https://user-gold-cdn.xit...
摘要:例如,也是一個有效的格雷編碼序列。示例輸入輸出解釋我們定義格雷編碼序列必須以開頭。給定編碼總位數為的格雷編碼序列,其長度為。因此,當時,其格雷編碼序列為。 LeetCode 89. 格雷編碼 格雷編碼是一個二進制數字系統,在該系統中,兩個連續的數值僅有一個位數的差異。給定一個代表編碼總位數的非負整數 n,打印其格雷編碼序列。格雷編碼序列必須以 0 開頭。第一個數與最后一位數 也只差以...
摘要:微信小程序圖片上傳阿里云服務器也折騰了蠻久才解決的,所以特意去記錄一下。上傳失敗第四步源碼在這里如果覺得這面文章對你有幫助的話,可給我點個這里,謝謝最后,希望這篇文章對你有所幫助,真真確確是可以在微信小程序中上傳圖片到阿里云的。 本人今年6月份畢業,最近剛在上海一家小公司實習,做微信小程序開發。最近工作遇到一個小問題。 微信小程序圖片上傳阿里云服務器Oss也折騰了蠻久才解決的,所以特意...
摘要:微信小程序圖片上傳阿里云服務器也折騰了蠻久才解決的,所以特意去記錄一下。上傳失敗第四步源碼在這里如果覺得這面文章對你有幫助的話,可給我點個這里,謝謝最后,希望這篇文章對你有所幫助,真真確確是可以在微信小程序中上傳圖片到阿里云的。 本人今年6月份畢業,最近剛在上海一家小公司實習,做微信小程序開發。最近工作遇到一個小問題。 微信小程序圖片上傳阿里云服務器Oss也折騰了蠻久才解決的,所以特意...
閱讀 1076·2021-11-22 14:56
閱讀 1520·2019-08-30 15:55
閱讀 3359·2019-08-30 15:45
閱讀 1655·2019-08-30 13:03
閱讀 2868·2019-08-29 18:47
閱讀 3334·2019-08-29 11:09
閱讀 2641·2019-08-26 18:36
閱讀 2615·2019-08-26 13:55