Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

※ 引述 《Rushia (早瀬ユウカの体操服)》 之銘言：
: 　
: https://leetcode.com/problems/partition-labels
: 763. Partition Labels
: 給你一個字母字串，可以把該字串切成n段子字串，任意字母只能出現在一段，且
: 盡量切成越多段越好，求出每段的長。
: 　
: 思路:
: 類似前幾天的區間問題，把每個字母第一次出現和最後一次出現的索引當成區間，
: 然後把交錯的區間合併，到下個區間的時候把區間長記錄起來就好。
: 　



思路

一樣

睡前發現好像最近傳每日的頻率有點低

還是傳一下好了

晚安捏


```cpp
class Solution {
public:
    vector<int> partitionLabels(string s)
    {

        int n = s.size();

        vector<pair<int,int>> cha(26,pair<int,int>{-1,-1});

        for(int i = 0 ; i < n ; i ++)
        {
            if(cha[s[i]-'a'].first == -1)
            {
                cha[s[i]-'a'].first = i;
                cha[s[i]-'a'].second = i;
            }
            else
            {
                cha[s[i]-'a'].second = i;
            }
        }

        sort(cha.begin(),cha.end());
        vector<int> res;
        int p = 0;

        while(p < 26)
        {
            int l = cha[p].first;
            int r = cha[p].second;

            if(l == -1 && r == -1)
            {
                p++;
                continue;
            }

            int np = p+1;
            while(np < 26 && r > cha[np].first)
            {
                r = max(r,cha[np].second);
                np++;
            }

            res.push_back(r-l+1);

            p = np;
        }

        return res;

    }
};
```




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.235.209 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1743356913.A.6BD.html
→ ttucse: 晚安。
→ oin1104: 晚安