860. 柠檬水找零
题目链接：860. 柠檬水找零
题目解析
一杯柠檬水5块钱，每个顾客每次只能买一杯，支付的现金的面额有5块、10块、20块。
我们需要能够正确的找零，而且最开始我们手里没有钱。
如果遇上不能找零的，则返回false；如果从始至终能够正确找零，返回true。
bills：顾客支付的钱的面额
算法原理
分情况讨论：
顾客给5块，收下
顾客给10块，手上有5块，给5块，然后收下10块；没有返回false
顾客给20块
- 给三张5块
- 给一张5块，一张10块
此时这里就能体现贪心，5块钱可以在10块那里用，也可以在20块这里用，所以要尽可能保留5块钱。
所以优先选择给一张5块和一张10块。
代码实现
class Solution {
public:
bool lemonadeChange(vector<int>& bills)
{
if(bills[0] != 5) return false;
//unordered_map<int, int> hash;
int five = 0;
int ten = 0;
for(auto e : bills)
{
if(e == 5) five++;
else if(e == 10)
{
if(five == 0) return false;
five--;
ten++;
}
else
{
if(five != 0 && ten != 0)
{
five--;
ten--;
}
else if(five >= 3)
{
five -= 3;
}
else
{
return false;
}
}
}
return true;
}
};
交换论证法
证明策略：交换论证法
假设贪心策略的结果是：a b c d e f；最优解是e b c d a f，需要证明在不破坏最优解最优性质的前提下，能够将最优解调整成贪心解。
这里唯一要考虑的就是顾客给20块钱，该如何找零：
- 贪心策略，有10块和5块，肯定先将10块给出去
- 最优解，可能是三个5块，也能是5块、10块各一张
这里需要考虑不一样的情况，即最优解给的三张5块
此时就要看能不能将这种情况替换成贪心策略一模一样的，这里2种情况：
- 10块钱后面没用上：此时可以直接将最优解的三张5块，换成一张10块和一张5块（因为这个10块钱不影响后续操作）
- 10块钱有用上：依旧可以替换两张5块钱，两张5块钱后面也能抵一张10块钱
所以，不管是用或者不用，都能将最优解替换成贪心解。
2208. 将数组和减半的最少操作次数
题目链接：2208. 将数组和减半的最少操作次数
题目解析
给我们一个正整数数组nums，每次操作都能够从数组选一个数字，对其减半（后续还能继续操作这个数）
最后返回，将nums数组和至少减小一半的最小次数。
算法原理
最少操作次数，每次就挑选最大的，这就是我们的贪心策略。
由于要选择每次最大的元素，这需要用堆来辅助。
最大元素，大根堆。
代码实现
class Solution {
public:
int halveArray(vector<int>& nums)
{
double sum = 0;
priority_queue<double> heap;
for(auto e : nums)
{
sum += e;
heap.push(e);
}
double targer = sum / 2.0;
int ret = 0;
while(sum > targer)
{
double n = heap.top();
heap.pop();
sum -= n;
n /= 2.0;
sum += n;
ret++;
heap.push(n);
}
return ret;
}
};
交换论证法
这次还是一样，如果能将最优解不失最优性质的前提下将最优转换为贪心解，就能证明贪心策略是正确的。
由于是贪心策略，到此处的时候x >= y，这里分2种情况：
x在最优解当中没有用过，此时x可以直接替换y，y比x小，x减半，效果更足x在最优解后续操作使用过，此时也能替换，因为都是要使用的，先后顺序并没有关系，不会影响操作次数
此时不管怎样，都能进行替换。
179. 最大数
题目链接：179. 最大数
题目解析
给我们一个非负整数数组，让我们排列组合，找出最大的组合。
返回的是字符串，因为这个数字可能非常大。
算法原理
这个排列组合，差不多像排序：
正常排序（升序）：
它的本质就是确定元素的先后顺序，谁在前谁在后
规则：a > b a前 b后 a = b 都行 a < b b前 a后 本题也是确定元素的先后顺序，即找出排序规则即可
ab > ba a前 b后 ab = ba 都行 ab < ba b前 a后 这里的贪心就体现在每次比较都确定最好的排序序列
代码实现
class Solution {
public:
string largestNumber(vector<int>& nums)
{
vector<string> str_nums;
for(auto e : nums)
{
str_nums.push_back(to_string(e));
}
sort(str_nums.begin(), str_nums.end(), [](const string &s1, const string &s2)
{
return s1 + s2 > s2 + s1;
});
string ret;
for(auto e : str_nums)
{
ret += e;
}
if(ret[0] == '0') return "0";
return ret;
}
};