算法| ss 贪心

这篇具有很好参考价值的文章主要介绍了算法| ss 贪心。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  • 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

到了这里,关于算法| ss 贪心的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法 - 动态规划 / 贪心算法

    🥂 🌸 121. 买卖股票的最佳时机 [数组] [股票] (动态规划) 🥂 🌸 122. 买卖股票的最佳时机Ⅱ [数组] [股票] (动态规划) 🥂 🌸 123. 买卖股票的最佳时机Ⅲ [数组] [股票] (动态规划) 🥂 🌸 188. 买卖股票的最佳时机Ⅳ [数组] [股票] (动态规划) 🥂 🌸 309. 买卖股票的最佳时机含冷冻

    2024年01月17日
    浏览(38)
  • 算法-贪心算法

    题目:给定一个字符串str,只由‘X’和‘.’两种字符构成。‘X’表示墙,不能放灯,也不需要点亮‘.’表示居民点,可以放灯,需要点亮如果灯放在i位置,可以让i-1,i和i+1三个位置被点亮返回如果点亮str中所有需要点亮的位置,至少需要几盏灯 思路:递归方式,每个位置

    2024年02月21日
    浏览(39)
  • 初级算法-贪心算法

    主要记录算法和数据结构学习笔记,新的一年更上一层楼! 贪心算法 本质找到每个阶段的局部最优,从而推导全局最优 1. 题目 :假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i],这是能让

    2024年02月03日
    浏览(30)
  • 算法之贪心算法

    定义 总是做出当前最好的选择,期望通过局部最优选择得到全局最优的解决方案。 适用标准 贪心选择性质。 原问题的整体最优解可以通过一系列局部最优的选择得到。这种选择依赖于已做出的选择,不依赖于未做出的选择。贪心算法解决的问题,在程序运行过程中无回溯过

    2024年02月08日
    浏览(34)
  • 18. 算法之贪心算法

    贪心算法(greedy algorithm,又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。下面,我们详细介绍。 贪婪算法(Greedy)的定义: 是一种在每一步选中都采取在当前状态

    2024年02月09日
    浏览(34)
  • 【算法思维】-- 贪心算法

    OJ须知: 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间(中值5*10e8)。在竞赛中, 一般认为计算机1秒能执行 5*10e8 次计算 。 时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11 时间复杂度排序: o(1)

    2024年02月07日
    浏览(36)
  • 计算机算法贪心算法

    贪心算法(Greedy Algorithm)是一种常见的算法思想,它在每一步选择当前状态下最优的解决方案,从而希望最终能够达到全局最优解。 贪心算法的基本思路是每一步都选择当前状态下的局部最优解,而忽略了当前选择所带来的影响,因此并不一定能够得到全局最优解。然而,

    2024年02月02日
    浏览(48)
  • 算法小课堂(五)贪心算法

    贪心算法是一种常见的算法思想,用于解决优化问题。其基本思想是在每一步选择中都采取当前状态下最优的选择,从而希望能够获得全局最优解。 具体来说,贪心算法通常分为以下步骤: 定义问题的最优解,通常需要将问题转化为求最大值或最小值; 选择一个局部最优解

    2024年02月02日
    浏览(43)
  • 【算法】—贪心算法详解

    ①贪心算法的概念 : 贪心算法就是不断选择 在当前看来最好的选择,也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择 虽然贪心算法不能对所有问题都得到整体最优解,但在一些情况下,即使贪心算法 不一定能得到整体最优解 ,其

    2024年02月04日
    浏览(45)
  • 贪心算法part03算法

    ● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果 https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ https://leetcode.cn/problems/gas-station/description/ https://leetcode.cn/problems/candy/description/

    2024年01月18日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包