乡村门户网站建设,青浦做网站,大连工程信息建设网,在本地服务器上建设网站的步骤原题链接#x1f517;#xff1a;划分字母区间难度#xff1a;中等⭐️⭐️
题目
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。
注意#xff0c;划分结果需要满足#xff1a;将所有划分结果按顺序连接#…原题链接划分字母区间难度中等⭐️⭐️
题目
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1 输入s “ababcbacadefegdehijhklij” 输出[9,7,8] 解释 划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的因为划分的片段数较少。
示例 2
输入s “eccbbbbdec” 输出[10]
提示
1 s.length 500s 仅由小写英文字母组成
贪心算法 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择从而希望导致结果是全局最好或最优的算法策略。它在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。 贪心算法不保证会得到最优解但在某些问题上贪心算法的解是足够好的。以下是贪心算法的一些关键特性 贪心选择性质算法在每一步都选择当前看起来最优的选项而不考虑未来的选择。最优子结构问题可以分解为子问题子问题的最优解能组成原问题的最优解。可行性贪心选择必须在当前状态下可行。 贪心算法通常用于求解以下类型的问题 资源分配问题调度问题网络流问题集合覆盖问题最小生成树问题如 Prim 算法和 Kruskal 算法 贪心算法的实现步骤通常包括 定义问题的一个解决方案。遍历所有候选解。选择当前状态下的最优候选解并将其添加到当前解决方案中。重复步骤2和3直到达到问题的结束条件。 贪心算法的优点是简单、直观且在某些情况下效率很高。然而缺点是它不总是能得到全局最优解特别是当问题不具有最优子结构时。 题解
解题思路 这个问题是一个典型的贪心算法问题我们可以通过以下步骤来解决 初始化创建一个空列表 result 用来存储每个片段的长度。 遍历字符串从左到右遍历字符串 s。 记录当前字母使用一个变量 current_char 记录当前遍历到的字母。 计数使用一个变量 count 来记录当前字母连续出现的次数。 更新片段长度每当遇到一个新的字母或者到达字符串的末尾时将 count 加入到 result 列表中并重置 count 和 current_char。 特殊情况处理如果当前字母和下一个字母相同则 count 自增继续遍历如果不同将当前 count 存入 result 并更新 current_char 和 count。 返回结果遍历结束后返回 result 列表。 c demo
#include iostream
#include vector
#include unordered_mapusing namespace std;class Solution {
public:vectorint partitionLabels(string s) {vectorint result;unordered_mapchar, 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;vectorint result solution.partitionLabels(s);for (int length : result) {cout length ;}cout endl;return 0;
}输出结果 9 7 8 代码仓库地址partitionLabels
