- 134.加油站
- 455.分发饼干
- 860.柠檬水找零
- 2171.拿出最少数目的魔法豆
- 826.安排工作以达到最大收益
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;
// 邮箱清0
currentGas = 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;
}
// 其他情况都是false
else 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 个魔法豆更少的方案。
826.安排工作以达到最大收益
/**
* @param {number[]} difficulty
* @param {number[]} profit
* @param {number[]} worker
* @return {number}
*/
// 思路
// 遍历worker 获取到每个工人能做的难度事情,
// 遍历时根据下标更新最大财富的金额
var maxProfitAssignment = function (difficulty, profit, worker) {
let maxValue = 0;
for (let i = 0; i < worker.length; i++) {
let curVal = 0;
for (let j = 0; j < difficulty.length; j++) {
if (worker[i] >= difficulty[j]) {
curVal = Math.max(curVal, profit[j]);
}
}
maxValue += curVal;
}
console.log(maxValue);
return maxValue;
};
maxProfitAssignment([2, 4, 6, 8, 10], [10, 20, 30, 40, 50], [4, 5, 6, 7]);
maxProfitAssignment([85, 47, 57], [24, 66, 99], [40, 25, 25]);
// 输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
// 输出: 100
// 解释: 工人被分配的工作难度是 [4,4,6,6] ,分别获得 [20,20,30,30] 的收益。
// 输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
// 输出: 0
文章来源地址https://www.toymoban.com/news/detail-849072.html
文章来源:https://www.toymoban.com/news/detail-849072.html
到了这里,关于算法| ss 贪心的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!