算法| ss 贪心

本文主要是介绍算法| ss 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 134.加油站
• 455.分发饼干
• 860.柠檬水找零
• 2171.拿出最少数目的魔法豆

134.加油站

/*** @param {number[]} gas* @param {number[]} cost* @return {number}*/
// 思路
// 判断: 汽油和 < 消耗和  return -1
// while循环遍历 从0开始, 计算是否有剩余 ,有就继续 没有就从下个点开始
// 不是绕一圈吗, 没看到代码
var canCompleteCircuit = function (gas, cost) {// 先判断是否有值let remainGas = 0;for (let i = 0; i < gas.length; i++) {remainGas += gas[i] - cost[i];}if (remainGas < 0) return -1;//let i = 0;let index = 0;let currentGas = 0;// 遍历循环while (i < gas.length) {currentGas += gas[i] - cost[i];// console.log("i, curgas", i, currentGas);// 大于等于都算if (currentGas >= 0) {i += 1;} else {//   console.log("上面不通, 下一个加油站");// 出发时的加油站编号, 索引index = i + 1;// 邮箱清0currentGas = 0;// 从下一个开始开发i += 1;}}return index;
};
console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]));
console.log(canCompleteCircuit([2, 3, 4], [3, 4, 3]));// 输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
// 输出: 3
// 输入: gas = [2,3,4], cost = [3,4,3]
// 输出: -1

455.分发饼干

/*** @param {number[]} g* @param {number[]} s* @return {number}*/
// 思路
// 小孩排序
// 饼干排序
// while  饼干 < 饼干长度
// 如果 饼干
var findContentChildren = function (g, s) {// 排序g.sort();s.sort();let child = 0;let cookie = 0;while (cookie < s.length) {// 饼干尺寸大于等于 还是胃口欲望值if (s[cookie] >= g[child]) {child += 1;}cookie += 1;}return child;
};
// 输入: g = [1,2,3], s = [1,1]
// 输出: 1

860.柠檬水找零

/*** @param {number[]} bills* @return {boolean}*/
// 思路
// 定义 5元和10元 数量
// for遍历账单  分3种场景
// 1: 5元 -> 5元数量++
// 2: 10元 -> if 有5元 10元++ 否则 false
// 3: 20元 -> if  有5元且有10元 5元-- 10元-- 否则 如果有5元数量>3  5元-=3 否则false
// 末尾返回true
var lemonadeChange = function (bills) {let five = 0;let ten = 0;for (let i = 0; i < bills.length; i++) {// 5元场景if (bills[i] === 5) {five += 1;// 10元场景} else if (bills[i] === 10) {if (five > 0) {ten += 1;five -= 1;} else {return false;}} else {if (ten > 0 && five > 0) {ten -= 1;five -= 1;} else {// 3张5元可以替换if (five >= 3) {five -= 3;}// 其他情况都是falseelse return false;}}}return true;
};
console.log(lemonadeChange([5, 5, 5, 10, 20]));
// 输入：bills = [5,5,5,10,20]
// 输出：true

2171.拿出最少数目的魔法豆

/*** @param {number[]} beans* @return {number}*/
// 思路
// 数组计算综合 并升序
// for循环遍历
// 关键计算方式:ans = Math.min(ans, sum - beans[i] * (beans.length - i));
var minimumRemoval = function (beans) {const sum = beans.reduce((x, y) => x + y, 0);beans.sort((a, b) => a - b);console.log(beans);let ans = sum;//   对于第个袋子 k， bean 个豆子，左边部分必须全部取出（小于等于），右边部分必须变成（大于等于） bean。可以用总和减去 bean * (beans.length - k)//   对于第k个袋子, 把k袋后面的每个袋子 -  k袋的数量 最小数目= 总和- k袋大小* k袋后面的数量for (let i = 0; i < beans.length; i++) {ans = Math.min(ans, sum - beans[i] * (beans.length - i));}console.log(ans);return ans;
};
minimumRemoval([4, 1, 6, 5]);// [ 1, 4, 5, 6 ]
// i 0 12 12
// i 1 4 4
// i 2 6 4
// i 3 10 4
// 示例 1：// 输入：beans = [4,1,6,5]
// 输出：4
// 解释：
// - 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
//   剩下袋子中魔法豆的数目为：[4,0,6,5]
// - 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
//   剩下袋子中魔法豆的数目为：[4,0,4,5]
// - 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
//   剩下袋子中魔法豆的数目为：[4,0,4,4]
// 总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。
// 没有比取出 4 个魔法豆更少的方案。

这篇关于算法| ss 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---