【贪心算法】day1
📝前言说明：
- 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
- 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）这个贪心算法正确性的证明
- 文章中的理解仅为个人理解。如有错误，感谢纠错
🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀ZEEKLOG主页 愚润泽
你可以点击下方链接，进行其他贪心算法题目的学习
| 点击链接 | 开始学习 |
|---|---|
| 贪心day1 | 贪心day2 |
| 贪心day3 | 贪心day4 |
| 贪心day5 | 贪心day6 |
| 贪心day7 | 贪心day8 |
| 贪心day9 | 贪心day10 |
也可以点击下面连接，学习其他算法
| 点击链接 | 开始学习 |
|---|---|
| 优选专题 | 动态规划 |
| 递归、搜索与回溯 | 贪心算法 |
题单获取→ 【贪心算法】题单汇总
题目
贪心算法导论
贪心策略的核心思想：局部最优 当做 全局最优
- 把解决问题的过程分为若干步
- 解决每一步时，都选择当前看起来 “最优的” 解法
- “希望” 这个局部最优是全局最优
贪心算法的特点：
- 根据 “贪心策略” 得到的结果可能是错误的
- 正确的 “贪心策略” 需要证明 “正确性”
- 不同题目的贪心策略不同，把我们遇到的贪心策略当 “经验” 来看就好
860. 柠檬水找零
题目链接：https://leetcode.cn/problems/lemonade-change/description/
优质解
思路：
- 问题分析（一杯柠檬水
5元）：找零问题可以分情况讨论5元 → 不用找，直接收下10元 → 收下，且找5元20元 → 收下，找10+5or5* 3
- 前两种情况是固定找法，只有
20的时候有选择，此时最优解是：优先找10+5（这就是本题的贪心策略）
代码：
classSolution{public:boollemonadeChange(vector<int>& bills){int arr[2];// 用来存放 5, 10 元的数量memset(arr,0,sizeof(arr));for(auto b: bills){if(b ==5) arr[0]++;elseif(b ==10){ arr[1]++; arr[0]--;}else{if(arr[1]>0)// 有 10 块的优先找10块的{ arr[1]--; arr[0]--;}else arr[0]-=3;}if(arr[0]<0)returnfalse;}returntrue;}};时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( 1 ) O(1) O(1)
证明
利用：交换论证法
原理：在不破坏最优解的 “最优性质” 的前提下，将最优解调整成贪心解，则代表这个贪心解是正确的
在这个问题中：只有遇到 20 元的时候才需要考虑策略：
- 贪心策略：有
10就优先10+5 - 最优策略：每次找
20：可能10+5或5+5+5（未知的）
最优策略中：当选择 5 + 5 + 5 的时候，如果有多的10块钱，此时可以用10元替换一个 5 + 5，（此时，最优解依然是最优解，即：依然可以保证能够找零成功，所以这个最优解可以调整为贪心解）
2208. 将数组和减半的最少操作次数
题目链接：https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/
个人解
思路：
- 每次选最大的来减小一半
- 意味着要排序，可以利用大根堆
屎山代码：
classSolution{public:inthalveArray(vector<int>& nums){ priority_queue<double> arr;double sum =0;for(auto x: nums){ sum += x; arr.push(x);}double cur = sum;int count =0;while(cur > sum /2){ count++;double max = arr.top(); arr.pop(); cur -= max /2; arr.push(max /2);}return count;}};时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度： O ( n ) O(n) O(n)
证明
依旧是：交换论证法
- 某次选择中，若：最优解中选择的数
x< 贪心中的y - 易知，此
x可用y替换
🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！
