正文

763.划分字母区间(代码片段)

我要出家当道士  我要出家当道士  2022-12-06  307

关键词：

1、Question

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

示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

2、Analysis

如上图所示，这题划分字符串，使得每个子串中的字母都不会再出现在其它子串中。

我们可以记录每个字母的区域范围，字母的区域范围可能会重叠，对于区域重叠的字母我们将其归类到一个子串中。最终的结果就是求得字符串中存在多少独立的不重叠的区域的长度。

这题和 452 类似

452.用最少数量的箭引爆气球_我要出家当道士的博客-CSDN博客https://blog.csdn.net/qq_37437983/article/details/124892972?spm=1001.2014.3001.5501

3、Code

夜深了，脑子有点乱，代码也有点乱，不过逻辑还是挺清晰的。确定字母范围可以用数组做hash快速索引，不然用两层循环性能会稍低。

class Solution 
public:
    vector<int> partitionLabels(string s)
    
        vector<int> res;
        int positions[26][2] = 0, words_flat[26] = 0;
        int flat_cur = 0, com_start = s[0] - 'a';
        // 确认每个字母的范围
        for (int i = 0; i < s.length(); i++)
        
            int position = s[i] - 'a';
            int flat = words_flat[position];
            if (flat == 0 && (position != com_start || i == 0))
            
                positions[flat_cur][0] = i;
                positions[flat_cur][1] = i;
                words_flat[position] = flat_cur;
                flat_cur++;
            
            else
            
                positions[flat][1] = i;
            
        
        // 确认独立区域
        int cur_start = positions[0][0], cur_end = positions[0][1];
        for (int i = 1; i < flat_cur; i++)
        
            if (positions[i][0] > cur_end)
            
                res.push_back(cur_end - cur_start + 1);
                cur_end = positions[i][1];
                cur_start = positions[i][0];
                continue;
            
            if (positions[i][1] > cur_end)
            
                cur_end = positions[i][1];
            
        
        res.push_back(s.length() - cur_start);
        return res;
    
;

4、Result

763.划分字母区间(代码片段)

... 字符串S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。示例：输入：S="ababcbacadefegdehijhklij"输出：... 查看详情

leetcode763.划分字母区间贪心策略：局部最优大区间划分(代码片段)

...的信息。解题思路：贪心策略：局部最优大区间划分，只不过这次是根据字母的最后一次出现的位置确定区间的最大值，因为字母是无规律分部，所查看详情

[m贪心]lc763.划分字母区间(贪心+代码实现)(代码片段)

文章目录1.题目来源2.题目解析1.题目来源链接：763.划分字母区间2.题目解析lc讨论中看见的华为od面试编程题目，可以试试。贪心思路：本次分割字符串如果在后面都不出现，则单独成一段，作为有效答案。因... 查看详情

763.划分字母区间(代码片段)

字符串S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。示例1:输入:S="ababcbacadefegdehijhklij"输出:[9,7,8]解释:划分结果为&qu... 查看详情

763.划分字母区间-贪心算法(代码片段)

...题目描述字符串S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。示例1：输入：S="ababcbacadefegdehijhklij"输出：[... 查看详情

leetcode763.划分字母区间贪心策略：局部最优大区间划分(代码片段)

...的信息。解题思路：贪心策略：局部最优大区间划分，只不过这次是根据字母的最后一次出现的位置确定区间的最大值，因为字母是无规律分部，所以区间的最大值会跳跃性增加，不在是+1递增等规律递... 查看详情

力扣算法jslc[435.无重叠区间]lc[763.划分字母区间]

菜鸡刷算法的一天，每天分享两题算法，大家有这个想法的，可以给我个关注，然后一起坚持每天的算法之旅。希望我们共同进步，一起加油。菜鸡刷算法的一天，每天分享两题算法，大家有这个想法的，可以给我个关注，然后... 查看详情

2021-12-24：划分字母区间。字符串s由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。力扣763。某大厂面试(代码片

2021-12-24：划分字母区间。字符串S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。力扣763。某大厂面试题。答案2021-12-24：... 查看详情

leetcode763.partitionlabels划分字母区间(中等)

一个字符串S，将其尽可能多的分割为子字符串，条件是每种字符最多只能出现在一个子串中。上面的示例中，字符串S中有多个a，这些a必须只能在第一个子串中，字母e出现在第二个子串中。这道题难点就是如何找到字符串的断... 查看详情

贪心热门问题8：划分字母区间(代码片段)

...LeetCode763.字符串S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。输入：S="ababcbacadefegdehijhklij"输出：[9,7,8]解释&#x... 查看详情

java求解划分字母区间(代码片段)

...一、题目字符串S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。二、题解在遍历的过程中相当于是要找每一个字母的边界，... 查看详情

leetcode刷题笔记-数据结构-day7(代码片段)

...-数据结构-day790.单词规律1.题目描述2.解题思路3.代码763.划分字母区间1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day790.单词规律1.题目描述原题链接：90.单词规律2.解题思路算法：哈希表用两个哈希表：一个... 查看详情

时分时间划分到不同时间区间段，python(代码片段)

用Python实现一个功能，把一个时间划入到不同的时间范围内，比如23:05，把这个时间划入到(23,24)区间内。又比如0:56，划入（0,1）范围内。importdatetimeimportrandom#生成随机测试时间数量TIME_COUNT=20defmy_time():ti... 查看详情

将数据划分为训练集和测试集；缩放特征区间(代码片段)

导入葡萄酒数据：1importnumpyasnp2importpandasaspd34df_wine=pd.read_csv("https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data",header=None)5df_wine.columns=["classlabel","alcohol",6"malicac 查看详情

763.partitionlabels(代码片段)

题目描述：Astring S oflowercaselettersisgiven.Wewanttopartitionthisstringintoasmanypartsaspossiblesothateachletterappearsinatmostonepart,andreturnalistofintegersrepresentingthesizeoftheseparts.&n 查看详情

763.partitionlabels(贪心)(代码片段)

AstringSoflowercaselettersisgiven.Wewanttopartitionthisstringintoasmanypartsaspossiblesothateachletterappearsinatmostonepart,andreturnalistofintegersrepresentingthesizeoftheseparts.Example1:Input:S="a 查看详情

1.快速排序(代码片段)

...找到一个数作为分界点x。（q[l],q[(l+r)/2],q[r],随机值）2：划分区间。使得左区间里的数都小于等于x，右区间里的数都大于等于x。快速排序是选择一个数来划分区间。3：递归处理左右两区间。左区间排好序，右区间排好序后再拼... 查看详情

二维线段树(代码片段)

...lazytag标记就可以实现优化。对比一下一维和二维线段树划分区间的思路：一维线段树划分区间思路：查看详情