3. 贪心思想(todo)
2021/12/19 23:49:43
本文主要是介绍3. 贪心思想(todo),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 1. 分配饼干
- 2. 不重叠区间个数
- 3. 投飞镖刺破气球
- 5. 买卖股票最大的收益
- 6. 买卖股票的最大收益 II
- 9. 修改一个数成为非递减数组
- 10. 子数组的最大和
- 11. 分隔字符串使同种字符出现在一起
leetcode 题解-贪心思想
保证每次操作都是局部最优的,并且最后得到的结果是全局最优的。
1. 分配饼干
Input: grid[1,3], size[1,2,4]
Output: 2
2. 不重叠区间个数
- Non-overlapping Intervals (Medium)
题目描述:计算让一组区间不重叠所需要移除的区间个数。
在每次选择中,区间的结尾最为重要,选择的区间结尾越小,留给后面的区间的空间越大,那么后面能够选择的区间个数也就越大。
按区间的结尾进行排序,每次选择结尾最小,并且和前一个区间不重叠的区间。
3. 投飞镖刺破气球
- Minimum Number of Arrows to Burst Balloons (Medium)
Input:
[[10,16], [2,8], [1,6], [7,12]]Output:
2
题目描述:气球在一个水平数轴上摆放,可以重叠,飞镖垂直投向坐标轴,使得路径上的气球都被刺破。求解最小的投飞镖次数使所有气球都被刺破。
也是计算不重叠的区间个数,不过和 Non-overlapping Intervals 的区别在于,[1, 2] 和 [2, 3] 在本题中算是重叠区间。
5. 买卖股票最大的收益
- Best Time to Buy and Sell Stock (Easy)
题目描述:一次股票交易包含买入和卖出,只进行一次交易,求最大收益。
只要记录前面的最小价格,将这个最小价格作为买入价格,然后将当前的价格作为售出价格,查看当前收益是不是最大收益。
6. 买卖股票的最大收益 II
- Best Time to Buy and Sell Stock II (Easy)
题目描述:可以进行多次交易,多次交易之间不能交叉进行,可以进行多次交易。
对于 [a, b, c, d],如果有 a <= b <= c <= d ,那么最大收益为 d - a。而 d - a = (d - c) + (c - b) + (b - a) ,因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] > 0,那么就把 prices[i] - prices[i-1] 添加到收益中。
9. 修改一个数成为非递减数组
题目描述:判断一个数组是否能只修改一个数就成为非递减数组。
在出现 nums[i] < nums[i - 1] 时,需要考虑的是应该修改数组的哪个数,使得本次修改能使 i 之前的数组成为非递减数组,并且 不影响后续的操作 。优先考虑令 nums[i - 1] = nums[i],因为如果修改 nums[i] = nums[i - 1] 的话,那么 nums[i] 这个数会变大,就有可能比 nums[i + 1] 大,从而影响了后续操作。还有一个比较特别的情况就是 nums[i] < nums[i - 2],修改 nums[i - 1] = nums[i] 不能使数组成为非递减数组,只能修改 nums[i] = nums[i - 1]。题目描述:判断一个数组是否能只修改一个数就成为非递减数组。
在出现 nums[i] < nums[i - 1] 时,需要考虑的是应该修改数组的哪个数,使得本次修改能使 i 之前的数组成为非递减数组,并且 不影响后续的操作 。优先考虑令 nums[i - 1] = nums[i],因为如果修改 nums[i] = nums[i - 1] 的话,那么 nums[i] 这个数会变大,就有可能比 nums[i + 1] 大,从而影响了后续操作。还有一个比较特别的情况就是 nums[i] < nums[i - 2],修改 nums[i - 1] = nums[i] 不能使数组成为非递减数组,只能修改 nums[i] = nums[i - 1]。
if (i - 2 >= 0 && nums[i - 2] > nums[i]) { nums[i] = nums[i - 1]; } else { nums[i - 1] = nums[i]; }
10. 子数组的最大和
11. 分隔字符串使同种字符出现在一起
这篇关于3. 贪心思想(todo)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?