建设网站难吗,红河县网站建设,wordpress host头攻击,h5编辑软件给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。
注意#xff0c;划分结果需要满足#xff1a;将所有划分结果按顺序连接#xff0c;得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1 输入s “ababcbacadefegdehijhklij” 输出[9,7,8] 解释 划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的因为划分的片段数较少。 示例 2 输入s “eccbbbbdec” 输出[10] 提示 1 s . l e n g t h 500 1 s.length 500 1s.length500 s 仅由小写英文字母组成 思路
初始化遍历字符串中的字符求出每个字符在字符串中最右的下标遍历字符串中的字符确定一个区间使得区间中的字串满足区间内每一个字母最只出现在当前区间中 用 l/r 标识当前区间的左/右边界下标如果当前字符的下标 r则将 [l.r] 加入 res 结果中更新 l 和 r否则更新 r 下标 对于 r如果当前字符在整个字符串中的最右边界 当前子区间的 r 边界则用其更新 r
class Solution {
public:int rmax[30];vectorint partitionLabels(string s) {int n s.size();for(int i 0; i n; i){rmax[s[i]-a] max(rmax[s[i]-a], i);}vectorint res;int l -1, r -1;for(int i 0; i n; i){if(i r){if(i) res.push_back(r - l 1);l i;}r max(r, rmax[s[i]-a]);}res.push_back(r - l 1);return res;}
};
