带你读《图解算法小抄》二十二、贪心算法（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
