455. 分发饼干
public int findContentChildren(int[] g, int[] s) {
if (s == null || s.length == 0) {
return 0;
}
// 1 <= g.length <= 3 * 104
// 0 <= s.length <= 3 * 104
Arrays.sort(g);
Arrays.sort(s);
// 优先满足大胃口的孩子
int length = s.length - 1;
int num = 0;
for (int i = g.length - 1; i >= 0; i--) {
if (length < 0) {
break;
}
if (s[length] >= g[i]) { // 饼干分量大于孩子胃口
num++;
length--;
}
}
return num;
}
贪心算法的核心思想就是，局部最优推出全局最优。
优先大饼干满足大胃口，或者小饼干满足小胃口，都可以完成目标。
376. 摆动序列
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length <= 1) {
return 1;
}
int preDiff = 0;
int curDiff = 0;
int result = 1; // 因为默认最后面是一个峰值
for (int i = 0; i < nums.length - 1; i++) {
curDiff = nums[i + 1] - nums[i];
if ((preDiff >= 0 && curDiff < 0) || (preDiff <= 0 && curDiff > 0)) {
result++;
preDiff = curDiff; // 在摆动的时候才计算
}
}
return result;
}
}
这是一道计算差值，得到所有的波峰和波谷。
该题考虑全面挺难的，开始按照回溯的想法写了一套，超时了。
先思考一下如何计算波峰波谷？
preDiff = nums[i] - nums[i - 1] // 前一个差值
curDiff = nums[i + 1] - nums[i] // 后一个差值
我们在做题中并不用去计算前一个差值，每次只计算后一个，等到进行下一步，再将后一个差值赋给前一个即可。
按照这个逻辑，当 i = 0 的时候，前一个差值是多少呢？
我们将其视为两个相等元素的差值，即0，那么后一个元素不为0时，视为峰顶或者峰谷，那么就有
if ((preDiff >= 0 && curDiff < 0) || (preDiff <= 0 && curDiff > 0)) {
result++;
}
那么，假设有三个元素，全是2，那么有几个摆动呢，1个
但是按照上述的写法，最终结果只会是0，我们始终将最后一个元素视为波峰，result默认等于1.
难点来了: preDiff = curDiff; // 在摆动的时候才计算
这个地方是最难考虑到的，在摆动的时候才进行赋值，没有进行摆动的话就不要进行赋值。即在上坡中出现了平坡的情况
53. 最大子数组和
/**
* 1 <= nums.length <= 105
* -104 <= nums[i] <= 104
* 局部最优，当计算的和为负数的时候，起始位置开始重新调整。因为负数只会拖累后面的值
* <p>
* 遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，
* 那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。
*
* @param nums
* @return
*/
public int maxSubArray(int[] nums) {
// 求最大子数组，
int maxValue = Integer.MIN_VALUE;
int count = 0;
for (int i = 0; i < nums.length; i++) {
count += nums[i];
if (count > maxValue) {
maxValue = count;
}
if (count <= 0) count = 0; // 重置起始位置
}
return maxValue;
}
122. 买卖股票的最佳时机 II
/**
* 低价买入，高价卖出
* <p>
* 1 <= prices.length <= 3 * 104
* 0 <= prices[i] <= 104
*
* @param prices
* @return
*/
public int maxProfit(int[] prices) {
int count = 0;
int prePrice = -1;
for (int i = 0; i < prices.length - 1; i++) {
// prices[i + 1] - prices[i] > 0 上升
// prices[i + 1] - prices[i] < 0 下降
if (prices[i + 1] - prices[i] < 0) { // 降价之前就要进行卖出,转折的时候才改变
if (prePrice != -1) { // 买了股票要进行卖出
count += prices[i] - prePrice;
prePrice = -1; // 重置
}
} else if (prices[i + 1] - prices[i] > 0) { // 价格即将升高了，也是转折的时候
if (prePrice == -1) { // 没有买股票
prePrice = prices[i];
}
}
}
if (prePrice != -1) {
count += prices[prices.length - 1] - prePrice;
}
// 如果prices =1，count=0.
return count;
}
public int maxProfit2(int[] prices) {
int count = 0;
for (int i = 1; i < prices.length; i++) {
count += Math.max(prices[i] - prices[i - 1], 0);
}
return count;
}
第一种方式整体去看，就显得过于复杂了，在即将上升的时候买入，在即将下跌的时候卖出。
第二种方式将其拆分开来，只关注于每天的收益。如果当天减去昨天大于0，就加上，小于0，就不加
55. 跳跃游戏
public boolean canJump(int[] nums) {
// 当只有拥有0才有可能跳不到最后一格
// 两个小格的距离等于i - (i - 1)
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
continue;
}
boolean jumpFlag = true;
for (int j = i - 1; j >= 0; j--) {
if (nums[j] > i - j || (nums[j] == i -j && i == nums.length -1)) {
jumpFlag = false;
break;
}
}
if (jumpFlag && i != nums.length -1) {
return false;
}
}
return true;
}
public boolean canJump2(int[] nums) {
if (nums.length == 1) {
return true;
}
int coverValue = 0;
for (int i = 0; i <= coverValue; i++) {
coverValue = Math.max(coverValue, i + nums[i]);
if (coverValue >= nums.length - 1) {
return true;
}
}
return false;
}
要注意的细节特别多，要分析0的位置可能性
只有一个元素[0],[1]
有多个元素[0,1],[1,0],[2,0],[2,0,0]
另一个题解思路：
跳跃范围能不能覆盖到最后一个元素。
每次都记录最大的跳跃范围，当最大跳跃范围能够覆盖终点，那么就可以完成。
