关键词:
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例 1:
输入:S = "ababcbacadefegdehijhklij" 输出:[9,7,8] 解释: 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的,因为划分的片段数较少。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/partition-labels
思路:
在这串字符串中,开头为a,找到的区间至少结尾为最后一个a
但是中间会出现一些干扰元素,比如b,而如果b在上面找到的结尾a的前面那就无所谓
如果在后面则要更新当前结尾为a的区间范围,一直包含到最后结尾为b的区间处
所以对于每一个字符都必须先找到最后结尾的位置的下标处并记录下来
再两个变量,一个用来更新区间,一个用来记录下标位置
class Solution public List<Integer> partitionLabels(String S) //定义一个数组,用来存储每个字符最后出现的位置下标 int[] last = new int[26]; for (int i = 0; i < S.length(); i++) last[S.charAt(i) - ‘a‘] = i; //记录完了之后需要两个变量,一个用来更新区间,一个用来记录新区间的下标 int j = 0, count = 0; //定义一个List用来存放分割出来的区间并返回 List<Integer> arr = new ArrayList<>(); for (int i = 0; i < S.length(); i++) j = Math.max(j,last[S.charAt(i) - ‘a‘]); //如果i = j 则说明这段区间这就是要找的区间 if ( i == j) arr.add(i - count + 1); count = i + 1; return arr;
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]解释... 查看详情
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标记就可以实现优化。对比一下一维和二维线段树划分区间的思路:一维线段树划分区间思路: 查看详情