贪心算法part01 算法
● 理论基础
● 455.分发饼干
● 376. 摆动序列
● 53. 最大子序和
1.leetcode455.分发饼干
https://leetcode.cn/problems/assign-cookies/description/
class Solution {
public int findContentChildren(int[] g, int[] s) {
//因为是尽可能满足多的孩子
Arrays.sort(g);
Arrays.sort(s);
//计数器
int count=0;
int startIndex=0;
for(int i=0;i<s.length;i++){//饼干
if(startIndex<=g.length-1&&g[startIndex]<=s[i]){//孩子
count++;
startIndex++;//孩子位置
}
//没有进入if,那就是孩子位置没有变,而饼干将要向后一个位置
}
return count;
}
}
2.leetcode376. 摆动序列
https://leetcode.cn/problems/wiggle-subsequence/description/文章来源:https://www.toymoban.com/news/detail-785235.html
class Solution {
public int wiggleMaxLength(int[] nums) {
//画图,上下坡
//如果数组长度是0个或者1个,那么直接返回数组长度
if(nums.length<=1){
return nums.length;
}
//当前差值
int curDiff=0;
//上一个差值
int preDiff=0;
//累加结果
int count=1;//最后一个已经包括
for(int i=1;i<nums.length;i++){//因为下标为1的元素衔接上一个和当前的差值
//得到当前差值
curDiff=nums[i]-nums[i-1];
//如果当前差值和上一个差值为一正一负的话
//等于0的情况表示初始时的preDiff
if((curDiff>0&&preDiff<=0)||(curDiff<0&&preDiff>=0)){
count++;
preDiff=curDiff;
}
}
return count;
}
}
3.leetcode53. 最大子序和
https://leetcode.cn/problems/maximum-subarray/description/文章来源地址https://www.toymoban.com/news/detail-785235.html
class Solution {
public int maxSubArray(int[] nums) {
//找出一个具有最大和的连续子数组
//连续
//最大,那就每次都是最大的
//用来保存结果,每次都是最大的
int result=Integer.MIN_VALUE;
//用来计数
int sum=0;
for(int i=0;i<nums.length;i++){
//进行累加
sum+=nums[i];
if(result<sum){
result=sum;
}
//当让整合为负数的时候,我们就舍弃掉重新出发
if(sum<0){
sum=0;
}
}
return result;
}
}
到了这里,关于贪心算法part01 算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!