文章目录最小或最大贪心排序后使用贪心策略例题使两个数组和相等的最少操作单一序列配对满足要求的配对不超过元素的一半双序列匹配问题田忌赛马思想从左/从右贪心贪心大模拟例题区间贪心不相交区间区间选点的反面先选区间重叠的点每一个点表示每一个不相交区间区间分组贪心策略向左端点排序实时选择最小的右端点合并分组区间选点射气球问题区间覆盖实际问题-跳跃游戏最小或最大贪心排序后使用贪心策略-1262. 可被三整除的最大和 1762948. 令牌放置 17621775. 通过最少操作次数使数组的和相等 18502333. 最小差值平方和 2011 批量减少3645. 最优激活顺序得到的最大总和 20192141. 同时运行 N 台电脑的最长时间 2265可被三整除的最大和 1762贪心策略-排序求和然后根据余数结果排除最小的余数为1或者余数为2的结果。classSolution{public:intmaxSumDivThree(vectorintnums){unordered_mapint,vectorintmp;// [0,1,2]:vectorintintsum0;for(inti0;inums.size();i){mp[nums[i]%3].push_back(nums[i]);sumnums[i];}sort(mp[1].begin(),mp[1].end());sort(mp[2].begin(),mp[2].end());if(sum%31){inttmp1INT_MIN,tmp2INT_MIN;if(mp[1].size()){tmp1sum-mp[1][0];}if(mp[2].size()2){tmp2sum-mp[2][0]-mp[2][1];}if(max(tmp1,tmp2)!INT_MIN){returnmax(tmp1,tmp2);}elsereturn0;}if(sum%32){inttmp1INT_MIN,tmp2INT_MIN;if(mp[1].size()2){tmp1sum-mp[1][0]-mp[1][1];}if(mp[2].size()){tmp2sum-mp[2][0];}if(max(tmp1,tmp2)!INT_MIN){returnmax(tmp1,tmp2);}elsereturn0;}else{returnsum;}}};状态机解法分别设定三个状态机余数分别为012注意初始化和转移方程即可。classSolution{public:intmaxSumDivThree(vectorintnums){// 状态机DPintnnums.size();vectorvectorintdp(19,vectorint(n9,0));dp[0][0]0;dp[1][0]dp[2][0]-0x3f3f3f3f;dp[nums[0]%3][0]nums[0];// 3%30,dp[0][0]3for(inti1;in;i){inttnums[i]%3;if(t%30){dp[0][i]max(dp[0][i-1]nums[i],dp[0][i-1]);// dp[0]dp[1][i]max(dp[1][i-1]nums[i],dp[1][i-1]);// dp[1]dp[2][i]max(dp[2][i-1]nums[i],dp[2][i-1]);}elseif(t%31){dp[0][i]max(dp[2][i-1]nums[i],dp[0][i-1]);dp[1][i]max(dp[0][i-1]nums[i],dp[1][i-1]);dp[2][i]max(dp[1][i-1]nums[i],dp[2][i-1]);}else{// t%32dp[0][i]max(dp[1][i-1]nums[i],dp[0][i-1]);dp[1][i]max(dp[2][i-1]nums[i],dp[1][i-1]);dp[2][i]max(dp[0][i-1]nums[i],dp[2][i-1]);}}for(inti0;i3;i){for(intj0;jn;j){coutdp[i][j] ;}coutendl;}returndp[0][n-1]-0x3f3f3f3f?0:dp[0][n-1];}};例题使两个数组和相等的最少操作1775.通过最少操作次数使数组的和相等最小差值平方和思路基本一致但是是大模拟题目需要注意动态更新前面的数值。单一序列配对满足要求的配对不超过元素的一半§1.2 单序列配对同上从最小/最大的元素开始贪心。-2592. 最大化数组的伟大值 1569 田忌赛马2576. 求出最多标记下标 18432577.§1.3 双序列配对同上从最小/最大的元素开始贪心。-2037. 使每位学生都有座位的最少移动次数 13572578. 分发饼干 13812579. 运动员和训练师的最大匹配数 1381 同 455 题2580. 检查一个字符串是否可以打破另一个字符串 14362581. 优势洗牌 1648 田忌赛马2582. 安排工作以达到最大收益 17092583. 使数组相似的最少操作次数 20762584. 装包裹的最小浪费空间 22142585. 重排水果 22222586. 你可以安排的最多任务数目 26482587. 完成所有工作的最短时间 II会员题-2576. 求出最多标记下标 1843把数组划分两个部分小的元素一定要当不等式的左侧计为nums[i]右侧为nums[j]。双序列匹配问题田忌赛马思想870.优势洗牌826.安排工作以达到最大收益简单题有明显的单调性。-2583. 使数组相似的最少操作次数 2076首先任意数组一定可以通过若干次操作恒等这样的前提是两个数组的总和完全相等。关键之处需要理解给定两个数组需要的操作次数等于差值/4问题然后就演化为一个双序列配对的问题保证两个数组排序后一一对应的情况差值少。由于这题比较特殊奇数不能变成偶数因此还需要专门分奇和偶数来排序。从左/从右贪心贪心大模拟例题-3776. 使循环数组余额非负的最少移动次数 1740模拟循环数组注意计算循环后的坐标避免重复。-861. 翻转矩阵后的得分 1818HOT100题目先用行操作保证第一列最优在用列操作保证列得分最优-862. 使数组非递减的最少除法操作次数 1864题目本意就是求最小素因子或者1因此预处理使用欧拉筛得到每一个数的最小素因子然后反向遍历即可classSolution{public:intminOperations(vectorintnums){intnnums.size();if(n2)return0;autoflynorpexelnums;intmaxnum*max_element(nums.begin(),nums.end());vectorintminp(maxnum1,-1);vectorintprimes;// 欧拉筛for(inti2;imaxnum;i){if(minp[i]-1){primes.push_back(i);}for(intp:primes){if(1LL*i*pmaxnum)break;minp[i*p]p;if(i%p0)break;}}intans0;for(intin-2;i0;i--){if(nums[i]nums[i1]){// nums[i] 是质数或者 1无法变小if(minp[nums[i]]-1){return-1;}nums[i]minp[nums[i]];ans;if(nums[i]nums[i1]){return-1;}}}returnans;}};-864. 删列造序 II 1876865. 排布二进制网格的最少交换次数 1881转换为每一个行的后缀0数量然后遍历贪心866. 使二叉树所有路径值相等的最小代价 1917可以证明每一个左右子树的路径和一定要相等因此可以通过树上DP的形式来完成。867. 避免洪水泛滥 1974注意两种情况一是提前的晴天而是用掉了最晚的晴天导致早些的晴天无法使用使用二分查找来查找最早的晴天这就是贪心策略(注意查找完需要删除)。区间贪心题单区间贪心有如下经典问题不相交区间区间选点的反面先选区间重叠的点每一个点表示每一个不相交区间给定一些区间从中选出尽量多的两两互不相交的区间。interaseOverlapIntervals(vectorvectorintintervals){// 最大重叠子区间sort(intervals.begin(),intervals.end(),[](constvectorinta,constvectorintb){returna[0]b[0];});intrintervals[0][1],ans0;for(inti1;iintervals.size();i){if(intervals[i][0]r){ans;rintervals[i][1];}else{rmin(r,intervals[i][1]);}}returnintervals.size()-ans-1;}435. 无重叠区间 约 1700646. 最长数对链 同 435 题1520. 最多的不重叠子字符串 23633458. 选择 K 个互不重叠的特殊子字符串 同 1520 题变形每个区间有各自的分数从中选一些两两互不相交的区间最大化得分之和。详见 动态规划题单 的「§7.2 不相交区间」。区间分组贪心策略向左端点排序实时选择最小的右端点合并分组intminGroups(vectorvectorintintervals){sort(intervals.begin(),intervals.end(),[](constvectorinta,constvectorintb){returna[0]b[0];});priority_queuevectorint,vectorvectorint,cmpq;for(inti0;iintervals.size();i){if(q.size()){autovecq.top();if(vec[1]intervals[i][0]){q.pop();q.push({vec[0],intervals[i][1]});continue;}}q.push(intervals[i]);}returnq.size();}给定一些区间把这些区间分成最少的组使得每组内的区间互不相交。2406. 将区间分为最少组数 1713253. 会议室 II会员题区间选点射气球问题给定一些区间在数轴上放置最少的点使得每个区间都包含至少一个点。最少要放置多少个点intfindMinArrowShots(vectorvectorintpoints){// 最大重叠子区间sort(points.begin(),points.end(),[](constvectorinta,constvectorintb){returna[0]b[0];});intrpoints[0][1],ans0;for(inti1;ipoints.size();i){if(points[i][0]r){ans;rpoints[i][1];}else{rmin(r,points[i][1]);}}returnans1;}452. 用最少数量的箭引爆气球 约 1700757. 设置交集大小至少为2 23792589. 完成所有任务的最少时间 2381LCP 32. 批量处理任务区间覆盖实际问题-跳跃游戏给定一些区间从中选出尽量少的区间覆盖一条指定线段 [s,t]。确定区间的右端点然后一直遍历到该右端点更新区间新长度。在区间的有效长度内任意更新长度的操作都是合理的如果区间的长度已经达到要求直接停止。intjump(vectorintnums){if(nums.size()1)return0;inti1,rnums[0],ans0;while(inums.size()){if(rnums.size()-1){break;}intnewr-1;while(irinums.size()){newrmax(inums[i],newr);i;}ans;rnewr;}returnans1;}45. 跳跃游戏 II 约 17001024. 视频拼接 17461326. 灌溉花园的最少水龙头数目 1885 
长河君 · 2026/8/19 14:41:46 · 阅读 1.2k 贪心·刷题总结
文章目录最小或最大贪心排序后使用贪心策略例题使两个数组和相等的最少操作单一序列配对满足要求的配对不超过元素的一半双序列匹配问题田忌赛马思想从左/从右贪心贪心大模拟例题区间贪心不相交区间区间选点的反面先选区间重叠的点每一个点表示每一个不相交区间区间分组贪心策略向左端点排序实时选择最小的右端点合并分组区间选点射气球问题区间覆盖实际问题-跳跃游戏最小或最大贪心排序后使用贪心策略-1262. 可被三整除的最大和 1762948. 令牌放置 17621775. 通过最少操作次数使数组的和相等 18502333. 最小差值平方和 2011 批量减少3645. 最优激活顺序得到的最大总和 20192141. 同时运行 N 台电脑的最长时间 2265可被三整除的最大和 1762贪心策略-排序求和然后根据余数结果排除最小的余数为1或者余数为2的结果。classSolution{public:intmaxSumDivThree(vectorintnums){unordered_mapint,vectorintmp;// [0,1,2]:vectorintintsum0;for(inti0;inums.size();i){mp[nums[i]%3].push_back(nums[i]);sumnums[i];}sort(mp[1].begin(),mp[1].end());sort(mp[2].begin(),mp[2].end());if(sum%31){inttmp1INT_MIN,tmp2INT_MIN;if(mp[1].size()){tmp1sum-mp[1][0];}if(mp[2].size()2){tmp2sum-mp[2][0]-mp[2][1];}if(max(tmp1,tmp2)!INT_MIN){returnmax(tmp1,tmp2);}elsereturn0;}if(sum%32){inttmp1INT_MIN,tmp2INT_MIN;if(mp[1].size()2){tmp1sum-mp[1][0]-mp[1][1];}if(mp[2].size()){tmp2sum-mp[2][0];}if(max(tmp1,tmp2)!INT_MIN){returnmax(tmp1,tmp2);}elsereturn0;}else{returnsum;}}};状态机解法分别设定三个状态机余数分别为012注意初始化和转移方程即可。classSolution{public:intmaxSumDivThree(vectorintnums){// 状态机DPintnnums.size();vectorvectorintdp(19,vectorint(n9,0));dp[0][0]0;dp[1][0]dp[2][0]-0x3f3f3f3f;dp[nums[0]%3][0]nums[0];// 3%30,dp[0][0]3for(inti1;in;i){inttnums[i]%3;if(t%30){dp[0][i]max(dp[0][i-1]nums[i],dp[0][i-1]);// dp[0]dp[1][i]max(dp[1][i-1]nums[i],dp[1][i-1]);// dp[1]dp[2][i]max(dp[2][i-1]nums[i],dp[2][i-1]);}elseif(t%31){dp[0][i]max(dp[2][i-1]nums[i],dp[0][i-1]);dp[1][i]max(dp[0][i-1]nums[i],dp[1][i-1]);dp[2][i]max(dp[1][i-1]nums[i],dp[2][i-1]);}else{// t%32dp[0][i]max(dp[1][i-1]nums[i],dp[0][i-1]);dp[1][i]max(dp[2][i-1]nums[i],dp[1][i-1]);dp[2][i]max(dp[0][i-1]nums[i],dp[2][i-1]);}}for(inti0;i3;i){for(intj0;jn;j){coutdp[i][j] ;}coutendl;}returndp[0][n-1]-0x3f3f3f3f?0:dp[0][n-1];}};例题使两个数组和相等的最少操作1775.通过最少操作次数使数组的和相等最小差值平方和思路基本一致但是是大模拟题目需要注意动态更新前面的数值。单一序列配对满足要求的配对不超过元素的一半§1.2 单序列配对同上从最小/最大的元素开始贪心。-2592. 最大化数组的伟大值 1569 田忌赛马2576. 求出最多标记下标 18432577.§1.3 双序列配对同上从最小/最大的元素开始贪心。-2037. 使每位学生都有座位的最少移动次数 13572578. 分发饼干 13812579. 运动员和训练师的最大匹配数 1381 同 455 题2580. 检查一个字符串是否可以打破另一个字符串 14362581. 优势洗牌 1648 田忌赛马2582. 安排工作以达到最大收益 17092583. 使数组相似的最少操作次数 20762584. 装包裹的最小浪费空间 22142585. 重排水果 22222586. 你可以安排的最多任务数目 26482587. 完成所有工作的最短时间 II会员题-2576. 求出最多标记下标 1843把数组划分两个部分小的元素一定要当不等式的左侧计为nums[i]右侧为nums[j]。双序列匹配问题田忌赛马思想870.优势洗牌826.安排工作以达到最大收益简单题有明显的单调性。-2583. 使数组相似的最少操作次数 2076首先任意数组一定可以通过若干次操作恒等这样的前提是两个数组的总和完全相等。关键之处需要理解给定两个数组需要的操作次数等于差值/4问题然后就演化为一个双序列配对的问题保证两个数组排序后一一对应的情况差值少。由于这题比较特殊奇数不能变成偶数因此还需要专门分奇和偶数来排序。从左/从右贪心贪心大模拟例题-3776. 使循环数组余额非负的最少移动次数 1740模拟循环数组注意计算循环后的坐标避免重复。-861. 翻转矩阵后的得分 1818HOT100题目先用行操作保证第一列最优在用列操作保证列得分最优-862. 使数组非递减的最少除法操作次数 1864题目本意就是求最小素因子或者1因此预处理使用欧拉筛得到每一个数的最小素因子然后反向遍历即可classSolution{public:intminOperations(vectorintnums){intnnums.size();if(n2)return0;autoflynorpexelnums;intmaxnum*max_element(nums.begin(),nums.end());vectorintminp(maxnum1,-1);vectorintprimes;// 欧拉筛for(inti2;imaxnum;i){if(minp[i]-1){primes.push_back(i);}for(intp:primes){if(1LL*i*pmaxnum)break;minp[i*p]p;if(i%p0)break;}}intans0;for(intin-2;i0;i--){if(nums[i]nums[i1]){// nums[i] 是质数或者 1无法变小if(minp[nums[i]]-1){return-1;}nums[i]minp[nums[i]];ans;if(nums[i]nums[i1]){return-1;}}}returnans;}};-864. 删列造序 II 1876865. 排布二进制网格的最少交换次数 1881转换为每一个行的后缀0数量然后遍历贪心866. 使二叉树所有路径值相等的最小代价 1917可以证明每一个左右子树的路径和一定要相等因此可以通过树上DP的形式来完成。867. 避免洪水泛滥 1974注意两种情况一是提前的晴天而是用掉了最晚的晴天导致早些的晴天无法使用使用二分查找来查找最早的晴天这就是贪心策略(注意查找完需要删除)。区间贪心题单区间贪心有如下经典问题不相交区间区间选点的反面先选区间重叠的点每一个点表示每一个不相交区间给定一些区间从中选出尽量多的两两互不相交的区间。interaseOverlapIntervals(vectorvectorintintervals){// 最大重叠子区间sort(intervals.begin(),intervals.end(),[](constvectorinta,constvectorintb){returna[0]b[0];});intrintervals[0][1],ans0;for(inti1;iintervals.size();i){if(intervals[i][0]r){ans;rintervals[i][1];}else{rmin(r,intervals[i][1]);}}returnintervals.size()-ans-1;}435. 无重叠区间 约 1700646. 最长数对链 同 435 题1520. 最多的不重叠子字符串 23633458. 选择 K 个互不重叠的特殊子字符串 同 1520 题变形每个区间有各自的分数从中选一些两两互不相交的区间最大化得分之和。详见 动态规划题单 的「§7.2 不相交区间」。区间分组贪心策略向左端点排序实时选择最小的右端点合并分组intminGroups(vectorvectorintintervals){sort(intervals.begin(),intervals.end(),[](constvectorinta,constvectorintb){returna[0]b[0];});priority_queuevectorint,vectorvectorint,cmpq;for(inti0;iintervals.size();i){if(q.size()){autovecq.top();if(vec[1]intervals[i][0]){q.pop();q.push({vec[0],intervals[i][1]});continue;}}q.push(intervals[i]);}returnq.size();}给定一些区间把这些区间分成最少的组使得每组内的区间互不相交。2406. 将区间分为最少组数 1713253. 会议室 II会员题区间选点射气球问题给定一些区间在数轴上放置最少的点使得每个区间都包含至少一个点。最少要放置多少个点intfindMinArrowShots(vectorvectorintpoints){// 最大重叠子区间sort(points.begin(),points.end(),[](constvectorinta,constvectorintb){returna[0]b[0];});intrpoints[0][1],ans0;for(inti1;ipoints.size();i){if(points[i][0]r){ans;rpoints[i][1];}else{rmin(r,points[i][1]);}}returnans1;}452. 用最少数量的箭引爆气球 约 1700757. 设置交集大小至少为2 23792589. 完成所有任务的最少时间 2381LCP 32. 批量处理任务区间覆盖实际问题-跳跃游戏给定一些区间从中选出尽量少的区间覆盖一条指定线段 [s,t]。确定区间的右端点然后一直遍历到该右端点更新区间新长度。在区间的有效长度内任意更新长度的操作都是合理的如果区间的长度已经达到要求直接停止。intjump(vectorintnums){if(nums.size()1)return0;inti1,rnums[0],ans0;while(inums.size()){if(rnums.size()-1){break;}intnewr-1;while(irinums.size()){newrmax(inums[i],newr);i;}ans;rnewr;}returnans1;}45. 跳跃游戏 II 约 17001024. 视频拼接 17461326. 灌溉花园的最少水龙头数目 1885