135. 分发糖果
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
class Solution {
public:
//贪心：局部最优推出全局最优：
//右边孩子比左边孩子大，那么就=左边孩子糖果数+1，相反亦如此
//要左右孩子分开考虑，不能同时考虑
int candy(vector<int>& ratings) {
vector<int> candies(ratings.size(), 1);
//先考虑当前孩子得分比左边的孩子得分高的情况
for(int i = 1; i < ratings.size(); i++)
{
if(ratings[i] > ratings[i - 1])
{
candies[i] = candies[i - 1] + 1;//那么当前孩子就比左边的孩子多一个
}
}
//再考虑当前孩子比右边孩子大，此时需要从后往前遍历
for(int i = ratings.size() - 2; i >= 0; i--)
{
if(ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1])
{
//如果当前孩子糖果比右边孩子少，那么左边孩子比右边孩子多一个（已经大的话就不用加了）
candies[i] = candies[i + 1] + 1;
}
}
//求个和
int sum = 0;
for(auto i : candies)
{
sum += i;
}
return sum;
}
};
这道题要分开考虑，要先考虑一边再考虑另一边，不能同时考虑一个孩子的左右两个孩子，还要注意在考虑第二边的时候，要注意目前糖果数量的对比，如果经历了第一次遍历，更改了糖果数量，在进行第二次遍历时已经比右边糖果大了，那就不用再+1了。
860. 柠檬水找零
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
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
vector<int > cash(2, 0);
//开始卖柠檬水
for(int i = 0; i < bills.size(); i++)
{
if(bills[i] == 5)//如果顾客支付5刀
{
cash[0]++;
}
else if(bills[i] == 10)//如果顾客支付10刀
{
if(cash[0] > 0)//如果有5刀的零钱
{
cash[1]++;//10刀零钱+1
cash[0]--;//5刀零钱-1
}else return false;
}
else//如果顾客支付20刀
{
if(cash[0] > 0 && cash[1] > 0)//有10和5刀的零钱
{
cash[0]--;
cash[1]--;
}
else if(cash[0] >= 3)//如果只有5刀的零钱而且5刀还必须多余三张
{
cash[0] -= 3;
}
else return false;
}
}
return true;
}
};
这道题相对上面那道题就简单多了，方法不难，就是贪心，就是这个分类讨论得分对。