[Swift]LeetCode135.分发糖果|Candy

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

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

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

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

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

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

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

28ms

 1 public class Solution {
 2     func candy(_ ratings: [Int]) -> Int {
 3         let size = ratings.count
 4         
 5         if size == 0 {
 6             return -1
 7         }
 8         if size == 1 {
 9             return 1
10         }
11         
12         var candys = Array(repeating: 1, count: size)
13         
14         for i in 1..<size {
15             if ratings[i] > ratings[i - 1] {
16                 candys[i] = candys[i - 1] + 1
17             }
18         }
19         for i in 1..<size {
20             let j = size - i
21             if ratings[j - 1] > ratings[j], candys[j - 1] <= candys[j]{
22                 candys[j - 1] = candys[j] + 1
23             }
24         }
25         
26         var sum = 0
27         for i in 0..<size {
28             sum += candys[i]
29         }
30         return sum
31     }
32 }

60ms

 1 class Solution {
 2     func candy(_ ratings: [Int]) -> Int {
 3         var result = 1
 4         var more = 0 // 连升次数
 5         var less = 0 // 连降次数
 6         var mark = 0
 7         
 8         for index in 1..<ratings.count {
 9             let dis = ratings[index] - ratings[index - 1]
10             if dis > 0 { // 升
11                 more += 1
12                 less = 0
13                 
14                 result += more + 1
15             } else if dis == 0 {
16                 more = 0
17                 less = 0
18                 mark = 0
19                 result += 1
20             } else {
21                 if more > 0 {
22                     mark = more
23                     more = 0
24                 }
25                 less += 1
26                 result += less + (less > mark ? 1 : 0)
27             }
28         }
29         return result
30     }
31 }

84ms

 1 class Solution {
 2     func candy(_ ratings: [Int]) -> Int {
 3         var candies = Array(repeating:1,count:ratings.count)
 4         var numCandies = 0
 5         
 6         //Go forward
 7         for i in 1..<ratings.count {
 8             if(ratings[i]>ratings[i-1]) {
 9                 candies[i] = candies[i-1]+1
10             }
11         }
12         
13         for i in stride(from:ratings.count-2,through:0,by:-1) {
14             if(ratings[i]>ratings[i+1] && (candies[i] <= candies[i+1])) {
15                 candies[i] = candies[i+1]+1
16             }
17         }
18         
19         print(candies)
20         numCandies = candies.reduce(0,+)
21         
22         return numCandies
23     }
24 }

172ms

 1 class Solution {
 2     func candy(_ ratings: [Int]) -> Int {
 3         guard ratings.count > 0 else { return 0 }
 4 
 5         // o(n), space, nlog(n) time
 6         let orderedKids = ratings.enumerated().map { ($1, $0) }.sorted { $0.0 < $1.0 }
 7         
 8         // (n), space, n, time
 9         var candies = Array(repeating: 1, count: ratings.count)
10         
11         // n time
12         orderedKids.forEach { (rating, index) in
13             var currentCandy = candies[index]
14             if index > 0 && rating < ratings[index - 1] && currentCandy >= candies[index - 1] {
15                 candies[index - 1] = currentCandy + 1
16             }
17             if index < candies.count - 1 && rating < ratings[index + 1] && currentCandy >= candies[index + 1] {
18                 candies[index + 1] = currentCandy + 1
19             }
20         }
21         // n time, o (1) space
22         return candies.reduce(into: 0) { $0 += $1 }
23     }
24 }