贪心算法理论
- 贪心算法分阶段工作
- 在每一个阶段，可以认为所作决定是好的，而不考虑将来的后果
- 这意味着选择的是某个局部最优，这种“眼下能够拿到的就拿”的策略是这类算法的名称的来源
- 当算法终止的时候，我们希望局部最优等于全局最优。如果是这样的话，那么算法就算正确
- 贪心算法没有什么套路
455.分发饼干
题目链接：力扣
思路
这里有两种思路：
1、优先考虑胃口：从大到小一次遍历胃口，先满足胃口大的
想象一下，你坐在一个椅子上，有的饼干为【1，3，5，9】，然后孩子的胃口为【1，2，7，10】.孩子们按照胃口从大到小的顺序来拿饼干，为了满足更多的小孩，就不要造成饼干尺寸的浪费，每个孩子来了你都给最大的
10 来了 没有
7 来了 给9
2 来了 给5
1 来了 给3
2、优先考虑饼干：孩子按照胃口从小到大来，给饼干也从小到大，给满足胃口即可，打发一个是一个
拿出1 1可以
拿出3 2可以
拿出5 7不可以
拿出9 7可以
分发饼干
优先考虑胃口
class Solution { public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); // 饼干指针 int sIndex = s.length - 1; // 胃口满足了的孩子的数量 int count = 0; // 递减饼干 for (int gIndex = g.length - 1; gIndex >= 0; gIndex--) { if (sIndex >= 0 && s[sIndex] >= g[gIndex]) { sIndex--; count++; } } return count; } }
优先考虑饼干
class Solution { public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); int gIndex = 0; // 胃口满足了的孩子的数量 int count = 0; for (int sIndex = 0; sIndex < s.length; sIndex++) { if (gIndex < g.length && s[sIndex] >= g[gIndex]) { count++; gIndex++; } } return count; } }
376. 摆动序列
题目链接：力扣
思路
删是不可能删的，核心思想一句话：记录满足峰值的的数字数量
局部最优：满足峰值的，当一个值满足 左小右大 或者 左大右小 的时候进行记录
全局最优：所有满足峰值情况的数字长度，就是摆动序列的数量，其他不符合要求的并没有记录
对这里的条件还不是很理解
摆动序列
class Solution { public int wiggleMaxLength(int[] nums) { if (nums.length <= 1) { return nums.length; } // 目前一对数字的差值 int curDiff = 0; // 前一对数字的差值 int preDiff = 0; // 符合要求的数量 int result = 1; for (int i = 0; i + 1 < nums.length; i++) { // 计算当前一对数字的差值 curDiff = nums[i + 1] - nums[i]; // 出现峰值的数字 if ((curDiff > 0 && preDiff <= 0)||(preDiff >= 0 && curDiff < 0)) { result++; preDiff = curDiff; } } return result; } }
在LeetCode上看到一个很绝的写法，特别妙，变相取峰值
class Solution { public int wiggleMaxLength(int[] nums) { int n = nums.length; if (n < 2) { return n; } int up = 1; int down = 1; for (int i = 1; i < n; i++) { if (nums[i] > nums[i - 1]) { up = down + 1; } if (nums[i] < nums[i - 1]) { down = up + 1; } } return Math.max(up, down); } }
53. 最大子序和
题目链接：力扣
思路
拿到题是真的没思路，能想到的最简单的就是使用回溯，但是会超出市场，应该使用其他方法
然后看了一下题解，真的想的太复杂了，使用了暴力解法，但是超出时长了
所以只好使用贪心算法，贪心算法的贪在于：只要当前和出现了负数，就会从0开始计数，因为负数只会降低“连续和”
最大子序和
暴力解法
超出时间限制 不可用
class Solution { public int maxSubArray(int[] nums) { int result = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = i; j < nums.length; j++) { sum += nums[j]; if (sum > result) { result = sum; } } } return result; } }
贪心算法
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; } if (count < 0) { count = 0; } } return result; } }
