[Swift]LeetCode605.种花问题|CanPlaceFlowers

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10455207.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Suppose 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 - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it 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

Note:

The input array won't violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won't exceed the input array size.

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

给定一个花坛（表示为一个数组包含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 是非负整数，且不会超过输入数组的大小。

Runtime: 128 ms

Memory Usage: 19.3 MB

 1 class Solution {
 2     func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
 3         var flowerbed = flowerbed
 4         var n = n
 5         flowerbed.insert(0,at:0)
 6         flowerbed.append(0)
 7         var i:Int = 1
 8         while(i < flowerbed.count - 1)
 9         {
10             if n == 0 {return true}
11             if flowerbed[i - 1] + flowerbed[i] + flowerbed[i + 1] == 0
12             {
13                 n -= 1
14                 i += 1  
15             }
16             i += 1            
17         }
18         return n <= 0
19     }
20 }

132ms

 1 class Solution {
 2     func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
 3         if n == 0{
 4             return true
 5         }
 6         var pending = n
 7         
 8         var currentIndex = 0
 9         var foundOne = false
10         while currentIndex < flowerbed.count{
11             if flowerbed[currentIndex] == 0{
12                 if foundOne || (currentIndex < flowerbed.count - 1 && flowerbed[currentIndex + 1] == 1){
13                     foundOne = false
14                     currentIndex += 1
15                 }
16                 else{
17                     pending -= 1
18                     if pending == 0{
19                         return true
20                     }
21                     currentIndex += 2
22                 }
23             }
24             else if flowerbed[currentIndex] == 1{
25                 foundOne = true
26                 currentIndex += 1
27             }
28             else{
29                 currentIndex += 1
30             }
31         }
32         return pending == 0
33     }
34 }

136ms

 1 class Solution {
 2     func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
 3         guard n > 0 else {
 4             return true
 5         }
 6 
 7         var left = n
 8         var newArray = [0]
 9         newArray.append(contentsOf: flowerbed)
10         newArray.append(0)
11         var i = 0
12         while i < newArray.count - 2 {
13             if newArray[i] == 0 && newArray[i+1] == 0 && newArray[i+2] == 0 {
14                 left -= 1
15                 i += 1
16                 if left == 0 {
17                     return true
18                 }
19             }
20             i += 1
21         }
22         return left == 0
23     }
24 }

140ms

 1 class Solution {
 2     func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
 3         var flowerbed = flowerbed
 4         var n = n
 5         var i = 0
 6         while i < flowerbed.count && n > 0 {
 7             if flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.count - 1 || flowerbed[i + 1] == 0) {
 8                 n -= 1
 9                 flowerbed[i] = 1
10             }
11             i += 1
12         }
13         return n == 0
14     }
15 }

144ms

 1 class Solution {
 2     func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
 3         var result = 0
 4         var count = 1
 5         for b in flowerbed {
 6             if b == 0 {
 7                 count += 1
 8             } else if b == 1 {
 9                 result += (count-1)/2
10                 count = 0
11             }
12         }
13         result += count / 2
14         return result >= n
15     }
16 }

152ms

 1 class Solution {
 2     func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
 3         if n == 0 {return true}
 4         
 5         
 6         var pre = -2
 7         var count = n
 8         for (index, num) in flowerbed.enumerated() {
 9             if num == 1 {
10                 count -= (index - pre - 1 - 1) / 2
11                 pre = index
12             }
13         }
14         count -= (flowerbed.count - pre - 1) / 2
15         return count <= 0
16     }
17 }

172ms

 1 class Solution {
 2     func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
 3         // how many possible position
 4          var adjcent = 0 
 5         // how many consequent 0 start with 1 because plant can be placed at first position it means the left of first position.
 6         var c = 1
 7         for i in 0..<flowerbed.count{
 8             if flowerbed[i] == 0 {
 9                 c += 1
10             }else{
11                 adjcent += (c-1)/2
12                 c = 0
13             }
14         }
15         // last consequent 0 won't be calculated within the loop if last position is 0. Like first position, last position'right is 0 as well.
16         adjcent += c/2 
17         return adjcent >= n
18     }
19 }

180ms

 1 class Solution {
 2   func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
 3     var flowerPlaced = 0
 4     
 5     var lastOne = -1
 6     var i = 0
 7     while i < flowerbed.count {
 8       while i < flowerbed.count && flowerbed[i] == 0 {
 9         i += 1
10       }
11       
12       let space = i - lastOne - 1
13       
14       if lastOne >= 0 && i < flowerbed.count {
15         flowerPlaced += (space - 1) / 2
16       } else if lastOne == -1 && i == flowerbed.count {
17         flowerPlaced += (space + 1) / 2
18       } else {
19         flowerPlaced += space / 2
20       }
21       
22       if flowerPlaced >= n {
23         return true
24       }
25       
26       while i < flowerbed.count && flowerbed[i] == 1 {
27         i += 1
28       }
29       lastOne = i - 1
30     }
31     
32     return false
33   }
34 }

196ms

 1 class Solution {
 2   func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
 3     var planted = 0
 4     
 5     var space = 1
 6     
 7     for plot in flowerbed {
 8       if plot == 0 {
 9         space += 1
10       } else {
11         planted += (space - 1) / 2
12         space = 0
13       }
14     }
15     
16     return (planted + space / 2) >= n
17   }
18 }