> 文档中心 > 【4.20-周三】lc贪心问题:455&&376

【4.20-周三】lc贪心问题:455&&376

贪心455&&376

  • 455.分发饼干
    • 思路分析
    • 代码
  • 376.摆动序列
    • 思路分析
    • 代码
  • 总结

455.分发饼干

链接直达

【4.20-周三】lc贪心问题:455&&376

ps:我可以选择自己吃吗🤣

思路分析

一道十分简单的贪心题。

  • 核心就是尽可能多的分发饼干。为了达到这个目的,我们选取排序来确认小饼干分发给小胃的孩子,大

    饼干分发给大胃的孩子。

  • 所以将饼干和孩子排序,然后遍历饼干数组,当此时遍历的饼干满足的孩子,就把这个饼干给对应的孩子,然后再来为后面的孩子分发—>指向孩子的指针++

代码

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

javascript

js的foreach还是很方便的哈哈哈

/** * @param {number[]} g * @param {number[]} s * @return {number} */var findContentChildren = function(g, s) {    const sortFunc = function(a,b){ return a - b;    }    g.sort(sortFunc);    s.sort(sortFunc);    let i = 0;    s.forEach(n =>{ if(n >= g[i]){     i += 1; }    })    return i;};

376.摆动序列

链接直达

【4.20-周三】lc贪心问题:455&&376

思路分析

  • 摆动序列,也就是摆动数列,高中接触过的。这里的差值是正负横跳的。我们要删除不满足横跳规律的数值,求出最大的子数列。满足横跳规律实际上就是需要连续峰值

  • 个人思路:【未果】求出所有差值放到一个新数组中,对这个新数组进行遍历。采用双指针。这个思路受到以前做过的一道双指针滑动窗口题的影响。但是原数组的值是可以不定项删除的,所以差值数组也应该是变化的,想了很多办法模拟,还有一些特殊数列处理,代码很长,但是最后还是4个案例没过。感觉修补不回来😭

  • 于是看了题解。。。

  • 首先模拟两个数值,代表前一个差值left和当前的差值right。当满足两个差值right>0 && left <=0 || right =0的时候,就说明是满足正负交替出现的,也就是峰值连续,所以count++。然后left代替right,right重新计算,不断循环到最后。

  • right>0 && left <=0 || right =0这个条件怎么思考出来的。我们首先将count设置为1,这里的1表示的是,最长子序列最左边这个数,当满足right>0 && left <=0 || right =0才会++。其实不难想到,当right和left异号的时候就进入if语句,然后count++。但是为什么不直接写right*left<=0呢?比如【0,0,0】这个案例,如果我们写做right*left<=0,这里的count就会++,实际上我们的count应该就是1。最长子序列数就只有1个才对。

    然后是为什么需要考虑0的情况,而且还是left考虑为0而right不用考虑。当【0,0,1】这个案例出现的时候,0与0之间是0,0与1之间是1,这种情况我们算做是摆动的,所以0是需要考虑的

    那为什么0是在left上考虑?思考【0,0,0,2,3】这个案例,当right也为0的时候,我们需要往后查找,找到【0,2,3】的时候才能此时才算有峰值。如果将right==0考虑进去,那么在【0,0,0】阶段就会count++。

代码

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

总结

第一道贪心确实简单,第二道直接崩!裂开了。刚开始做,没什么体会😵只感觉好难

【4.20-周三】lc贪心问题:455&&376