https://leetcode.com/problems/partition-labels/
题意是要对一个字符串进行尽可能多的划分,并保证每个划分中的元素不在其他划分中出现。
想法比较具有技巧性。如果一段序列中每个元素的在S中最右边的序号都在某个范围内,那么就可以划分成一个段。
因此,使用字典保存每个元素出现的最靠右的位置。然后对字符串S进行遍历,找出最靠右的序号的最大值j。如果i和j重合了,说明已经到了这个划分的末尾了,然后进行划分。并开始计算下一个划分。
https://zxi.mytechroad.com/blog/string/leetcode-763-partition-labels/
https://segmentfault.com/a/1190000017354158
A string
S
of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
Example 1:
Input: S = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
Note:
S
will have length in range[1, 500]
.S
will consist of lowercase letters ('a'
to'z'
) only
- 字符串中等題。滑動窗口+貪心。時間複雜度O(N),空間複雜度O(N)。
- 首先依然是做hash,不過這次是對所有char記錄它們最後出現的位置。
- 然後定義三個指針,window開始left和結束right,當前i。每次移動i,然後判斷當前S[i]最後出現的位置是否大於當前right,如果是,則擴展right為last[S[i]]。
- 如果當前i == window結束right,則代表當前window中所有的字符都只在當前window中出現。所以可以把當前window的size記錄。同時移動left到下一個window的起點。
16 vector<int> partitionLabels(string S) { 17 vector<int> vResult; 18 19 // corner case 20 if (S.empty()) return vResult; 21 22 unordered_map<char, int> last; 23 24 // the last occurred index of S[i] 25 for (int i = 0; i < S.size(); ++ i) 26 last[S.at(i)] = i; 27 28 // start and end of the current window 29 int left = 0, right = 0; 30 31 // current pointer 32 for (int i = 0; i < S.size(); ++ i) { 33 right = max(right, last[S.at(i)]); // maximum index of the current window 34 35 // reach the end of current window 36 if (i == right) { 37 vResult.push_back(right - left + 1); // size of the current window 38 left = i + 1; // move to start of the next window 39 } 40 } 41 42 return vResult; 43 }https://blog.csdn.net/fuxuemingzhu/article/details/79265829
题意是要对一个字符串进行尽可能多的划分,并保证每个划分中的元素不在其他划分中出现。
想法比较具有技巧性。如果一段序列中每个元素的在S中最右边的序号都在某个范围内,那么就可以划分成一个段。
因此,使用字典保存每个元素出现的最靠右的位置。然后对字符串S进行遍历,找出最靠右的序号的最大值j。如果i和j重合了,说明已经到了这个划分的末尾了,然后进行划分。并开始计算下一个划分。
vector<int>
partitionLabels(string S) {
map<char, int> d;
for (int i = 0; i < S.size(); i++) d[S[i]] = i;
int start = 0, end = 0;
vector<int> res;
for (int i = 0; i < S.size(); i++) {
end = max(end, d[S[i]]);
if (i == end) {
res.push_back(end - start + 1);
start = end + 1;
}
}
return res;
}
http://www.cnblogs.com/grandyang/p/8654822.html
这道题给了我们一个字符串S,然我们将其尽可能多的分割为子字符串,条件是每种字符最多只能出现在一个子串中。比如题目汇总的例子,字符串S中有多个a,这些a必须只能在第一个子串中,再比如所有的字母e值出现在了第二个子串中。那么这道题的难点就是如何找到字符串的断点,即拆分成为子串的位置。我们仔细观察题目中的例子,可以发现一旦某个字母多次出现了,那么其最后一个出现位置必须要在当前子串中,字母a,e,和j,分别是三个子串中的结束字母。所以我们关注的是每个字母最后的出现位置,我们可以使用一个HashMap来建立字母和其最后出现位置之间的映射,那么对于题目中的例子来说,我们可以得到如下映射:
a -> 8
b -> 5
c -> 7
d -> 14
e -> 15
f -> 11
g -> 13
h -> 19
i -> 22
j -> 23
k -> 20
l -> 21
b -> 5
c -> 7
d -> 14
e -> 15
f -> 11
g -> 13
h -> 19
i -> 22
j -> 23
k -> 20
l -> 21
建立好映射之后,就需要开始遍历字符串S了,我们维护一个start变量,是当前子串的起始位置,还有一个last变量,是当前子串的结束位置,每当我们遍历到一个字母,我们需要在HashMap中提取出其最后一个位置,因为一旦当前子串包含了一个字母,其必须包含所有的相同字母,所以我们要不停的用当前字母的最后一个位置来更新last变量,只有当i和last相同了,即当i = 8时,当前子串包含了所有已出现过的字母的最后一个位置,即之后的字符串里不会有之前出现过的字母了,此时就应该是断开的位置,我们将长度9加入结果res中
https://leetcode.com/articles/partition-labels/
Let's try to repeatedly choose the smallest left-justified partition. Consider the first label, say it's
'a'
. The first partition must include it, and also the last occurrence of 'a'
. However, between those two occurrences of 'a'
, there could be other labels that make the minimum size of this partition bigger. For example, in "abccaddbeffe"
, the minimum first partition is "abccaddb"
. This gives us the idea for the algorithm: For each letter encountered, process the last occurrence of that letter, extending the current partition [anchor, j]
appropriately.
Algorithm
We need an array
last[char] -> index of S where char occurs last
. Then, let anchor
and j
be the start and end of the current partition. If we are at a label that occurs last at some index after j
, we'll extend the partition j = last[c]
. If we are at the end of the partition (i == j
) then we'll append a partition size to our answer, and set the start of our new partition to i+1
.
public List<Integer> partitionLabels(String S) {
int[] last = new int[26];
for (int i = 0; i < S.length(); ++i)
last[S.charAt(i) - 'a'] = i;
int j = 0, anchor = 0;
List<Integer> ans = new ArrayList();
for (int i = 0; i < S.length(); ++i) {
j = Math.max(j, last[S.charAt(i) - 'a']);
if (i == j) {
ans.add(i - anchor + 1);
anchor = i + 1;
}
}
return ans;
}
https://zxi.mytechroad.com/blog/string/leetcode-763-partition-labels/
public List<Integer> partitionLabels(String S) {
int lastIndex[] = new int[128];
for (int i = 0; i < S.length(); ++i)
lastIndex[(int)S.charAt(i)] = i;
List<Integer> ans = new ArrayList<>();
int start = 0;
int end = 0;
for (int i = 0; i < S.length(); ++i) {
end = Math.max(end, lastIndex[(int)S.charAt(i)]);
if (i == end) {
ans.add(end - start + 1);
start = end + 1;
}
}
return ans;
}
https://segmentfault.com/a/1190000017354158