Leetcode刷题-763-partition labels-贪心

partition labels

题目：A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

链接：点这里

贪心算法

思路 首先遍历s，得到每个字母最靠后出现的位置下标index

然后从左开始再次遍历，由最左边的字母得到一个区间，遍历区间内的字母最后出现的位置如果不在该区间则扩大区间，否则继续遍历。

首先是记录最后出现的位置的技巧

int map[26];
       int len = S.size();
       for(int i=0;i<len;i++)
       {
           map[s[i]-'a']=i;
       } 
           

第二次遍历找区间

官方题解：简单美观，但需要设置多个变量记录位置，我暂时还没能往这方面想

只能记录到end的位置，再最后减。

此处记录动态大小数组vector，可以直接得到没固定大小的数组输出，很方便。

// vector声明
vector<int>vname ;
//vector大小获取
int len = vector.size();