forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 14
/
lemonade-change.cpp
56 lines (54 loc) · 1.43 KB
/
lemonade-change.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Time: O(n)
// Space: O(1)
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
static const vector<int> coins = {20, 10, 5};
unordered_map<int, int> counts;
for (const auto& bill : bills) {
++counts[bill];
auto change = bill - coins.back();
for (const auto& coin : coins) {
if (change == 0) {
break;
}
if (change >= coin) {
const auto count = min(counts[coin], change / coin);
counts[coin] -= count;
change -= coin * count;
}
}
if (change != 0) {
return false;
}
}
return true;
}
};
class Solution2 {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0;
for (const auto& bill : bills) {
if (bill == 5) {
++five;
} else if (bill == 10) {
if (!five) {
return false;
}
--five;
++ten;
} else {
if (five && ten) {
--five;
--ten;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
};