作为一个通信人，平对对CS方面的东西都是东看一点西看一点的碎片化的东西。最近不是特别忙，打算坚持做一个刷题系列，每天跟着LEETCODE官网刷题，把网站的每日一题，自己的想法、思路和代码发不出来，大家一起讨论讨论，说不定会有更好的实现方案！
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。 示例 1： 输入：S = “ababcbacadefegdehijhklij” 输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。 提示： S的长度在[1, 500]之间。 S只包含小写字母 ‘a’ 到 ‘z’ 。 链接：https://leetcode-cn.com/problems/partition-labels
首先注意到字符串只包括小写字母，并且长度最长的500，大胆猜测是可以使用暴力破解法的。暴力法需要找到每种划分成字符片段的方式，并且对每个字符片段检查是否包含的字符串只出现在该字符片段中，最后从所有划分中找到一个划分片段最多的方案，返回长度列表。 可以看出来上述暴力破解法，有大量重复和不必要的处理。对于一个字符片段而言，要求同一个字母只出现在该片段中，也就是说，对于该字符片段中的每一个字母，都只能出现在该字符片段中，这个字母第一次出现和最后一次出现的位置都包括在字符片段中，这也是对该字母而言，长度最短的划分方式了。我们对所有字母都做这个处理，那么这个划分出来的字符片段就是最短的字符片段，每个字符片段保证为最短的划分，此时的划分结果就是字符片段最多的结果。 具体做法如下： 第一次遍历，对于每一个字母，找到其最后出现的位置，并记录下来。 初始化当前划分的起始位置分别为start,end=0,0 第二次遍历，寻找对于每一个字母，其最后一次出现的位置为last_pos，则目前位置的最短划分子串的末尾位置为end=max(end,last_pos)。如果遍历的当前位置已经是end，则说明出现在目前子串的每个字母都已经包括在内了，则记录下当前这个子串的长度，开始新一个子串的划分，设置start为当前位置。 具体代码如下。
