怎么做网站静态布局,网站建设案例多少钱,什么软件可以免费引流,港闸网站建设代码随想录 贪心的本质是选择每一阶段的局部最优#xff0c;从而达到全局最优。 文章目录 455. 分发饼干376. 摆动序列53. 最大子数组和122. 买卖股票的最佳时机 II55. 跳跃游戏45. 跳跃游戏 II1005. K 次取反后最大化的数组和134. 加油站135. 分发糖果#xff08;困难#…代码随想录 贪心的本质是选择每一阶段的局部最优从而达到全局最优。 文章目录 455. 分发饼干376. 摆动序列53. 最大子数组和122. 买卖股票的最佳时机 II55. 跳跃游戏45. 跳跃游戏 II1005. K 次取反后最大化的数组和134. 加油站135. 分发糖果困难860. 柠檬水找零406.根据身高重建队列452. 用最少数量的箭引爆气球435. 无重叠区间763.划分字母区间56. 合并区间738.单调递增的数字968.监控二叉树 455. 分发饼干
https://leetcode.cn/problems/assign-cookies/description/
大饼干可以满足大孩子也可以满足小孩子在这里显然是满足大孩子最划算。因此饼干从大到小如果饼干可以满足该孩子ans否则尝试是否可以满足小孩子。
注意跳出循环的条件当i0||j0
var findContentChildren function (g, s) {g.sort((a, b) (a - b))s.sort((a, b) (a - b))let ans 0;for (let i g.length - 1, j s.length - 1; i 0, j 0;) {// g[i] 人 s[j]饼干if (s[j] g[i]) {ans;i--, j--;} else {i--;}if (i 0 || j 0) break;}return ans;
};376. 摆动序列
376. 摆动序列
想要得到最长的摆动数组需要保留一个上/下坡的头和尾如
1257521这里1257都是上坡但17的上坡比其他的好因为7可以与后面组成更好的下坡——若是17则后面想要下坡7即可若12后面想要下坡则需要2条件比7要小。反之亦然。
但是选择17还是12本质都是上坡且长度都为2。因此我们可以把问题简化为数组有多少个上下坡的变化。
上面的样例就是一上一下不管怎么选摆动数组都是3.
我们用一个flag来记录前面是上坡还是下坡前面是上坡且当前数组是下坡则ans反之亦然。
注意要判断平坡且从第一个上/下坡之后开始flag值就记录第一个上/下坡。
var wiggleMaxLength function(nums) {// flag表示是上行1还是下行0-1表示一直平坡let ans1,flag-1;// 要找到第一次上行或下行let index1;for(;indexnums.length;index){if(nums[index]nums[index-1]) continue;if(nums[index]nums[index-1]) {flag1;ans2;break;}else{flag0;ans2;break;}}for(let iindex1;inums.length;i){// 上行if(nums[i]nums[i-1]){if(!flag){ans;flag1;}}// 下行else if(nums[i]nums[i-1]){if(flag){ans;flag0;}}}return ans;
};53. 最大子数组和
53. 最大子数组和
分为两种情况数组全负和数组非全负。
数组全负则选元素最大的那一个。 数组非全负则一直累加并存最大值若出现cnt0则令cnt0相当于前面部分都不选。
var maxSubArray function (nums) {let ans -10001;// 数组全为负数let flag 0;nums.forEach(item {if (item 0) {flag 1; return;}})if (!flag) {nums.forEach(item {ans Math.max(ans, item);})return ans;}let cnt 0;// 贪心如果一块连续部分是负数则舍去nums.forEach(item {cnt item;if (item 0) ans Math.max(ans, cnt);else {if (cnt 0) cnt 0;}})return ans;
};122. 买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II
有prices数组1,2,3,5,8
最低买入最高卖出肯定是答案即8-17
注意8-12-13-25-38-5。即前缀差中正值的和。
若数组为2,0,1,4前缀差为-2,1,3说明要在0时买入在4时卖出。
var maxProfit function (prices) {// 前缀差 差值为正表示利润let ans 0;for (let i 1; i prices.length; i) {let temp prices[i] - prices[i - 1]if (temp 0) ans temp;}return ans;
};55. 跳跃游戏
55. 跳跃游戏
var canJump function (nums) {// cover表示可以覆盖的范围也就是下标let cover 0;if (nums.length 1) return true;for (let i 0; i cover; i) {cover Math.max(cover, i nums[i]);if (cover nums.length - 1) return true;}return false;
};45. 跳跃游戏 II
45. 跳跃游戏 II
var jump function (nums) {if (nums.length 1) return 0;// ans步数,next本次可以到达的最大范围,max下一次可以到达的最大范围let ans 0, next 0, max 0;for (let i 0; i nums.length; i) {max Math.max(max, i nums[i]);// 当前已经达到本次可以达到的最大范围,到下一范围需要一步if (i next) {ans;next max;if (max nums.length - 1) break;}}return ans;
};1005. K 次取反后最大化的数组和
1005. K 次取反后最大化的数组和
var largestSumAfterKNegations function (nums, k) {// k是偶数可以相当于不变let f [], z []nums.forEach(item {if (item 0) f.push(item);else z.push(item);})f.sort((a, b) (a - b));z.sort((a, b) (a - b));if (k f.length) {k - f.length;f f.map(item {return -item;})z.push(...f);f []} else {for (let i 0; i k; i) {let temp -f[i];z.push(temp);}f f.slice(k);k 0;}f.sort((a, b) (a - b));z.sort((a, b) (a - b));if (k k % 2) {// k是奇数z[0] -z[0];}let ans 0;if (f.length) {ans f.reduce((pre, val) {return pre val;})}if (z.length) {ans z.reduce((pre, val) {return pre val;})}return ans;
};134. 加油站
134. 加油站
n是1e5暴力双层循环会超出时间限制。
获得数组arrgas-costarr[i]表示离开i地点剩余的油。 遍历arr计算区间和但凡出现区间和0说明不能从这个区间的开头开始走没油了可能从此区间的下一个地方j开始走。于是从j开始计算区间和。维护这个j值是可能的答案。
计算arr的和若arr的和0说明存在一个地方开始走能顺时针跑完。由题知这个答案是唯一的。因此就是上面维护的j值。
若arr0说明不存在答案。
var canCompleteCircuit function (gas, cost) {// 遍历 找gas-cost的区间和0 答案就是此区间的下一个let curSum 0, allSum 0, ans 0;for (let i 0; i gas.length; i) {let temp gas[i] - cost[i];curSum tempallSum temp// 此区间和为负不能从这个区间和的头开始if (curSum 0) {curSum 0;ans i 1;//从此区间的下一个下标开始尝试}}if (allSum 0) return -1;return ans;
};135. 分发糖果困难
135. 分发糖果
思路这个讲得好
省流从左到右遍历一次从右到左遍历一次。
var candy function (ratings) {let arr new Array(ratings.length).fill(1)// 右边大于左边即从左到右:右边大的糖果1for (let i 1; i ratings.length; i) {if (ratings[i] ratings[i - 1]) {arr[i] arr[i - 1] 1;}}// 左边大于右边即从右到左右边最小for (let i ratings.length - 1; i 0; i--) {if (ratings[i - 1] ratings[i]) {arr[i - 1] Math.max(arr[i - 1], arr[i] 1);}}let ans arr.reduce((pre, val) {return pre val;})return ans;
};860. 柠檬水找零
860. 柠檬水找零
forEach中的return是跳出循环而不是函数的return。
var lemonadeChange function (bills) {let cnt5 0, cnt10 0;let flag true;bills.forEach(item {console.log(item, cnt5, cnt10)if (item 5) {cnt5;} else if (item 10) {cnt10;if (cnt5 0) cnt5--;else {flag false; return;//这里的return是跳出bills的循环 而不是函数的return}} else if (item 20) {if (cnt5 0 cnt10 0) {cnt5--; cnt10--;} else if (cnt5 3) {cnt5 - 3;} else {flag false; return;}}})return flag;
};406.根据身高重建队列
406.根据身高重建队列
想要队列queue中的内容满足第 i 个人的身高为 hi 前面 正好 有 ki 个身高大于或等于 hi 的人只需要构造
前面的人都比第i个人高前面的人的个数是k[i]
因此需要先对身高从大到小排列若身高相同则对k从小到大排列。如[5,0]一定在[5,1]前
以[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]为例排序后为
[ [ 7, 0 ], [ 7, 1 ], [ 6, 1 ], [ 5, 0 ], [ 5, 2 ], [ 4, 4 ] ]开始构造
对[ 7, 0 ]前面有0个比它高的因此他在第0个这里的0即people[0][0]对[ 7, 1 ]前面有1个比它高的因此他在第1个这里的0即people[1][1]对[ 6, 1 ]前面有1个比它高的因此他在第1个这里的1即people[2][1]对[ 5, 0 ]前面有0个比它高的因此他在第0个这里的0即people[3][1]
以此类推。
每次的queue为
i为 0 , [ [ 7, 0 ] ]
i为 1 , [ [ 7, 0 ], [ 7, 1 ] ]
i为 2 , [ [ 7, 0 ], [ 6, 1 ], [ 7, 1 ] ]
i为 3 , [ [ 5, 0 ], [ 7, 0 ], [ 6, 1 ], [ 7, 1 ] ]
i为 4 , [ [ 5, 0 ], [ 7, 0 ], [ 5, 2 ], [ 6, 1 ], [ 7, 1 ] ]
i为 5 , [ [ 5, 0 ], [ 7, 0 ], [ 5, 2 ], [ 6, 1 ], [ 4, 4 ], [ 7, 1 ] ]总体代码
var reconstructQueue function (people) {// 先看h,h从大到小,若h一样看k从小到大people.sort((a, b) {if (a[0] ! b[0]) return b[0] - a[0];else return a[1] - b[1];})let queue []for (let i 0; i people.length; i) {queue.splice(people[i][1], 0, people[i]);}return queue;
};452. 用最少数量的箭引爆气球
452. 用最少数量的箭引爆气球
var findMinArrowShots function (points) {let ans 1;// 都从小到大排points.sort((a, b) {if (a[0] ! b[0]) return a[0] - b[0];else return a[1] - b[1];})let min points[0][0], max points[0][1];for (let i 1; i points.length; i) {let a points[i][0], b points[i][1];if (a min b max) {min amax b} else {if (a min a max) min aelse if (b min b max) max belse {ans;min a, max b;}}}return ans;
};435. 无重叠区间
435. 无重叠区间
var eraseOverlapIntervals function (intervals) {intervals.sort((a, b) {if (a[0] ! b[0]) return a[0] - b[0]else return a[1] - b[1]})let ans 0let min intervals[0][0], max intervals[0][1]for (let i 1; i intervals.length; i) {let a intervals[i][0], b intervals[i][1]if (a max) {min a, max b} else {ans;if (a min b max) {min a, max b;}}}return ans;
};763.划分字母区间
763.划分字母区间
var partitionLabels function (s) {let start new Map(), end new Map()for (let i 0; i s.length; i) {// 注意只有一个的情况end.set(s[i], i);if (!start.has(s[i])) start.set(s[i], i);}let arr [...start.keys()], nums []arr.forEach(item {nums.push([start.get(item), end.get(item)])})// 从小到大nums.sort((a, b) {if (a[0] ! b[0]) return a[0] - b[0]else return a[1] - b[1]})let min nums[0][0], max nums[0][1], ans []for (let i 1; i nums.length; i) {let a nums[i][0], b nums[i][1]if (a max) {ans.push(max - min 1)min a, max b} else max Math.max(max, b);}ans.push(max - min 1)return ans;
};56. 合并区间
56. 合并区间
var merge function (intervals) {// 从小到大intervals.sort((a, b) {if (a[0] ! b[0]) return a[0] - b[0]else return a[1] - b[1]})let min intervals[0][0], max intervals[0][1], ans []for (let i 1; i intervals.length; i) {let a intervals[i][0], b intervals[i][1];if (a min b max) continue;if (a max) {ans.push([min, max])min a, max b;} else max b;}ans.push([min, max])return ans;
};738.单调递增的数字
738.单调递增的数字
var monotoneIncreasingDigits function (n) {let str n.toString()str str.split().map(item {return Number(item)});// 找到第一个不是递增的位置let flag;for (let i str.length - 1; i 0; i--) {if (str[i - 1] str[i]) {flag istr[i - 1]--;str[i] 9}}for (let i flag; i str.length; i) str[i] 9return Number(str.join())
};968.监控二叉树
968. 监控二叉树
困难先跳了。
