一：題目：

字符串 S 由小寫字母組成。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現在一個片段中。返回一個表示每個字符串片段的長度的列表。

示例：

輸入：S = "ababcbacadefegdehijhklij" 輸出：[9,7,8] 解釋： 劃分結果為 "ababcbaca", "defegde", "hijhklij"。 每個字母最多出現在一個片段中。 像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的，因為劃分的片段數較少。

二：思路：

思路:1.統計每個字母最后出現時候所對應的下標，
2.然后在遍歷字符串，當 i 和該字母所對應的下標一樣時，說明這是一個區間

三：圖示：

四：上碼：

class Solution { public:vector<int> partitionLabels(string s) {/**思路:1.統計每個字母最后出現時候所對應的下標，2.然后在遍歷字符串，當 i 和該字母所對應的下標一樣時，說明這是一個區間*/map<char,int>m;//選取map容器是因為map的鍵值有自動去重功能，可以不斷更新下標的位置vector<int>v;int start = 0,end = 0;//記錄每個字母最后出現時候的下標for(int i = 0; i < s.size(); i++){m[s[i]] = i;}for(int i = 0; i < s.size(); i++){end = max(end,m[s[i]]);//這里每次選取每個區間內的字母對應的下標最大值if(end == i){v.push_back( end - start + 1);start = end+1;}}return v;} };

加油 BOY!!!

總結

以上是生活随笔為你收集整理的763. 划分字母区间009（贪心算法+思路+详解+图示）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。