国外网站做淘宝客,创造一个网页,网站建设开场白,深圳网站建设公司联系【贪心算法】Leetcode 455 分发饼干 376. 摆动序列【规律很多】53. 最大子数组和 455 分发饼干局部最优推全局最优#xff1a;尽量用大饼干去满足大胃口的小朋友 376. 摆动序列【规律很多】思想#xff1a;注意考虑一个坡度留首尾两个点、平坡、首尾 53. 最大子数组和【好思想… 【贪心算法】Leetcode 455 分发饼干 376. 摆动序列【规律很多】53. 最大子数组和 455 分发饼干局部最优推全局最优尽量用大饼干去满足大胃口的小朋友 376. 摆动序列【规律很多】思想注意考虑一个坡度留首尾两个点、平坡、首尾 53. 最大子数组和【好思想】思想遍历nums当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和” 455 分发饼干 ---------------题目链接-------------------
局部最优推全局最优尽量用大饼干去满足大胃口的小朋友
class Solution {public int findContentChildren(int[] g, int[] s) {// 贪心// 局部最优推全局最优尽量用大饼干去满足大胃口的小朋友if(s.length 0) return 0;int result 0;Arrays.sort(g);Arrays.sort(s);// 遍历小孩胃口g[i]int start s.length - 1;for(int i g.length-1; i 0; i--){if(start 0 g[i] s[start]){result;start--;}}return result;}
} 时间复杂度
对两个数组进行排序的时间复杂度为 O(n log n)其中 n 分别为小孩胃口数组 g 和饼干数组 s 的长度。 在最坏情况下遍历两个数组的时间复杂度为 O(n)其中 n 是小孩胃口数组 g 的长度。 因此总的时间复杂度为 O(n log n)。
空间复杂度
除了输入数组 g 和 s 外额外使用了常量空间进行迭代和计算。 因此总的空间复杂度为 O(1)。 376. 摆动序列【规律很多】 一正一负 找到一个峰值(pre0 cur0) || (pre0 cur0)。result遇到波动点就更新pre的值为cur 设定开头pre 0即原本是2-5模拟为2-2-5 这样可以保证计算到开头的节点也算波动点。 设定开头cur 0 但是随后循环中就赋值了 cur nums[i1] - nums[i] 思想注意考虑一个坡度留首尾两个点、平坡、首尾
class Solution {public int wiggleMaxLength(int[] nums) {
// 贪心 一个坡度上只留首位两个点
// 考虑平坡的时候// 考虑单调有平坡 : 左右留一个就行 pre0 cur0 || pre0 cur0// 考虑上下中间有平坡 只需要在 坡度摆动变化的时候更新 pre 就行这样 pre 在 单调区间有平坡的时候 就不会发生变化造成我们的误判
// 考虑首尾元素 首尾元素都要计算坡度 尾部直接result本身就为1首部假定开头pre0int result 1;int pre 0; // 前一段默认先为0 后面遇到波动点的时候赋值为curint cur 0;for(int i 0; i nums.length-1; i){cur nums[i1] - nums[i]; // 后一段if((pre0 cur0) || (pre0 cur0)){ // 一正一负就找到一个峰值result;pre cur; // 即出现波动点才给pre赋值为cur就可以避免单调中平坡的影响} }return result;}
}53. 最大子数组和【好思想】
题目链接
思想遍历nums当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和” 思想 如果一部分加和为负数那么后面再加一个无论什么元素都相当于是减那么就没必要了 那么就遍历nums遇到和为负数就重新开始计算加和 没遇到的时候如果加和结果大于result就给result赋值 最后返回result 注意这里用了int result Integer.MIN_VALUE; 保证了若数组都为负数result记录的就是最大的负数。 class Solution {public int maxSubArray(int[] nums) {// 贪心算法// 如果一部分加和为负数那么后面再加一个无论什么元素都相当于是减那么就没必要了// 那么就遍历nums遇到和为负数就重新开始计算加和没遇到的时候如果加和结果大于result就给result赋值// 最后返回resultint result Integer.MIN_VALUE; // 这个很重要 可以保证如果全为负数的时候可以正常输出int sum 0;for(int i 0; i nums.length; i){sum sumnums[i];if(sum result) { result sum;}if(sum 0){ // 如果加和小于零那就重新开始 因为后面再加没必要了sum 0;} }return result; // 最后返回的result就是最大的}
}
