763. 划分字母区间

- 日理万妓 2022-11-03 11:15 142阅读 0赞

## 763. 划分字母区间 ##

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

### 示例： ###

输入：S = "ababcbacadefegdehijhklij"
    输出：[9,7,8]

解释：  
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。  
每个字母最多出现在一个片段中。  
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

### 解题思路 ###

用 last\[字母\] 记录每个字母最后的位置，遍历第一个找第一个对应的字母最后出现的位置，再把start end向后移动为下一个字母，以此类推

### 代码 ###

class Solution { 
    public:
        vector<int> partitionLabels(string S) { 
            int last[26];
            int size=S.size();
            for(int i=0;i<size;i++)
            { 
                // 记录每个字母最后的位置
                last[S[i] - 'a'] = i;
            }
            vector<int> part;
            int start=0,end=0;
            for (int i = 0; i < size; i++) { 
                // 每次初始化end 使得作用到新的区间中
                end=max(end,last[S[i]-'a']);
                // 如果遍历到，第一个字母的最后一个 让该长度写入容器 并且让 start = 新的字母位置
                if (i == end) { 
                    part.push_back(end - start + 1);
                    start = end + 1;
                }
            }
            return part;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，142人围观）

还没有评论，来说两句吧...

相关阅读

相关 763. 划分字母区间

763. 划分字母区间题目：字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的

Myth丶恋晨/ 2024年04月01日 15:14/ 0 赞/ 67 阅读

相关 763.划分字母区间

763.划分字母区间题干描述解题思路总结补充代码实现题干描述 [力扣入口][Link 1] 字符串 S 由小写字母组成

绝地灬酷狼/ 2023年10月16日 15:41/ 0 赞/ 117 阅读

相关 LeetCode_贪心算法_中等_763.划分字母区间

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一

向右看齐/ 2023年10月14日 11:03/ 0 赞/ 35 阅读

相关 763. 划分字母区间（贪心算法）

763. 划分字母区间题目解题思路代码题目字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片

布满荆棘的人生/ 2023年10月05日 13:09/ 0 赞/ 13 阅读

相关 LeetCode 763. 划分字母区间 JAVA

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。示例 1：

Dear 丶/ 2022年12月17日 08:38/ 0 赞/ 125 阅读

相关 LeetCode-763划分字母区间

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

超、凢脫俗/ 2022年12月17日 07:11/ 0 赞/ 134 阅读

相关 Leetcode.763. 划分字母区间

[763. 划分字母区间][763.] 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段

我会带着你远行/ 2022年12月17日 07:03/ 0 赞/ 132 阅读

相关 OJ-leetcode-763. 划分字母区间（中等并查集）

目录题目思路代码结果更优题解提升笔记全部代码 -------------------- 题目字符串 S 由小写字母组成。我们要把这个字符

╰半夏微凉°/ 2022年12月17日 07:03/ 0 赞/ 120 阅读

相关 763. 划分字母区间

763. 划分字母区间字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。示

- 日理万妓/ 2022年11月03日 11:15/ 0 赞/ 143 阅读

相关 leecode 763 划分字母区间

前言题目：[763. 划分字母区间][763.] 参考题解：[划分字母区间-代码随想录][-] -------------------- 提交代码方法一

怼烎@/ 2022年09月15日 06:02/ 0 赞/ 120 阅读