贪心算法
分发饼干
题目描述
有两个数组，一个代表小孩，一个代表饼干，第$i$个小孩的值是饥饿度，第$i$个饼干是饱和度，请问，饼干最多能让多少小孩吃饱。
解题思路
小饼干先喂饱小胃口。下面的代码中利用遍历cookie来遍历胃口数组，并没有再使用一个for循环，而是采用自加的方式，这也是常用的技巧。
public static int findContentChildren(int[]cookies, int[]children) {
Arrays.sort(cookies);
Arrays.sort(children);
int child = 0;
int cookie = 0;
while (child < children.length && cookie < cookies.length) {
if (children[child] <= cookies[cookie++])
child++;
}
return child;
}
|
摆动序列
题目描述
给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
解题思路
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动序列的长度，所以只需要统计数组的峰值数量就可以了。
public static int wiggleMaxLength(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
int result = 1;
int pre = 0;
int cur = 0;
for (int i = 1; i < nums.length; i++) {
cur = nums[i] - nums[i-1];
if (cur > 0 && pre <= 0 || cur < 0 && pre >= 0) {
result++;
pre = cur;
}
}
return result;
}
|
最大子序和
题目描述
给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
解题思路
局部最优：当前连续和为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素的连续和只会越来越小。
全局最优：选取最大“连续和”。
public static int Maximum_Suborder_Sum(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int count = 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
count += nums[i];
max = Math.max(max, count);
if (count < 0){
count = 0;
}
}
return 0;
}
|
买卖股票的最佳时机II
题目描述
给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
解题思路
其实只需要收集每天的正利润就可以了，收集正利润的区间，就是股票买卖的区间，而只需要关注最终利润，不需要记录区间。
局部最优：收集每天的正利润，全局最优：求得最大利润。
public static int maxProfit(int[] prices) {
int max = 0;
int flag = 0;
int cur = 0;
for (int i = 1; i < prices.length; i++) {
cur = prices[i] - prices[i-1];
if (cur > 0) {
max += cur;
flag = 1;
}
if (cur < 0 && flag == 1) {
flag = 0;
}
}
return max;
}
|
