当前位置：首页 > news >正文

C++贪心

news 2024/10/21 10:21:45

前言

C++算法与数据结构
打开打包代码的方法兼述单元测试

简介

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。贪心算法的正确性必须证明。常见的证明方法有五种：一，反证法。二，数学归纳法。三，决策包容性。四，扩展决策范围。五，临项交换。
在这里插入图片描述

决策包容性

如果存在最优解，增加某种条件限制后，仍然有最优解。故只需要考虑此种条件下的最优解。


【C++二分查找贪心决策包容性】826. 安排工作以达到最大收益	1708
【C++栈贪心决策包容性】3170. 删除星号以后字典序最小的字符串	1772
【C++二分查找贪心决策包容性】2576. 求出最多标记下标	1843
【C++二分查找贪心决策包容性】1488. 避免洪水泛滥	1973
【贪心决策包容性】2561. 重排水果	2221
【贪心决策包容性】757. 设置交集大小至少为	2348

临项交换（微扰）

证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差。经常用于以“排序”为贪心策略的证明。


【C++贪心临项交换】3219. 切蛋糕的最小总开销 II	1789
【贪心临项交换多指针】2931. 购买物品的最大开销	1822
【C++贪心临项交换】1665. 完成所有任务的最少初始能量	1900
【反悔堆优先队列临项交换决策包容性】630. 课程表 II	无

扩展决策范围（放缩法）

在思考贪心算法时，有时候不容易直接证明局部最优决策的正确性，此时可以往后多扩展一步，进而对当前的决策进行验证。扩展决策范围，即往后多看一步。

数学归纳法

【C++贪心数学归纳法】1054. 距离相等的条形码|1701

常见场景

中位数贪心：

pos[0…n-1]升序，记录了所有房间的位置，将邮筒放在何处，邮筒到各户的距离最短。
结论：如果n为偶数，则pos[n/2-1]到pos[n/2]之间；如果n为奇数，pos[n/2]。
下面用分组法和扩展决策范围来证明。
先假定n是偶数，分组法：pos[i]和pos[n-1-i]一组，任意一组最小距离为pos[n-1-i]-pos[i]，放在两者的中间，可以取最小值。
当n =2时，放在中间可以取最小值。
当 n=4,放置pos[1]和pos[2]中间可以取最小值。
$\cdots$ 放置到pos[n/2-1]和pos[n/2]可以取最小值。
当n为奇数时：邮箱放到pos[i]，各组取最小值，pos[i]为0。


【动态规划】【中位数贪心】【C++算法】1478. 安排邮筒	2190
【贪心算法】【中位贪心】2968.执行操作使频率分数最大	2444
【动态规划】【前缀和】【中位数贪心】2463. 最小移动总距离	2453
【对顶队列】【中位数贪心】【前缀和】3086. 拾起 K 个 1 需要的最少行动次数	2672

临项不同

n个字符，能否让相邻的字符不同。
性质一：出现次数最多的字符出现次数<= n/2。则限制队首不为指定字符也可以让相邻不相等。
性质二：n是奇数。出现最多的条形码出现n/2+1次。如果队首可以为此条形码，则可以让相邻不相等。
下面用数学归纳法来证明。
n为1成立：{a}
n为2成立：{a,b},{b,a}
n为3成立：{a,b,a} {a,b,c}{a,c,b}
从小到大证明n = 4 To $\infty$
n为偶数：
如果存在两个众数为n/2，将任意众数放到队首，余下的符合性质二。
否则，将任意众数放到队首，余下的符合性质一。
n为奇数：
如果众数为n/2+1，则只有一个众数。否则两个众数的数量为n+1，与n个数矛盾。
将众数放到队首，余下的符合性质一。
从上面的证明过程得知：如果有解，则将众数放到最前面，一定存在解。


【C++贪心数学归纳法】1054. 距离相等的条形码	1701
【C++二分查找贪心】2856. 删除数对后的最小数组长度	1749
【C++贪心】1953. 你可以工作的最大周数	1803

反悔贪心

发现无法贪心时，再更改。如：完成第i个任务需要task[i]块砖头或一个梯子。问最多能完成多少个任务，必须依次次完成任务。两种反悔贪心法：一，优先用砖头，砖头不够，就用梯子完成需要砖头最多的任务。二，优先用梯子，梯子不够。将需要砖头最少的梯子换成砖头。


【反悔贪心反悔堆】1642. 可以到达的最远建筑	1962
【大根堆】【反悔堆】【反悔贪心】【C++算法】871 最低加油次数	2074
【反悔堆反悔贪心】2813. 子序列最大优雅度	2582
【反悔贪心】【优先队列】3049. 标记所有下标的最早秒数 II	3111

未分类


【排序贪心】3107. 使数组中位数等于 K 的最少操作数	1604
【C++贪心】2522. 将字符串分割成值不超过 K 的子字符串	1604
【C++贪心】2567. 修改两个元素的最小分数	1608
【C++贪心】2086. 喂食仓鼠的最小食物桶数	1622
【C++贪心位运算】2571. 将整数减少到零需要的最少操作数	1649
【C++二分查找贪心】792. 匹配子序列的单词数	1695
【C++贪心】2498. 青蛙过河 II	1759
【C++ 贪心滑动窗口前后缀分解】948. 令牌放置	1762
【C++贪心】1262. 可被三整除的最大和	1762
【C++贪心】2712. 使所有字符相等的最小成本	1791
【C++贪心】1953. 你可以工作的最大周数	1803
【C++ 贪心双指针】2576. 求出最多标记下标	1843
【C++贪心】1775. 通过最少操作次数使数组的和相等	1850
【C++ 贪心】1616. 分割两个字符串得到回文串	1868
【C++贪心分治】1717. 删除子字符串的最大得分	1867
【贪心堆】3081. 替换字符串中的问号使分数最小	1904
【C++前缀和位运算贪心】2680. 最大或值	1912
【C++贪心 DFS】2673. 使二叉树所有路径值相等的最小代价	1917
【C++二分查找贪心】1552. 两球之间的磁力	1919
【C++贪心单调栈】1727. 重新排列后的最大子矩阵	1926
【C++前缀和动态规划贪心】813. 最大平均值和的分组	1936
【位运算贪心】2835. 使子序列的和等于目标的最少操作次数	2207
【C++前缀和数论贪心】2245. 转角路径的乘积中最多能有几个尾随零	2036
【C++二分查找贪心】1648. 销售价值减少的颜色球	2050
【字符串】【贪心】【树状数组】2193. 得到回文串的最少操作次数	2090
【贪心】【二分查找】【动态规划】1739放置盒子	2198
【解析几何】【多源路径】【贪心】1520 最多的不重叠子字符串	2362
【贪心】【回溯】【字符串】2014. 重复 K 次的最长子序列	2558
【贪心】【分类讨论】2499. 让数组不相等的最小总代价	2633
【贪心算法】2071:你可以安排的最多任务数目	2648
前缀和+单调双队列+贪心：2945:找到最大非递减数组的长度	2943
【贪心]【字符串】【分类讨论】420 强密码检验器	无难度分
【贪心堆优先队列】502. IPO	无难度分

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功