leetcode 763. 划分字母区间
题目详情
题目链接 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例 1： 输入：S = “ababcbacadefegdehijhklij” 输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。提示： S的长度在[1, 500]之间。 S只包含小写字母 ‘a’ 到 ‘z’ 。
我的代码
class Solution {
public:
vector
<int> partitionLabels(string S
) {
int n
= S
.size();
if (n
== 1) {
return {1};
}
map
<char, int> locs
;
for (int i
= 0; i
< n
; ++i
) {
locs
[S
[i
]] = i
;
}
vector
<int> results
;
int left
= 0, right
= locs
[S
[left
]];
while (left
< n
&& right
!= n
- 1) {
for (int i
= left
+ 1; i
<= right
; ++i
) {
right
= max(right
, locs
[S
[i
]]);
}
results
.push_back(right
- left
+ 1);
left
= right
+ 1;
right
= locs
[S
[left
]];
}
if (n
!= left
) {
results
.push_back(n
- left
);
}
return results
;
}
};
我的成绩
执行结果：通过 执行用时：16 ms, 在所有 C++ 提交中击败了28.43%的用户 内存消耗：7 MB, 在所有 C++ 提交中击败了11.53%的用户
一些想法
我的想法是经过一次遍历，记录每个字符最后出现的次数，然后再和之前的比较。
执行用时为 0 ms 的范例
class Solution {
public:
vector
<int> partitionLabels(string S
){
if(!S
.size()) return {};
int t
[26] = {0};
for(int i
= 0; i
< S
.size(); i
++)
t
[S
[i
] - 'a'] = i
;
vector
<int> res
;
int k
= 0;
for(int i
= 0; i
< S
.size();){
int j
= i
;
while(j
<= t
[S
[i
] - 'a'] && t
[S
[j
] - 'a'] <= t
[S
[i
] - 'a']) j
++;
if(j
== t
[S
[i
] - 'a'] + 1){
res
. push_back(t
[S
[i
] - 'a'] - k
+ 1);
k
= j
;
}
i
= j
;
}
return res
;
}
};
思考
参见官方解答
