目录
题目
思路
代码
结果
更优题解
提升笔记
全部代码
题目
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
提示：
S的长度在[1, 500]之间。 S只包含小写字母 'a' 到 'z' 。 链接：https://leetcode-cn.com/problems/partition-labels
思路
并查集
集合：字符的开始下标和结束下标
查找：字符开始到结束这个区间内的所有字符的集合中结束下标最大的
合并：查找时动态更新结束下标
由于按照顺序遍历，集合不需要保存开始下标，开始下标第一次为0，之后为结束下标+1即可。
代码
class Solution {
public:
vector<int> partitionLabels(string S) {
vector<int> res;
//集合 记录字符对应的和终点
unordered_map<char, int> um;
int len = S.size();
//初始化
for (int i = 0; i < len; ++i)um[S[i]] = i;
//查找与合并
int start = 0;
int end = 0;
for (int j = 0; j < len; ++j)
{
end = max(end,um[S[j]]);
if (j == end) {
res.emplace_back(end - start + 1);
start = end + 1;
}
//cout << start << " " << end << endl;
}
return res;
}
};
结果
结果截图
更优题解
思路差不多，粘贴个官方吧-贪心算法+双指针
并查集
提升笔记
给定了小写26个字母，可以使用数组而不是unordered_map来进行存储。数组是真的O(1)，但是unordered_map里面其实还有一些浪费时间的东西，比如计算hash值。
全部代码
/*
https://leetcode-cn.com/problems/partition-labels/
Project: 763. 划分字母区间
Date: 2020/10/22
Author: Frank Yu
*/
#include<vector>
#include<algorithm>
#include<iostream>
#include<unordered_map>
using namespace std;
void check(vector<int> res)
{
for (auto i : res)
{
cout << i << " ";
}
cout << endl;
}
class Solution {
public:
vector<int> partitionLabels(string S) {
vector<int> res;
//集合 记录字符对应的和终点
unordered_map<char, int> um;
int len = S.size();
//初始化
for (int i = 0; i < len; ++i)um[S[i]] = i;
//查找与合并
int start = 0;
int end = 0;
for (int j = 0; j < len; ++j)
{
end = max(end,um[S[j]]);
if (j == end) {
res.emplace_back(end - start + 1);
start = end + 1;
}
cout << start << " " << end << endl;
}
return res;
}
};
//主函数
int main()
{
Solution s;
check(s.partitionLabels("ababcbacadefegdehijhklij"));
//check(s.partitionLabels(""));
//check(s.partitionLabels("abc"));
//check(s.partitionLabels("awddwetwedwesfgrhthy"));
return 0;
}
更多内容：OJ网站题目分类，分难度整理笔记（leetcode、牛客网）
喜欢本文的请动动小手点个赞，收藏一下，有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。
