上海住房和城乡建设局网站首页,wordpress注释符号,wordpress 宽度,免费搭建文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;本题的思路比较简单#xff0c;首先要保存收到的零钱#xff0c;其次计算找零#xff0c;最后分解找… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析本题的思路比较简单首先要保存收到的零钱其次计算找零最后分解找零。程序当中for循环遍历整个数组然后stock保存收到的零钱change表示找零。找零一共有三种情况其中第三种情况最特殊 不用找零固定 找零5元固定 找零15元可以分解为105或者555但是我们需要优先用掉10元因为5元更加万能即可以找5元零钱也可以找15元零钱而10元只能找15元的零钱。 程序如下
class Solution {
public:bool lemonadeChange(vectorint bills) {// 1.计算找零 2.找零的分解vectorint 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) { // 分解成105,优先用10元找零stock[1]--;stock[0]--;}else if (stock[0] 3) stock[0] - 3; // 分解成555else return false;}}return true;}
}; 复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( 1 ) O(1) O(1)。
三、完整代码
# include iostream
# include vector
using namespace std;class Solution {
public:bool lemonadeChange(vectorint bills) {// 1.计算找零 2.找零的分解vectorint 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) { // 分解成105,优先用10元找零stock[1]--;stock[0]--;}else if (stock[0] 3) stock[0] - 3; // 分解成555else return false;}}return true;}
}; int main() {vectorint bills { 5,5,5,10,20 }; // 加油站的油量Solution s1;int result s1.lemonadeChange(bills);cout result endl;system(pause);return 0;
}end
