建设项目环境影响登记表网站,博物馆网站做的最好的,帝国cms小说网站模板下载地址,东莞网站建设公司 h5Day27贪心算法基础贪心的本质是选择每一阶段的局部最优#xff0c;从而达到全局最优。刷题或者面试的时候#xff0c;手动模拟一下感觉可以局部最优推出整体最优#xff0c;而且想不到反例#xff0c;那么就试一试贪心。做题的时候#xff0c;只要想清楚 局部最优 是什么从而达到全局最优。刷题或者面试的时候手动模拟一下感觉可以局部最优推出整体最优而且想不到反例那么就试一试贪心。做题的时候只要想清楚 局部最优 是什么如果推导出全局最优其实就够了。贪心没有套路说白了就是常识性推导加上举反例。455.分发饼干力扣题目链接假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。思路贪心算法每一次都拿着一个小孩让这个小孩去吃尺寸最小的饼干这样能达到全局最优尽量能喂饱更多的小孩先把数组进行排序因为要有序用index来处理小孩i来遍历饼干因为对每个小孩饼干的尺寸要不断移动都从最小开始如果遍历到某个位置饼干能满足小孩那count同时这个小孩被满足了index最后返回count或者是每一次拿着一个饼干让这个饼干尽可能满足胃口大的小孩所以要遍历小孩找到符合要求的饼干位置减一代码class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);//先排序int count 0;//满足的胃口int index 0;//小孩的位置for (int i 0; i s.length index g.length; i){//饼干进行遍历因为要看哪个饼干能满足小孩if (s[i] g[index]){//找到了符合要求的count;index;//小孩位置自增}}return count;}
}class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count 0;int index s.length - 1;for (int i g.length - 1; i 0; i--){if (index 0 s[index] g[i]){count;index--;}}return count;}
}376. 摆动序列力扣题目链接如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为摆动序列。第一个差如果存在的话可能是正数或负数。少于两个元素的序列也是摆动序列。例如 [1,7,4,9,2,5] 是一个摆动序列因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。给定一个整数序列返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些也可以不删除元素来获得子序列剩下的元素保持其原始顺序。思路这个解法很巧妙先剪枝如果长度小于2直接return 1之后使用up和down进行记录从1开始遍历因为要和前一个元素进行比较如果比前一个大那up就是down 1如果比前一个小那down就是up 1最后返回两者较大值即可代码class Solution {public int wiggleMaxLength(int[] nums) {if (nums.length 2) return 1;int up 1;int down 1;for (int i 1; i nums.length; i) {if (nums[i] nums[i - 1]) down up 1;if (nums[i] nums[i - 1]) up down 1;}return Math.max(up,down);}
}53. 最大子序和力扣题目链接给定一个整数数组 nums 找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。思路先简单看一下暴力解法外层循环给出子数组起始位置内层循环不断遍历后面的元素并更新res时间复杂度O(n2)贪心算法贪心的点在于计算一个连续和如果遍历到某个元素加上这个元素让连续和变为负数了那我们就把连续和置为0从下一个元素开始重新计算连续和因为加上一个负数肯定会让结果变小代码class Solution {public int maxSubArray(int[] nums) {int res Integer.MIN_VALUE;int sum;for (int i 0; i nums.length; i){sum 0;for (int j i; j nums.length; j){sum nums[j];res Math.max(res,sum);}}return res;}
}class Solution {public int maxSubArray(int[] nums) {int res Integer.MIN_VALUE;int sum 0;for (int i 0; i nums.length; i) {sum nums[i];//加上这个位置的元素res Math.max(res,sum);//这句话要写在前面否则全是负数的情况会返回0不断更新resif (sum 0){//如果连续和变为负数了sum 0;//把连续和置为0继续遍历}}return res;//最后返回res}
}
