LeetCode——贪心算法（Java）

简介

记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录的刷题路线。会附上一些个人的思路，如果有错误，可以在评论区提醒一下。

[简单] 455. 分发饼干

原题链接
贪心思路，优先把大的饼干分给胃口大的。

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(s);Arrays.sort(g);int ans = 0;int j = s.length - 1;for(int i = g.length - 1; i >= 0 && j >= 0; i--){if(s[j] >= g[i]){j--;ans++;}}return ans;}
}

[中等] 376. 摆动序列

原题链接
初次提交无法通过[0,1,1,2,2]这样的示例，没有判断出带平坡的单调递增，需要注意，只在result++的时候才去记录prediff的值，因为没有判断出result++的节点理论上是被删掉了，下一轮循环使用的还是同一个prediff
prediff初值设置为0是假设nums[0] 前面有一个跟他一样的节点。

class Solution {public int wiggleMaxLength(int[] nums) {int prediff = 0;int curdiff;int length = nums.length;if(length <= 1) return length;int result = 1;for(int i = 0; i < length - 1; i++){curdiff = nums[i + 1] - nums[i];if((prediff <= 0 && curdiff > 0) || (prediff >= 0 && curdiff < 0)) {result++;prediff = curdiff;}}return result;}
}

[中等] 53. 最大子数组和

原题链接

从左到右开始累加，如果[0 - i] 的累加<=0,说明这一段肯定不是结果的一部分，可以直接抛弃。

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(sum > result){result = sum;}if(sum <=0 ) sum = 0;}return result;}
}

[中等] 122. 买卖股票的最佳时机 II

原题链接

就按每天的差值来进行交易，差值为正就购入，算入总和。

class Solution {public int maxProfit(int[] prices) {int ans = 0;for(int i = 1; i < prices.length; i++){int count = prices[i] - prices[i - 1];if(count > 0) ans += count;}return ans;}
}

[中等] 55. 跳跃游戏

原题链接

不需要考虑具体跳到哪里，只要知道能跳的最大范围即可，比如nums = [3,2,1,0,4]中，从第一个位置开始跳，不管跳到 nums[1]/nums[2]/nums[3]，他们最多也都是够到下标为3，所以最后会是false。

class Solution {public boolean canJump(int[] nums) {int cover = 0;for(int i = 0; i <= cover ; i++) {cover = Integer.max(i + nums[i], cover);if(cover >= nums.length - 1) return true;}return false;}
}