【4.20-周三】lc贪心问题:455&&376
贪心455&&376
- 455.分发饼干
-
- 思路分析
- 代码
- 376.摆动序列
-
- 思路分析
- 代码
- 总结
455.分发饼干
链接直达
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个案例没过。感觉修补不回来😭
-
于是看了题解。。。
-
首先模拟两个数值,代表前一个差值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; }}
总结
第一道贪心确实简单,第二道直接崩!裂开了。刚开始做,没什么体会😵只感觉好难