本站消息
588
文章
329593
访问
+关注
分类
暂无分类
标签
暂无标签
leetcode每日一题V—763.划分字母区间
发布于2020-10-24 19:09 阅读(753) 评论(0) 点赞(5) 收藏(4)
基础知识：
题目：
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
思路：
1.利用enumerate() 函数用于将字符串转换为一个索引序列，对其遍历，并用last[]记录每个字母最后一次出现的位置;
2.利用贪心算法 判断当前片段的起始和结束位置：start和end，初始值置为0
解答：
class Solution:
def partitionLabels(self, S: str) -> List[int]:
last = [0] * 26
#记录每个字母的最后一次出现的位置
for i, ch in enumerate(S):
last[ord(ch) - ord("a")] = i
partition = list()
#当前片段的起始和结束下标
start = end = 0
for i, ch in enumerate(S):
end = max(end, last[ord(ch) - ord("a")])
if i == end:
partition.append(end - start + 1)
start = end + 1
return partition
原文链接:https://blog.csdn.net/jqq125/article/details/109216557
所属网站分类: 技术文章 > 博客
作者：9384vfnv
链接： https://www.pythonheidong.com/blog/article/608548/97dcdd2b08b0449f771e/
来源： python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
5
0
收藏该文
昵称:
评论内容：(最多支持255个字符)
程序员的那些事(new)
电子书(new)
博客(new)
视频教程(new)
问答(new)
游戏(new)