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

关键词：

文章目录

• • 1. 题目来源
  • 2. 题目解析

1. 题目来源

链接：763. 划分字母区间

2. 题目解析

lc 讨论中看见的华为 od 面试编程题目，可以试试。

贪心思路：

• 本次分割字符串如果在后面都不出现，则单独成一段，作为有效答案。因为这样分割一定不会使答案变差。贪心思路正确。
• 维护每个字符最后出现的位置下标，从前到后遍历字符串，统计当前遍历字符串中所出现字符的最大下标值，若当前下标等于最大下标，说明已遍历的字符串中的所有字符在后续不会再次出现，则可以作为答案，计算长度即可。

坐在高铁上简单写了写，代码不够简洁。以下几点需要注意：

• 维护字符最后出现的位置
  • 可以从后向前遍历，记录第一次出现时的下标值即可
  • 可以从前向后遍历，遇见字符即记录下标，覆盖式记录，代码优雅
• 采用双指针 l, r 来维护目标区间，不用统计长度，代码更加简洁
  • 右区间 r 维护当前字符串的最大下标位置，l 维护起始位置
  • 一定会有答案，整段为答案，当前下标与最大下标位置相等时则找到一个答案。计算长度为 r-l+1，更新左区间起点 l 为 r 的下一个位置。r 不需要更新，下一个字符位置一定大于当前的 r。

---

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

class Solution 
public:
    vector<int> partitionLabels(string s) 
        int n = s.size();
        vector<int> arr(26, -1);
        for (int i = n - 1; ~i; i -- ) 
            if (arr[s[i] - 'a'] == -1) arr[s[i] - 'a'] = i;
        

        vector<int> res;
        int midx = -1, cur = 0;
        for (int i = 0; i < n; i ++ ) 
            cur ++ ;
            midx = max(arr[s[i] - 'a'], midx);
            if (i == midx) 
                res.push_back(cur);
                midx = -1;
                cur = 0;
                continue;
            
        

        return res;
    
;

较为优雅的代码实现：

class Solution 
public:
    vector<int> partitionLabels(string S) 
        int n = S.size();
        int hash[26] = 0;
        for (int i = 0; i < n; ++i) hash[S[i] - 'a'] = i;
        
        vector<int> res;
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i) 
            r = max(r, hash[S[i] - 'a']);
            if (i == r) res.push_back(r - l + 1), l = r + 1;
        
        return res;
    
;

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

...;的划分是错误的，因为划分的片段数较少。二、解题贪心算法记录每个小写字母出现的最远距离，然后遍历字符串，使用双指针，记录最远的边界end,以及开始的边界start，当遍历的字符的下标等于记录的最远... 查看详情

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

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

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

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

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

这个题第一次做会感觉特别难，无从下手，或者想的很复杂，但其实特别特别简单的方法就能解决。LeetCode763.字符串S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中... 查看详情

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

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

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

 方法一：滑动窗口classSolutionpublicList<Integer>partitionLabels(Strings)List<Integer>res=newArrayList<>();int[]arr=newint[128];for(charc:s.toCharArray())arr[c]++;int[]window=newint 查看详情

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

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

[m贪心]lc524.通过删除字母匹配到字典里最长单词(排序+判断子序列)(代码片段)

文章目录1.题目来源2.题目解析1.题目来源链接：524.通过删除字母匹配到字典里最长单词2.题目解析首先字母一定不能比字典的字母长度还短，那么一定不是子序列。其次要去一个长度最长且字典序最小的字典中的，满... 查看详情

[m贪心]lc881.救生艇(贪心+贪心证明)(代码片段)

...析1.题目来源链接：881.救生艇2.题目解析常规的一道贪心，思路很简单，关键仍旧是贪心思路的证明。思路：排序，尽量让重的和轻的组成一个救生艇。即，每次都会将末尾最终的安排掉。注意可能会造成i... 查看详情

[m贪心]lc881.救生艇(贪心+贪心证明)(代码片段)

...析1.题目来源链接：881.救生艇2.题目解析常规的一道贪心，思路很简单，关键仍旧是贪心思路的证明。思路：排序，尽量让重的和轻的组成一个救生艇。即，每次都会将末尾最终的安排掉。注意可能会造成i... 查看详情

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

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

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

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

[m二分]lc1818.绝对差值和(二分+贪心失败+好题)(代码片段)

...对差值和2.题目解析二分题目，中等意思。首先，贪心思路的大失败…一开始想的是找到绝对值差最大的数对，将其替换成最小即可。错误样例[1,28,21][9,21,20]9，贪心思路是万万行不通的…貌似周赛比赛时贪心竟然... 查看详情

[m贪心]lc524.通过删除字母匹配到字典里最长单词(排序+判断子序列)(代码片段)

文章目录1.题目来源2.题目解析1.题目来源链接：524.通过删除字母匹配到字典里最长单词2.题目解析首先字母一定不能比字典的字母长度还短，那么一定不是子序列。其次要去一个长度最长且字典序最小的字典中的，满... 查看详情

[m贪心]lc1877.数组中最大数对和的最小值(贪心+双周赛53_2)(代码片段)

...ff1a;1877.数组中最大数对和的最小值2.题目解析比较好猜的贪心，最大和最小作为数对，一定和最小。证明：贪心方式：从小到大排序，首尾组合作为数对。反证法，如果一个最优解不是首尾组合的，设... 查看详情

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

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

[m数学]lc1802.有界数组中指定下标处的最大值(贪心+二分+数学推公式)(代码片段)

...ff1a;1802.有界数组中指定下标处的最大值2.题目解析直觉的贪心思路，证明看官方题解吧。至于数学思路也推荐看官方题解，一开始确实想着推公式的，最后没走下去。贪心思路：让index值最大，剩余两边依次递... 查看详情

[m贪心]lc1353.最多可以参加的会议数目(扫描线+stl优先队列)(代码片段)

...1353.最多可以参加的会议数目精选题解：扫描算法+贪心2.题目解析只是本题比较像扫描线，并不是扫描线的经典应用。每个时间点只会参加一次会议，所以可以按照天数从1~MAX开始扫描，即扫描每个时间点。如... 查看详情