【贪心算法】day1

📝前言说明：

• 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）这个贪心算法正确性的证明
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀ZEEKLOG主页 愚润泽

你可以点击下方链接，进行其他贪心算法题目的学习

也可以点击下面连接，学习其他算法

题单获取→ 【贪心算法】题单汇总

题目

• 贪心算法导论
• 860. 柠檬水找零
  • 优质解
  • 证明
• 2208. 将数组和减半的最少操作次数
  • 个人解
  • 证明

贪心算法导论

贪心策略的核心思想：局部最优 当做 全局最优

1. 把解决问题的过程分为若干步
2. 解决每一步时，都选择当前看起来 “最优的” 解法
3. “希望” 这个局部最优是全局最优

贪心算法的特点：

1. 根据 “贪心策略” 得到的结果可能是错误的
2. 正确的 “贪心策略” 需要证明 “正确性”
3. 不同题目的贪心策略不同，把我们遇到的贪心策略当 “经验” 来看就好

860. 柠檬水找零

题目链接：https://leetcode.cn/problems/lemonade-change/description/

优质解

思路：

• 问题分析（一杯柠檬水5元）：找零问题可以分情况讨论
  • 5 元 → 不用找，直接收下
  • 10 元 → 收下，且找 5元
  • 20 元 → 收下，找10 + 5 or 5 * 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替换

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！