字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。 示例 1： 输入：S = “ababcbacadefegdehijhklij” 输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/partition-labels 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include "pch.h" #include <iostream> #include<string> #include<vector> #include<algorithm> using namespace std; class Solution { public: vector<int> partitionLabels(string S) { int last[26]; int length = S.size(); for (int i = 0; i < length; i++) { last[S[i] - 'a'] = i; //记录每个字母存的位置 对应第i个位置存的字母是S[i]-'a' a-z对应0-26 给每个字母编号 } vector<int> partition; int start = 0, end = 0; for (int i = 0; i < length; i++) { //遍历S end = max(end, last[S[i] - 'a']); //end等于对应a-z字母最后出现的位置 //例如：i=0时第一个字母出现的最后的位置等于end if (i == end) { //如果i等于最后出现的位置 把当前位置记录压入partitionLabels partition.push_back(end - start + 1); start = end + 1; } } return partition; } }; int main() { vector<int> a; string S; cin >> S; Solution test; a=test.partitionLabels(S); for (vector<int>::iterator iter = a.begin(); iter != a.end(); iter++) { cout << *iter << " "; } return 0; }