Leetcode 每日一题 题目链接：763. 划分字母区间 解题思路： 预处理出所有相同的字符的最后一个字符所在的位置，对于每个字符都标记这个位置（O(n)），然后遍历整个字符串（O(n)），动态找到最大的位置即为划分的位置。下图为例（反向求解）： 题解：
class Solution: def partitionLabels(self, S: str) -> List[int]: slist = list(S) slist.reverse() slen = len(slist) # position 记录最后的位置，visit标记 position = [] visit = {} index = slen # 求解位置 for c in slist: # print(c) if visit.get(c, -1) == -1: visit[c] = index position.append(visit[c] - 1) index -= 1 position.reverse() index, max_position = 0, 0 result = [] # 动态找到最长的长度 for key in position: if key > max_position: max_position = key # 找到了最长的长度，求划分以后的长度 if index == max_position: if len(result) == 0: result.append(max_position) else: result.append(max_position-sum(result)) index += 1 # 对于第一个还要加上1，由于第一个是取得下标 result[0] += 1 return result