C++贪心
前言
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 | 无难度分 |
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。