【LeetCode与《代码随想录》】贪心算法篇：做题笔记与总结-JavaScript版

代码随想录

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

文章目录

- 455. 分发饼干
- 376. 摆动序列
- 53. 最大子数组和
- 122. 买卖股票的最佳时机 II
- 55. 跳跃游戏
- 45. 跳跃游戏 II
- 1005. K 次取反后最大化的数组和
- 134. 加油站
- 135. 分发糖果（困难）
- 860. 柠檬水找零
- 406.根据身高重建队列
- 452. 用最少数量的箭引爆气球
- 435. 无重叠区间
- 763.划分字母区间
- 56. 合并区间
- 738.单调递增的数字
- 968.监控二叉树

455. 分发饼干

https://leetcode.cn/problems/assign-cookies/description/

大饼干可以满足大孩子也可以满足小孩子，在这里显然是满足大孩子最划算。因此饼干从大到小，如果饼干可以满足该孩子，ans++，否则，尝试是否可以满足小孩子。

注意跳出循环的条件，当i<0||j<0

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. 摆动序列

想要得到最长的摆动数组，需要保留一个上/下坡的头和尾，如：

1，2，5，7，5，2，1

这里1，2，5，7都是上坡，但1，7的上坡比其他的好，因为7可以与后面组成更好的下坡——若是1，7，则后面想要下坡<7即可；若1，2，后面想要下坡则需要<2，条件比<7要小。反之亦然。

但是，选择1，7还是1，2本质都是上坡，且长度都为2。因此，我们可以把问题简化为数组有多少个上下坡的变化。

上面的样例就是一上一下，不管怎么选摆动数组都是3.

我们用一个flag来记录前面是上坡还是下坡：前面是上坡且当前数组是下坡则ans++，反之亦然。

注意要判断平坡，且从第一个上/下坡之后开始（flag值就记录第一个上/下坡）。

var wiggleMaxLength = function(nums) {// flag表示是上行1还是下行0，-1表示一直平坡let ans=1,flag=-1;// 要找到第一次上行或下行let index=1;for(;index<nums.length;index++){if(nums[index]===nums[index-1]) continue;if(nums[index]>nums[index-1]) {flag=1;ans=2;break;}else{flag=0;ans=2;break;}}for(let i=index+1;i<nums.length;i++){// 上行if(nums[i]>nums[i-1]){if(!flag){ans++;flag=1;}}// 下行else if(nums[i]<nums[i-1]){if(flag){ans++;flag=0;}}}return ans;
};

53. 最大子数组和

分为两种情况：数组全负和数组非全负。

数组全负则选元素最大的那一个。
数组非全负则一直累加并存最大值，若出现cnt<0则令cnt=0，相当于前面部分都不选。

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

有prices数组：1,2,3,5,8

最低买入最高卖出肯定是答案，即8-1=7

注意，8-1=（2-1）+（3-2）+（5-3）+（8-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. 跳跃游戏

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

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 次取反后最大化的数组和

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. 加油站

n是1e5，暴力双层循环会超出时间限制。

获得数组arr=gas-cost，arr[i]表示离开i地点剩余的油。
遍历arr，计算区间和，但凡出现区间和<0，说明不能从这个区间的开头开始走（没油了），可能从此区间的下一个地方j开始走。于是从j开始计算区间和。维护这个j值：是可能的答案。

计算arr的和，若arr的和>0，说明存在一个地方开始走能顺时针跑完。由题知，这个答案是唯一的。因此就是上面维护的j值。

若arr<0，说明不存在答案。

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. 柠檬水找零

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.根据身高重建队列

想要队列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. 用最少数量的箭引爆气球

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. 无重叠区间

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.划分字母区间

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. 合并区间

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.单调递增的数字

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(''))
};