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

[Swift]LeetCode948.令牌放置|BagofTokens

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

You have an initial power P, an initial score of 0 points, and a bag of tokens.

Each token can be used at most once, has a value token[i], and has potentially two ways to use it.

  • If we have at least token[i] power, we may play the token face up, losing token[i] power, and gaining 1 point.
  • If we have at least 1 point, we may play the token face down, gaining token[i] power, and losing 1point.

Return the largest number of points we can have after playing any number of tokens.

Example 1:

Input: tokens = 50
Output: 0

Example 2:

Input: tokens = 150
Output: 1

Example 3:

Input: tokens = 200
Output: 2

 Note:

  1. tokens.length <= 1000
  2. 0 <= tokens[i] < 10000
  3. 0 <= P < 10000

你的初始能量为 P,初始分数为 0,只有一包令牌。

令牌的值为 token[i],每个令牌最多只能使用一次,可能的两种使用方法如下:

  • 如果你至少有 token[i] 点能量,可以将令牌置为正面朝上,失去 token[i] 点能量,并得到 1 分。
  • 如果我们至少有 1 分,可以将令牌置为反面朝上,获得 token[i] 点能量,并失去 1 分。

在使用任意数量的令牌后,返回我们可以得到的最大分数。

示例 1:

输入:tokens = [100], P = 50
输出:0

示例 2:

输入:tokens = [100,200], P = 150
输出:1

示例 3:

输入:tokens = [100,200,300,400], P = 200
输出:2

提示:

  1. tokens.length <= 1000
  2. 0 <= tokens[i] < 10000
  3. 0 <= P < 10000

40ms
 1 class Solution {
 2     func bagOfTokensScore(_ tokens: [Int], _ P: Int) -> Int {
 3         var curTokens = tokens
 4         var curP = P
 5         curTokens.sort{$0<$1}
 6         var lo = 0;
 7         var hi = curTokens.count-1;
 8         var points = 0
 9         var ans = 0
10         while (lo <= hi && (curP >= curTokens[lo] || points > 0)){
11             while (lo <= hi && curP >= curTokens[lo]){
12                 curP -= curTokens[lo]
13                 lo += 1
14                 points += 1;
15             }
16             ans = ans > points ? ans : points
17             if(lo <= hi && points > 0){
18                 curP += curTokens[hi]
19                 hi -= 1
20                 points -= 1
21             }
22         }
23         
24         return ans
25     }
26 }

44ms

 1 class Solution {
 2     func bagOfTokensScore(_ tokens: [Int], _ P: Int) -> Int {
 3         guard !tokens.isEmpty else { return 0 }
 4         let tokens = tokens.sorted()
 5         
 6         var l = 0
 7         var h = tokens.count - 1
 8         var result = 0
 9         var current = 0
10         var power = P
11         
12         while l <= h {
13             let cToken = tokens[l]
14             if power >= cToken {
15                 current += 1
16                 result = max(result, current)
17                 power -= cToken
18                 l += 1
19             } else if current > 0 {
20                 current -= 1
21                 power += tokens[h]
22                 h -= 1
23             } else {
24                 break
25             }
26         }
27         
28         return result
29     }

72ms

 1 class Solution {
 2     
 3     func bagOfTokensScore(_ tokens: [Int], _ power: Int) -> Int {
 4         let tokens = tokens.sorted()
 5         var power = power
 6 
 7         var leftIndex = 0
 8         var rightIndex = tokens.count - 1
 9         var points = 0
10         var maxPoints = 0
11         while leftIndex <= rightIndex {
12             if power >= tokens[leftIndex] {
13                 power -= tokens[leftIndex]
14                 leftIndex += 1
15                 points += 1
16                 maxPoints = max(maxPoints, points)
17             } else if points > 0 {
18                 power += tokens[rightIndex]
19                 rightIndex -= 1
20                 points -= 1
21             } else {
22                 break
23             }
24         }
25 
26         return maxPoints
27     }
28 }

76ms

 1 class Solution {
 2     func bagOfTokensScore(_ tokens: [Int], _ P: Int) -> Int {
 3         var tokens = tokens.sorted(by:<)
 4         var P = P
 5         if tokens.count == 0 || P < tokens[0]
 6         {
 7             return 0
 8         }
 9         var n:Int = tokens.count
10         var p:Int = 0
11         var point:Int = 0
12         var ret:Int = 0
13         for i in 0...n
14         {
15             if i > 0
16             {
17                 P += tokens[n-i]
18                 point -= 1
19             }
20             while(p < n-i && P >= tokens[p])
21             {
22                 P -= tokens[p]
23                 point += 1
24                 p += 1
25             }
26             if p <= n-i
27             {
28                 ret = max(ret, point)
29             }
30         }
31         return ret
32     }
33 }

144ms
 1 class Solution {
 2     func bagOfTokensScore(_ tokens: [Int], _ P: Int) -> Int {
 3         
 4           if tokens.count == 0 {
 5     return 0
 6   }
 7   
 8   var sortedTokens = tokens.sorted()
 9   
10   if sortedTokens[0] > P {
11     return 0
12   }
13   
14   var maxScore = 0
15   var score = 0
16   var currentPower = P
17   
18   while !sortedTokens.isEmpty {
19     let firstToken = sortedTokens.first!
20     print("firstToken \(firstToken) currentPower \(currentPower)")
21     if firstToken <= currentPower {
22       score += 1
23       maxScore = max(maxScore, score)
24       currentPower -= sortedTokens.removeFirst()
25     } else {
26       score -= 1
27       currentPower += sortedTokens.removeLast()
28       print("currentPower \(currentPower)")
29     }
30   }
31   
32   return maxScore
33 }
34 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode591.标签验证器|TagValidator发布时间:2022-07-13
下一篇:
[Swift]LeetCode1051.高度检查器|HeightChecker发布时间: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