leetcode|leetcode 763. Partition Labels 划分字母区间(中等) leetcode763.PartitionLabels划分字母

一、题目大意标签: 贪心
https://leetcode.cn/problems/partition-labels
【leetcode|leetcode 763. Partition Labels 划分字母区间(中等)】字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

提示：

S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。
二、解题思路一个字符串S，将其尽可能多的分割为子字符串，条件是每种字符最多只能出现在一个子串中。上面的示例中，字符串S中有多个a，这些a必须只能在第一个子串中，字母e出现在第二个子串中。这道题难点就是如何找到字符串的断点，即拆分成为子串的位置。观察上述例子，一旦某个字母多次出现，那么其最后一个出现位置必须要在当前子串中，字母a，e，j分别是三个子串中的结束字母。所以我们关注的是每个字母最后的出现位置，我们可以使用一个Map来建立字母和其最后出现位置之间的映射，建立好映射之后，就需要开始遍历字符串S，我们维护一个start变量，是当前子串的起始位置，还有一个last变量，是当前子串的结束位置，每当我们遍历到一个字母，需要在Map中提取出其最后一个位置，因为一旦当前子串饮食了一个字母，其必须饮食所有的相同字母，所以我们要不停的用当前字母的最后一个位置来更新last变量，只有当i和last相同了，即i=last时，当前子串饮食了所有已出现过的字母的最后一个位置，即之后的字符串不会有之前出现过的字母了，此时就应该是断开的位置，我们将子串长度加入到结果中。
三、解题方法3.1 Java实现

public class Solution { public List partitionLabels(String s) { Map map = new HashMap<>(); char[] cArr = s.toCharArray(); for (int i = 0; i < cArr.length; i++) { map.put(cArr[i], i); }List res = new ArrayList<>(); int start = 0; int last = 0; for (int i = 0; i < cArr.length; i++) { last = Math.max(map.get(cArr[i]), last); if (i == last) { res.add(last - start + 1); start = last + 1; } }return res; } }

四、总结小记
2022/7/28 把思路理清了，代码就顺理成章出来了