Java实现 LeetCode 763 划分字母区间(暴力)
2024-10-09 04:29:35
763. 划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例 1:
输入: S = “ababcbacadefegdehijhklij”
输出: [9,7,8]
解释:
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的,因为划分的片段数较少。
注意:
S的长度在[1, 500]之间。
S只包含小写字母’a’到’z’。
class Solution {
public List<Integer> partitionLabels(String S) {
boolean[] flag = new boolean[S.length()];
List<Integer> list = new ArrayList<>();
int begin = 0;
while(begin<S.length()){
int end = begin;
for(int i=begin;i<=end;i++){
if(flag[i]){
continue;
}
int last = lastIndex(S, i, flag);
end = last>end?last:end;
}
list.add(end-begin+1);
begin = end+1;
}
return list;
}
private int lastIndex(String S, int begin, boolean[] flag){
int cur = begin, precur = -1;
while(cur!=-1){
precur = cur;
flag[precur] = true;
cur = S.indexOf(S.charAt(begin), cur+1);
}
return precur;
}
}
最新文章
- iOS Swift-注释与分号
- ListView的联动实现
- TFS 改服务器IP 域名 端口方法
- jQuery常规选择器
- Git基础(一)
- DataTable导入到Excel文件
- 【转】onPrepareOptionsMenu 和onCreateOptionsMenu 的区别
- 序列化TList of objects(摘自danieleteti的网站)
- centos 7 yum方式安装MySQL 5.6
- wrapper induction随笔
- std::bind 的使用说明
- 第26月第3天 java gradle
- Mapreduce atop Apache Phoenix (ScanPlan 初探)
- Python3学习之路~0 目录
- 【python011--数组2】
- 第8月第15天 app支持后台播放
- 写带有清晰图片的博客:如何将word中的图片复制到windows live writer保持大小不变--清晰度不变
- [Command] lrzsz - 文件传输工具包
- Android获取网络图片应用示例
- 【Unity】同时打开多个项目工程