模板搭建网站,百度信息流推广,自适应影视网站模板,项目网发布信息平台● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和
在本次的题目中#xff0c;我们使用了贪心算法来解决三个问题#xff1a;分发饼干、摆动序列、最大子序和。这三个问题都可以使用贪心算法来解决#xff0c;而且贪心算法的时间复杂度相对较低#xff0c;能够在较短的…● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和
在本次的题目中我们使用了贪心算法来解决三个问题分发饼干、摆动序列、最大子序和。这三个问题都可以使用贪心算法来解决而且贪心算法的时间复杂度相对较低能够在较短的时间内得出解决方案。
分发饼干
题目描述有一群孩子和一些饼干每个孩子有一个贪心因子g每个饼干有一个大小s。只有当一个孩子的贪心因子小于等于饼干的大小时这个孩子才能获得这个饼干。求最多能满足多少个孩子。
贪心思路首先将孩子的贪心因子g和饼干的大小s从小到大排序然后从贪心因子最小的孩子开始依次判断每个孩子是否能够获得一块饼干。如果可以获得则将饼干的大小s继续判断下一个孩子是否能够获得饼干。如果不能获得则继续寻找下一个大小更大的饼干直到找到一个能够满足当前孩子的饼干或者没有更大的饼干为止。
Java代码如下
public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int i 0, j 0;int count 0;while (i g.length j s.length) {if (g[i] s[j]) {count;i;j;} else {j;}}return count;
}摆动序列
题目描述给定一个整数序列你的任务是找到其中最长的摆动子序列的长度。摆动序列的定义如果连续元素之间的差的正负性交替出现则称这样的序列为摆动序列。
贪心思路从序列的第一个数开始判断当前数与下一个数之间的差的正负性。如果这两个数之间的差为正则说明下一个数应该比当前数大如果这两个数之间的差为负则说明下一个数应该比当前数小。如果这两个数之间的差为0则说明这两个数相等直接跳过。通过这样的方式每次找到一个摆动序列的峰值或者谷值最终就能得到最长的摆动子序列的长度。
Java代码如下
public int wiggleMaxLength(int[] nums) {if (nums.length 2) {return nums.length;}int preDiff 0;int curDiff 0;int count 1;for (int i 1; i nums.length; i) {curDiff nums[i] - nums[i - 1];if ((curDiff 0 preDiff 0) || (curDiff 0 preDiff 0)) {count;preDiff curDiff;}}return count;
}最大子序和
题目描述给定一个整数序列找到一个具有最大和的连续子序列至少包含一个数。
贪心思路从序列的第一个数开始依次将每个数加到当前的子序列中并记录当前子序列的最大值和当前子序列的和。如果当前子序列的和小于0则说明当前子序列已经不可能是最大的连续子序列了需要重新开始寻找从下一个数开始的子序列。通过这样的方式每次找到一个最大的连续子序列的和最终就能得到整个序列中的最大子序和。
Java代码如下
public int maxSubArray(int[] nums) {int maxSum nums[0];int curSum 0;for (int i 0; i nums.length; i) {curSum nums[i];if (curSum maxSum) {maxSum curSum;}if (curSum 0) {curSum 0;}}return maxSum;
}贪心算法理论知识总结
贪心算法是一种解决最优化问题的算法它是一种启发式算法通过每一步的最优选择来达到整体的最优解。贪心算法的具体实现方法就是在每一步选择中都采取当前状态下最优的选择从而希望得到全局最优解。
贪心算法的时间复杂度通常比较低因为它每次只考虑当前状态下的最优解不需要考虑全局的情况。但是贪心算法并不能保证得到全局最优解因为它每次都只考虑局部最优解可能会导致整体上的局部最优解并不是全局最优解。
因此在使用贪心算法时需要确定一个贪心策略即确定每一步的最优选择以保证最终得到的解是全局最优解。同时需要证明所采用的贪心策略是正确的即证明每一步的最优选择可以推导出全局最优解。
