• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode135.分发糖果|Candy

原作者: [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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode1121.将数组分成几个递增序列|DivideArrayIntoIncreasingSequences ...发布时间:2022-07-13
下一篇:
swift 学习- 11 -- 属性发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap