Re: [閒聊] 每日leetcode
※ 引述 《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
→
03/31 01:50,
8月前
, 1F
03/31 01:50, 1F
→
03/31 01:51,
8月前
, 2F
03/31 01:51, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 1378 之 1548 篇)：