455.分发饼干
/*** @param {number[]} g* @param {number[]} s* @return {number}*/
var findContentChildren = function(g, s) {let a=0let b=0let count=0g.sort((a,b)=>a-b)s.sort((a,b)=>a-b)while(a<=g.length&&b<s.length){if(s[b]>=g[a]){count++b++a++}else{b++}}return count
};
第一想法
两个数组排序排序,双指针
376. 摆动序列
var wiggleMaxLength = function (nums) {let count = 0;let i = 1;while (nums[i] === nums[i - 1]) {i++;}let r = nums[i] - nums[i - 1] > 0 ? -1 : 1; //可能一开始是-也可能是+while (i <= nums.length) { //[3,3,3,2,5]避免这种while (nums[i] === nums[i - 1]) {i++;}if ((nums[i] - nums[i - 1]) * r < 0) { //判断是否不一样r = nums[i] - nums[i - 1];count++;i++;} else i++;}return count + 1;};
第一想法
如代码所示,可以不删除,i++就是了
53. 最大子数组和
/*** @param {number[]} nums* @return {number}*/var maxSubArray = function (nums) {let l = 0;let reslut = -10000000;let suml = 0;let flag = 0;while (l < nums.length) {suml += nums[l];if (reslut < suml) reslut = suml;if (suml < 0) suml = 0;l++;}return reslut;};
第一想法
滑动,但不行
思想
一路加上,小于0的都按0来处理,l++
if (reslut < suml) reslut = suml;
if (suml < 0) suml = 0;
这两个的顺序注意
计算起点的时候,一定是从 1 开始计算,因为负数只会拉低总和,这就是贪心贪的地方!
局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。