网站建设属于什么税,iis做的网站模板,唐山市城市建设档案馆网站,全国装修公司大概多少家题目#xff1a;给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。注意#xff0c;划分结果需要满足#xff1a;将所有划分结果按顺序连接#xff0c;得到的字符串仍然是 s 。返回一个表示每个字符串片段的长度的列表…题目给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。返回一个表示每个字符串片段的长度的列表。
本题我想到了去找当前子字符串出现字母的最远边界但没有想出来如何去寻找。通过遍历整个字符串找到之前遍历的所有字母的最远边界处也就是分割点。
具体步骤如下 1统计每一个字符最后出现的位置使用一个数组进行统计 2从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点 代码如下
class Solution {
public:vectorint partitionLabels(string S) {int hash[27] {0}; // i为字符hash[i]为字符出现的最后位置for (int i 0; i S.size(); i) { // 统计每一个字符最后出现的位置hash[S[i] - a] i;}vectorint result;int left 0;int right 0;for (int i 0; i S.size(); i) {right max(right, hash[S[i] - a]); // 找到字符出现的最远边界if (i right) {result.push_back(right - left 1);left i 1;}}return result;}
};
