LeetCode 算法：划分字母区间 c++

• 原题链接🔗：划分字母区间
• 难度：中等⭐️⭐️

题目

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = “eccbbbbdec”
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法策略。它在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。

贪心算法不保证会得到最优解，但在某些问题上贪心算法的解是足够好的。以下是贪心算法的一些关键特性：

1. 贪心选择性质：算法在每一步都选择当前看起来最优的选项，而不考虑未来的选择。
2. 最优子结构：问题可以分解为子问题，子问题的最优解能组成原问题的最优解。
3. 可行性：贪心选择必须在当前状态下可行。

贪心算法通常用于求解以下类型的问题：

• 资源分配问题
• 调度问题
• 网络流问题
• 集合覆盖问题
• 最小生成树问题（如 Prim 算法和 Kruskal 算法）

贪心算法的实现步骤通常包括：

1. 定义问题的一个解决方案。
2. 遍历所有候选解。
3. 选择当前状态下的最优候选解，并将其添加到当前解决方案中。
4. 重复步骤2和3，直到达到问题的结束条件。

贪心算法的优点是简单、直观，且在某些情况下效率很高。然而，缺点是它不总是能得到全局最优解，特别是当问题不具有最优子结构时。

题解

1. 解题思路：

这个问题是一个典型的贪心算法问题，我们可以通过以下步骤来解决：

• 初始化：创建一个空列表 result 用来存储每个片段的长度。

• 遍历字符串：从左到右遍历字符串 s。

• 记录当前字母：使用一个变量 current_char 记录当前遍历到的字母。

• 计数：使用一个变量 count 来记录当前字母连续出现的次数。

• 更新片段长度：每当遇到一个新的字母，或者到达字符串的末尾时，将 count 加入到 result 列表中，并重置 count 和 current_char。

• 特殊情况处理：如果当前字母和下一个字母相同，则 count 自增，继续遍历；如果不同，将当前 count 存入 result 并更新 current_char 和 count。

• 返回结果：遍历结束后，返回 result 列表。

2. c++ demo：

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;class Solution {
public:vector<int> partitionLabels(string s) {vector<int> result;unordered_map<char, int> last_position;int start = 0, end = -1, length = 0;// 记录每个字符最后一次出现的位置for (int i = 0; i < s.length(); ++i) {last_position[s[i]] = i;}for (int i = 0; i < s.length(); ++i) {// 更新当前片段的结束位置end = max(end, last_position[s[i]]);length++;// 如果当前位置是当前片段的结束位置，则添加到结果中if (i == end) {result.push_back(length);start = i + 1; // 重置片段开始位置end = -1; // 重置片段结束位置length = 0; // 重置片段长度}}return result;}
};int main() {Solution solution;string s = "ababcbacadefegdehijhklij";vector<int> result = solution.partitionLabels(s);for (int length : result) {cout << length << " ";}cout << endl;return 0;
}

• 输出结果：

9 7 8

3. 代码仓库地址：partitionLabels