+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-07(2)

2019-08(106)

2019-09(110)

2019-10(14)

2019-11(8)

leetcode每日一题V—763.划分字母区间

发布于2020-10-24 19:09     阅读(753)     评论(0)     点赞(5)     收藏(4)


0

1

2

3

4

5

6

7

基础知识:
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
题目:
字符串 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

0

1

2

3

4

5

6

7

8

9



所属网站分类: 技术文章 > 博客

作者:9384vfnv

链接: https://www.pythonheidong.com/blog/article/608548/97dcdd2b08b0449f771e/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

5 0
收藏该文
已收藏

评论内容:(最多支持255个字符)