LeetCode算法训练-贪心算法 455.分发饼干 376. 摆动序列 53. 最大子序和
2024-10-21 04:08:48
欢迎关注个人公众号:爱喝可可牛奶
LeetCode算法训练-贪心算法 455.分发饼干 376. 摆动序列 53. 最大子序和
前置知识
贪心算法核心是找局部最优解,通过局部最优推导出全局最优
LeetCode 455. 分发饼干
分析
要求:把饼干分给孩子,并返回分了多少个孩子
局部最优:小饼干分给胃口小的
代码
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i = 0, j = 0;
int num = 0;
while(i < g.length && j < s.length){
if(s[j] >= g[i]){
num++;
j++;
i++;
}else{
j++;
}
}
return num;
}
}
LeetCode 376. 摆动序列
分析
返回 nums
中作为 摆动序列 的 最长子序列的长度
对于我们当前考虑的这个数,要么是作为山峰(即nums[i] > nums[i-1]),要么是作为山谷(即nums[i] < nums[i - 1])
代码
class Solution {
public int wiggleMaxLength(int[] nums) {
// 0 i 作为波峰的最大长度
// 1 i 作为波谷的最大长度
int dp[][] = new int[nums.length][2];
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i < nums.length; i++){
//i 自己可以成为波峰或者波谷
dp[i][0] = dp[i][1] = 1;
for (int j = 0; j < i; j++){
if (nums[j] > nums[i]){
// i 是波谷
dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
}
if (nums[j] < nums[i]){
// i 是波峰
dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
}
}
}
return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
}
}
LeetCode 53. 最大子数组和
分析
局部最优: 遍历到当前元素cur时,和为正数,继续遍历; 如果遍历到当前元素后和为负数,从后一个元素重新开始遍历
代码
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 1){
return nums[0];
}
int sum = Integer.MIN_VALUE;
int count = 0;
for (int i = 0; i < nums.length; i++){
count += nums[i];
sum = Math.max(sum, count); // 取区间累计的最大值(相当于不断确定最大子序终止位置)
if (count <= 0){
count = 0; // 相当于重置最大子序起始位置,因为遇到负数一定是拉低总和
}
}
return sum;
}
}
总结
贪心算法没有银弹,如果找出局部最优并可以推出全局最优,就是贪心,关键是如何去找局部最优
最新文章
- java certificate 工具 portecle.sourceforge.net
- 史上最详cxf-Springmvc-maven实现webservice教程(转)
- VTK初学一,a Mesh from vtkImageData—球冠
- mysql一个事务中有DDL语句的binlog情况
- Socket 之 同步以及异步通信
- AjaxPro使用说明
- [转]JavaScript 的同源策略
- unison实时双向数据同步
- xcode APP 打包以及提交apple审核详细流程(新版本更新提交审核)
- 201521123112《Java程序设计》第9周学习总结
- XBMC源代码分析 3:核心部分(core)-综述
- Node.js微服务实践(一)
- 2018 Multi-University Training Contest 3 - HDU Contest
- python tkinter Text
- vue开发中regeneratorRuntime is not defined
- Kafka 0.11客户端集群管理工具AdminClient
- kubectl命令使用
- spoj 1825 Free tour II
- SpringMVC之八:基于SpringMVC拦截器和注解实现controller中访问权限控制
- 看完MJ讲解的单例后的个人总结