划分字母区间问题
2023-02-18 16:36:42 时间
划分字母区间问题
作者:Grey
原文地址:
题目描述
LeetCode 763. Partition Labels
思路
显然,如果整个字符串无重复值,那么字符串的字符个数就是最多划分的区间个数。
如果有重复值,假设a
字符有重复,那么所有的a
必须划分到同一个区间内,否则a
分布不同区间的话,就不满足题目要求了。
同理,其他字符也是类似的逻辑。
我们的整体流程是从左往右遍历字符,当遍历到一个字符的时候,我们需要快速知道这个字符在字符串后续位置是哪里,这样才能知道这个字符串至少应该从哪里开始切。
例如:abdtydfsdfdasbsssrr
这个字符串,当遍历到第一个a
时候,我们需要马上知道整个字符串后续是否还有a
这个字符,此例子中,在字符串的11位置确实还有一个字符a
。
设置一个right
变量,用于记录当前刀最少要切到的位置,
如上例,当遍历到第一个a
字符以后,可以判断第一刀至少要切到11
位置,right
记录为11
,
至于后续是否还需要继续扩散,要继续遍历下一个字符b
,如果整个字符串中最右边的b
字符没有超过11
位置,则第一刀可以继续保持到11
位置来切,
如果整个字符串中的b
的最右位置超过了11
,如此例,最右边的b
出现在13
位置,那么第一刀位置就要从11
扩散到13
位置,right
记录为13
如果遍历到某个字符串的最右边位置正好是right
,则可以开始从这个位置切一刀了。
以此类推,直到遍历完整个字符串。
根据以上流程,我们需要对数组进行一次预处理,即,记录每个字符串出现的最右位置,由于题目限定是小写字母,所以可以通过如下方式来保存每个字符的最右位置
int[] help = new int[26];
for (int i = 0; i < str.length; i++) {
help[str[i] - 'a'] = i;
}
主流程代码
int right = 0;
int pre = right;
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < str.length; i++) {
// 是否可以将right位置扩散
right = Math.max(right, help[str[i] - 'a']);
if(i == right) {
// 当前位置已经是能扩散的最右位置了
// 收集答案
ans.add(right - pre + 1);
pre = right + 1;
}
}
return ans;
pre
记录上一刀的位置,便于求每个区间的长度(题目要求), 当前遍历到的位置i
如果正好是目前区间能扩散的最右位置right
,则结算。
完整代码如下
class Solution {
// 统计每一个字符最后出现的位置
// 从头遍历字符,如果找到之前字符最大出现位置下标和当前下标相等,则找到了分割点
public static List<Integer> partitionLabels(String s) {
char[] str = s.toCharArray();
// help收集每个字符最右位置
int[] help = new int[26];
for (int i = 0; i < str.length; i++) {
help[str[i] - 'a'] = i;
}
int right = 0;
int pre = right;
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < str.length; i++) {
// 是否可以将right位置扩散
right = Math.max(right, help[str[i] - 'a']);
if (i == right) {
// 当前位置已经是能扩散的最右位置了
// 收集答案
ans.add(right - pre + 1);
pre = right + 1;
}
}
return ans;
}
}
更多
相关文章
- SQL语句练习实例之八——对于销售员提成收入的计算
- [linux]centos安装宝塔面板
- [linux] linux宝塔面板安装GOFLY开源客服
- [docker] win10 docker桌面版镜像源
- [docker]解决:docker桌面版报错error during connect: This error may indicate that the docker daemon is not running
- [正则]正则表达式里面的?: ?! ?= ?<=
- 三连冠!腾讯Angel PowerFL联队斩获iDASH-2022隐私计算大赛同态加密赛道冠军
- 宝塔面板12.7(或更早)高危漏洞
- 在web页面中水晶报表显示速度过慢的原因
- 10年经验总结,华为fellow教你如何成为一名优秀的架构师?
- CANN5.0黑科技解密 | 高并发图片视频处理,为出行保驾,为生活添彩!
- 为啥你写的代码老有大串的if/else?
- 全链路数据血缘在满帮的实践
- 解析云原生2.0架构设计的8大关键趋势
- 万字详解什么是生成对抗网络GAN
- 基于MRS-Hudi构建数据湖的典型应用场景介绍
- 华为云首席架构师顾炯炯:敢为人先,探索架构创新之路如何走
- TCP的慢启动、拥塞避免、重传、快恢复乱七八糟总是记不清?11个连环问让你一次性打通任督二脉
- 计划会议想开好,这两件事必须清楚
- 漏洞检测方法如何选?详解源代码与二进制SCA检测原理