所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
??思路分析:本题的思路比较简单,首先要保存收到的零钱,其次计算找零,最后分解找零。程序当中for循环遍历整个数组,然后stock保存收到的零钱,change表示找零。找零一共有三种情况,其中第三种情况最特殊:
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
// 1.计算找零 2.找零的分解
vector<int> stock(4, 0);
for (int i = 0; i < bills.size(); i++) {
stock[bills[i] / 5 - 1]++;
int change = bills[i] - 5;
if (change == 0) continue; // 不用找钱
else if (change == 5) { // 找5元
if (stock[0] < 1) return false;
stock[0]--;
}
else{ // 找15元
if (stock[1] >= 1 && stock[0] >= 1) { // 分解成10+5,优先用10元找零
stock[1]--;
stock[0]--;
}
else if (stock[0] >= 3) stock[0] -= 3; // 分解成5+5+5
else return false;
}
}
return true;
}
};
复杂度分析:
# include <iostream>
# include <vector>
using namespace std;
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
// 1.计算找零 2.找零的分解
vector<int> stock(4, 0);
for (int i = 0; i < bills.size(); i++) {
stock[bills[i] / 5 - 1]++;
int change = bills[i] - 5;
if (change == 0) continue; // 不用找钱
else if (change == 5) { // 找5元
if (stock[0] < 1) return false;
stock[0]--;
}
else{ // 找15元
if (stock[1] >= 1 && stock[0] >= 1) { // 分解成10+5,优先用10元找零
stock[1]--;
stock[0]--;
}
else if (stock[0] >= 3) stock[0] -= 3; // 分解成5+5+5
else return false;
}
}
return true;
}
};
int main() {
vector<int> bills = { 5,5,5,10,20 }; // 加油站的油量
Solution s1;
int result = s1.lemonadeChange(bills);
cout << result << endl;
system("pause");
return 0;
}
end