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

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

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


9.划分字母区间

1)题目描述

给定一个字符串 S,将字符串划分为尽可能多的片段,使得每个字母最多出现在一个片段中。返回每个片段的长度列表。

2)解题步骤

为了解决划分字母区间的问题,我们可以使用贪心算法来解决。贪心算法的思路是尽量选择包含较大字母范围的片段,以确保每个字母只出现在一个片段中。

 

 

 

我们按照以下步骤进行解题:

 

  • 创建一个字母表 lastIndex 来存储每个字母最后出现的索引。
  • 遍历字符串 S,对于每个字母 S[i],更新字母在 lastIndex 中的索引为 i。
  • 初始化变量 start 和 end,表示当前片段的起始位置和结束位置,初始值均为 0。
  • 遍历字符串 S,对于每个字母 S[i]:
  • 更新当前片段的结束位置 end 为 Math.max(end, lastIndex[S[i]]),确保当前片段包含了所有之前出现的字母。
  • 如果当前位置 i 等于当前片段的结束位置 end,说明当前片段中的所有字母都在该片段中且没有出现在其他片段中,此时可以将当前片段加入结果列表,并更新下一个片段的起始位置 start 为 end + 1。

 

  • 返回结果列表,即每个片段的长度。

以下是使用贪心算法解决划分字母区间问题的算法框架:

 

function partitionLabels(S) {
  const lastIndex = {};  for (let i = 0; i < S.length; i++) {
    lastIndex[S[i]] = i;
  }  let start = 0;
  let end = 0;
  const result = [];  for (let i = 0; i < S.length; i++) {
    end = Math.max(end, lastIndex[S[i]]);    if (i === end) {
      result.push(end - start + 1);
      start = end + 1;
    }
  }
  return result;
}

 

10.救生艇

1)题目描述

有一些人需要乘坐救生艇从一个岛屿到另一个岛屿。每个人的体重不同,而救生艇有一定的限重。每艘救生艇最多可同时乘坐两人,但条件是这两人的体重之和不超过限重。求解最少需要多少艘救生艇才能将所有人安全送到目的地。

2)解题步骤

为了解决救生艇的问题,我们可以使用贪心算法来解决。

 

  • 首先对人员的体重数组 people 进行排序,从小到大。
  • 使用两个指针 left 和 right 分别指向体重数组的起始位置和末尾位置。
  • 初始化 count 变量为 0,表示救生艇的数量。
  • 在循环中,比较 left 和 right 位置的人员体重之和:
  • 如果体重之和不超过限重,表示可以安排这两个人乘坐一艘救生艇,将 left 向右移动一位,将 right 向左移动一位,同时 count 加一。
  • 如果体重之和超过限重,表示无法安排这两个人乘坐同一艘救生艇,只能让 right 的人单独乘坐一艘救生艇,将 right 向左移动一位,同时 count 加一。

 

  • 循环结束后,返回 count 作为最少需要的救生艇数量。

下面是使用贪心算法解决救生艇问题的算法框架:

 

function numRescueBoats(people, limit) {
  people.sort((a, b) => a - b);  let left = 0;
  let right = people.length - 1;
  let count = 0;  while (left <= right) {
    if (people[left] + people[right] <= limit) {
      left++;
      right--;
    } else {
      right--;
    }
    count++;
  }
  return count;
}


带你读《图解算法小抄》二十二、贪心算法(8)https://developer.aliyun.com/article/1347845?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