文章目录
- 860. 柠檬水找零
- 题目解析
- 算法原理
- 代码实现
- 交换论证法
- 2208. 将数组和减半的最少操作次数
- 题目解析
- 算法原理
- 代码实现
- 交换论证法
- 179. 最大数
- 题目解析
- 算法原理
- 代码实现
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;}
};
