[Swift]LeetCode860.柠檬水找零|LemonadeChange

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

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

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

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

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

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

At a lemonade stand, each lemonade costs $5.

Customers are standing in a queue to buy from you, and order one at a time (in the order specified by bills).

Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer, so that the net transaction is that the customer pays $5.

Note that you don't have any change in hand at first.

Return true if and only if you can provide every customer with correct change.

Example 1:

Input: [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:

Input: [5,5,10]
Output: true

Example 3:

Input: [10,10]
Output: false

Example 4:

Input: [5,5,10,10,20]
Output: false
Explanation: 
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can't give change of $15 back because we only have two $10 bills.
Since not every customer received correct change, the answer is false.

Note:

0 <= bills.length <= 10000
bills[i] will be either 5, 10, or 20.

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

输入：[5,5,10]
输出：true

示例 3：

输入：[10,10]
输出：false

示例 4：

输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

0 <= bills.length <= 10000
bills[i] 不是 5 就是 10 或是 20

Runtime: 104 ms

Memory Usage: 19 MB

 1 class Solution {
 2     func lemonadeChange(_ bills: [Int]) -> Bool {        
 3         var fiveLeft = 0 
 4         var tenLeft = 0
 5         var twentyLeft = 0
 6         for i in 0..<bills.count {
 7             if bills[i] == 5 {
 8                 fiveLeft += 1
 9             } else if bills[i] == 10 {
10                 tenLeft += 1
11                 fiveLeft -= 1
12             } else {
13                 twentyLeft += 1
14                 if tenLeft > 0 {
15                     tenLeft -= 1
16                     fiveLeft -= 1
17                 } else {
18                     fiveLeft -= 3
19                 }                
20             }
21             
22             if fiveLeft < 0 || tenLeft < 0 {
23                 return false
24             }            
25         }
26         
27         return true        
28     }
29 }

104ms

 1 class Solution {
 2     func lemonadeChange(_ bills: [Int]) -> Bool {
 3         if bills.count == 0 {
 4             return true
 5         }
 6         
 7         var fiveDollarBills = 0
 8         var tenDollarBills = 0
 9         
10         for bill in bills {
11             if bill == 5 {
12                 fiveDollarBills += 1
13             } else if bill == 10 {
14                 if fiveDollarBills == 0 {
15                     return false
16                 }
17                 fiveDollarBills -= 1
18                 tenDollarBills += 1
19             } else if bill == 20 {
20                 if tenDollarBills > 0 && fiveDollarBills > 0 {
21                     tenDollarBills -= 1
22                     fiveDollarBills -= 1
23                 } else if fiveDollarBills > 2 {
24                     fiveDollarBills -= 3
25                 } else {
26                     return false
27                 }
28             }
29         }
30         
31         return true
32     }
33 }

108ms

 1 class Solution {
 2     func lemonadeChange(_ bills: [Int]) -> Bool {        
 3         var fiveLeft = 0 
 4         var tenLeft = 0
 5         var twentyLeft = 0
 6         for i in 0..<bills.count {
 7             if bills[i] == 5 {
 8                 fiveLeft += 1
 9             } else if bills[i] == 10 {
10                 tenLeft += 1
11                 fiveLeft -= 1
12             } else {
13                 twentyLeft += 1
14                 if tenLeft > 0 {
15                     tenLeft -= 1
16                     fiveLeft -= 1
17                 } else {
18                     fiveLeft -= 3
19                 }                
20             }            
21             if fiveLeft < 0 {
22                 return false
23             }            
24         }        
25         return true        
26     }
27 }

108ms

 1 class Solution {
 2     func lemonadeChange(_ bills: [Int]) -> Bool {
 3         var c5 = 0
 4         var c10 = 0
 5 
 6         for i in bills {
 7             if i == 5{
 8                 c5 += 1
 9             }
10             else if i == 10{
11                 if c5 > 0{
12                     c5 -= 1
13                     c10 += 1
14                 }else{
15                     return false
16                 }
17             }else {
18                 if c5 > 0 && c10 > 0{
19                     c5 -= 1
20                     c10 -= 1
21                 }else if c5 > 3{
22                     c5 -= 3
23                 }else{
24                     return false
25                 }
26             }
27         }
28         return true
29     }
30 }

110ms

 1 class Solution {
 2    func lemonadeChange(_ bills: [Int]) -> Bool {
 3        
 4         var dic = [Int:Int]()
 5         dic.updateValue(0, forKey: 5)
 6         dic.updateValue(0, forKey: 10)
 7         dic.updateValue(0, forKey: 20)
 8         for i  in 0..<bills.count {
 9             if bills[i] - 5 == 0{
10                 dic.updateValue(dic[5]! + 1, forKey: 5)
11                 continue
12             }
13             let dif = bills[i] - 5
14             let tenCount =  dif/10
15             let fiveCount =  dif/5
16             let sfiveCount =  fiveCount - tenCount * 2
17             var needFive: Int = 0
18             
19             if dic[10]! - tenCount < 0{
20                  needFive = (tenCount - dic[10]!) * 2
21             }
22             if dic[5]! < needFive  + sfiveCount{
23                 return false
24             }else{
25                dic.updateValue(max(0, dic[5]! - needFive - sfiveCount), forKey: 5)
26             }
27             dic.updateValue(max(0, dic[10]! - tenCount), forKey: 10)
28             dic.updateValue(dic[bills[i]]!  + 1, forKey: bills[i])
29         }
30        return true
31     }
32 }

112ms

 1 class Solution {
 2     func lemonadeChange(_ bills: [Int]) -> Bool {
 3         var fiveSum = 0, tenSum = 0, twentySum = 0
 4         let five = 5, ten = 10, twenty = 20
 5         
 6         for bill in bills {
 7             switch bill {
 8             case five:
 9                 fiveSum += bill
10             case ten:
11                 if fiveSum > 0 {
12                     fiveSum -= five
13                     tenSum += bill
14                 } else {
15                     return false
16                 }
17             case twenty:
18                 if tenSum > 0 {
19                     if fiveSum > 0 {
20                         tenSum -= ten
21                         fiveSum -= five
22                     } else {
23                         return false
24                     }
25                 } else if fiveSum >= five * 3 {
26                     fiveSum -= five * 3
27                 } else {
28                     return false
29                 }
30                 
31                 twentySum += bill
32             default: break
33             }
34         }
35         
36         return true
37     }
38 }

120ms

 1 class Solution {
 2     func lemonadeChange(_ bills: [Int]) -> Bool {
 3         var bank = [5:0, 10:0]
 4         for bill in bills {
 5             if bill == 5 {
 6                 bank[5]! += 1
 7             }
 8 
 9             if bill == 10 {
10                 if bank[5]! == 0 {
11                     return false
12                 } else {
13                     bank[5]! -= 1
14                     bank[10]! += 1
15                 }
16             }
17 
18             if bill == 20 {
19                 if bank[10]! > 0 && bank[5]! > 0 {
20                     bank[10]! -= 1
21                     bank[5]! -= 1
22                 } else if bank[5]! >= 3 {
23                     bank[5]! -= 3
24                 } else {
25                     return false
26                 }
27             }
28         }
29         return true
30     }
31 }