带你读《图解算法小抄》二十二、贪心算法(5)

简介: 带你读《图解算法小抄》二十二、贪心算法(5)

带你读《图解算法小抄》二十二、贪心算法(4)https://developer.aliyun.com/article/1347850?groupCode=tech_library


6.分糖果

1)题目描述

给定一个整数数组 ratings,表示每个孩子的评分。现在你要按照以下规则给这些孩子分糖果:

 

  • 每个孩子至少分配到 1 个糖果。
  • 如果一个孩子的评分比他相邻的孩子高,那么他应该得到更多的糖果。

你需要计算出最少需要分配多少糖果才能满足上述要求。

2)解题步骤

为了解决分糖果的问题,我们可以使用贪心算法来解决。

 

  • 首先初始化一个长度为 ratings.length 的糖果数组 candies,用于记录每个孩子分配到的糖果数量,初始值都为 1。
  • 从左到右遍历 ratings 数组,比较当前孩子的评分与前一个孩子的评分:
  • 如果当前孩子的评分大于前一个孩子的评分,将当前孩子分配到的糖果数量设为前一个孩子分配到的糖果数量加一。
  • 否则,不做任何操作。

 

  • 从右到左再次遍历 ratings 数组,比较当前孩子的评分与后一个孩子的评分:
  • 如果当前孩子的评分大于后一个孩子的评分,并且当前孩子分配到的糖果数量小于等于后一个孩子分配到的糖果数量,将当前孩子分配到的糖果数量设为后一个孩子分配到的糖果数量加一。
  • 否则,不做任何操作。

 

  • 遍历完成后,将糖果数组 candies 中的所有元素相加,得到最少需要分配的糖果数量。

下面是使用贪心算法解决分糖果问题的算法框架:

 

function minCandies(ratings) {
  const candies = Array(ratings.length).fill(1);  for (let i = 1; i < ratings.length; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }  for (let i = ratings.length - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
      candies[i] = candies[i + 1] + 1;
    }
  }
  return candies.reduce((sum, candy) => sum + candy, 0);
}


带你读《图解算法小抄》二十二、贪心算法(6)https://developer.aliyun.com/article/1347847?groupCode=tech_library

 


相关文章
|
22天前
|
算法 Java C++
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
|
5月前
|
算法 C++ Python
数据结构与算法===贪心算法
数据结构与算法===贪心算法
|
2月前
|
算法 前端开发
一文了解贪心算法和回溯算法在前端中的应用
该文章深入讲解了贪心算法与回溯算法的原理及其在前端开发中的具体应用,并通过分析LeetCode题目来展示这两种算法的解题思路与实现方法。
|
3月前
|
算法
【算法】贪心算法——柠檬水找零
【算法】贪心算法——柠檬水找零
|
3月前
|
算法
【算法】贪心算法简介
【算法】贪心算法简介
|
4月前
|
算法 Python
Python算法高手进阶指南:分治法、贪心算法、动态规划,掌握它们,算法难题迎刃而解!
【7月更文挑战第10天】探索Python算法的精华:分治法(如归并排序)、贪心策略(如找零钱问题)和动态规划(解复杂问题)。通过示例代码揭示它们如何优化问题解决,提升编程技能。掌握这些策略,攀登技术巅峰。
101 2
|
4月前
|
存储 算法 Python
Python算法界的秘密武器:分治法巧解难题,贪心算法快速决策,动态规划优化未来!
【7月更文挑战第9天】Python中的分治、贪心和动态规划是三大关键算法。分治法将大问题分解为小问题求解,如归并排序;贪心算法每步选局部最优解,不保证全局最优,如找零钱;动态规划存储子问题解求全局最优,如斐波那契数列。选择合适算法能提升编程效率。
64 1
|
4月前
|
存储 算法 大数据
Python算法高手的必修课:深入理解分治法、贪心算法、动态规划,让你的代码更智能!
【7月更文挑战第9天】在Python算法学习中,分治法(如归并排序)将大问题分解为小部分递归解决;贪心算法(如货币找零)在每步选择局部最优解尝试达到全局最优;动态规划(如斐波那契数列)通过存储子问题解避免重复计算,解决重叠子问题。掌握这三种方法能提升代码效率,解决复杂问题。
44 1
|
4月前
|
算法 索引 Python
逆袭算法界!Python分治法、贪心算法、动态规划深度剖析,带你走出算法迷宫!
【7月更文挑战第8天】分治法,如快速排序,将大问题分解并合并解;贪心算法,选择局部最优解,如活动选择;动态规划,利用最优子结构避免重复计算,如斐波那契数列。Python示例展示这些算法如何解决实际问题,助你精通算法,勇闯迷宫。
42 1
|
4月前
|
算法 索引 Python
Python算法设计与分析大揭秘:分治法、贪心算法、动态规划...掌握它们,让你的编程之路更加顺畅!
【7月更文挑战第8天】探索Python中的三大算法:分治(如快速排序)、贪心(活动选择)和动态规划(0-1背包问题)。分治法将问题分解求解再合并;贪心策略逐步求局部最优;动态规划通过记忆子问题解避免重复计算。掌握这些算法,提升编程效率与解决问题能力。
38 1