【算法与数据结构】860、LeetCode柠檬水找零

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：本题的思路比较简单，首先要保存收到的零钱，其次计算找零，最后分解找零。程序当中for循环遍历整个数组，然后stock保存收到的零钱，change表示找零。找零一共有三种情况，其中第三种情况最特殊：

• 1. 不用找零：固定
• 2. 找零5元：固定
• 3. 找零15元：可以分解为10+5或者5+5+5；但是我们需要优先用掉10元，因为5元更加万能，即可以找5元零钱也可以找15元零钱，而10元只能找15元的零钱。

  程序如下：

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+5else return false;}}return true;}
}; 

复杂度分析：

• 时间复杂度： $O(n)$。
• 空间复杂度：$O(1)$。

三、完整代码

# 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+5else 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