3. 贪心思想(todo)
保证每次操作都是局部最优的,并且最后得到的结果是全局最优的。
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. 分隔字符串使同种字符出现在一起
最新文章
- NumberFormat usage
- PHP中冒号、endif、endwhile、endfor这些都是什么
- hdu2015
- iOS中的动画
- openssl的CRYPTO_set_locking_callback
- Java简单记录
- 全面理解java异常机制
- LINUX 笔记-cal 命令
- linkin大话设计模式--简单工厂
- C语言博客作业--函数嵌套调用
- Java开发笔记(八十九)缓存字节I/O流
- IoC容器的接口设计
- Linux编程 14 文件权限(用户列表passwd,用户控制shadow,useradd模板与useradd命令参数介绍)
- Python——Flask框架——程序的基本结构
- ***腾讯云直播(含微信小程序直播)研究资料汇总-原创
- MATLAB 笔记
- CSS背景横向平铺BUG,解决方法
- redis安装 卸载 启动 关闭
- 3 TFRecord样例程序实战
- synchronize 和volatile 实现共享变量在多线程中的可见性
热门文章
- STL set容器常用API
- JVM面试大总结
- [数学理论] NP问题解释
- 8. 字符串转整数 (atoi)
- Django之数据增删改查、Django请求生命周期流程图、Django路由层(路由匹配、转换器、正则匹配)、反向解析
- 常用的SQL命令:
- AJAX容易出错地方,错误处理
- npm 中设置环境NODE_ENV变量,判断失败打印process.env.NODE_ENV确实是";development";,但是判断process.env.NODE_ENV === ";development"; 是false
- Java 进阶P-8.3+P-8.4
- 【Android】Android 源码方式使用 opencv 库文件