贪心算法章节理论基础:
455.分发饼干
题目链接:https://leetcode.cn/problems/assign-cookies/
思路:
大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子,那么就应该优先满足胃口大的。
这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略,先将饼干数组和小孩数组排序。
然后从后向前遍历小孩数组,用大饼干优先满足胃口大的,并统计满足小孩数量。
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int cnt = 0;
int children = g.length;
int index = s.length - 1; // 饼干数组
for(int i=children-1;i>=0;i--){
if(index >= 0 && s[index] >= g[i]) // index >= 0 要加上去
{
index --;
cnt++;
}
}
return cnt;
}
}
376. 摆动序列
题目链接:https://leetcode.cn/problems/wiggle-subsequence/
思路:
摆动序列,先升高再下降,先下降再升高,都是可以的,没有限制死,这里需要注意一下。
然后,当数字相同的时候,是不满足摆动的定义的。
我们依次统计升降的次数就行了,这里res初始化为1,是因为我们默认把第一个数加进来,direction设为-1,也就是没有初始的升降限制。
class Solution {
public int wiggleMaxLength(int[] nums) {
// 摆动序列,可以升降,也可以降升
if(nums.length <= 1) return nums.length;
int direction = -1;
int res = 1;
for(int i=1; i< nums.length;i++){
// 没有变化
if(nums[i] == nums[i-1])
continue;
// 有变化,升高了
else if(nums[i] - nums[i-1] > 0)
{
// 如果上一次也是升高,就不要算进去
if(direction == 1)
continue;
direction = 1;
res += 1;
}
// 有变化,降低了
else{
if(direction == 0)
continue;
direction = 0;
res += 1;
}
}
return res;
}
}
时间复杂度: O(n)
空间复杂度: O(1)
53. 最大子序和
题目链接:https://leetcode.cn/problems/maximum-subarray/
思路:
如果 -2 1 在一起,计算起点的时候,一定是从 1 开始计算,因为负数只会拉低总和,这就是贪心贪的地方!
局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。
从代码角度上来讲:遍历 nums,从头开始用 count 累积,如果 count 一旦加上 nums[i]变为负数,那么就应该从 nums[i+1]开始从 0 累积 count 了,因为已经变为负数的 count,只会拖累总和。
class Solution {
public int maxSubArray(int[] nums) {
int result = Integer.MIN_VALUE;
int count = 0;
for(int i=0;i<nums.length;i++){
count += nums[i];
// 不断更新最大值
if(count > result){
result = count;
}
// 如果递加过程中,只要大于0,就保留下来。大于0的数累加下去肯定会越来越大
if(count < 0) count = 0;
}
return result;
}
}
时间复杂度: O(n)
空间复杂度: O(n)