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();