力扣763-分别字母区间(Java具体题解)
题目链接：763. 分别字母区间 - 力扣（LeetCode）前情提要：
因为本人近来都来刷贪婪类的题目所以该题就默认用贪婪方法来做。
贪婪方法：局部最优推出全局最优。
如果一个题你觉得可以用局部最优推出全局最优，并且没有反例来反驳的话就可以用贪婪来试试。
题目思路：
其实这个题入手很快，本题要求将字符划尽大概多的分为片段。其实贪婪就贪在，我们要找到尽大概长度小的片段。
局部最优：根据范围来得到最小的片段。
全局最优：得到尽大概多的片段。
那么我们怎么找呢？题目要求不同片段内，同一字母只能出现一次。
其实这题跟力扣55-跳跃游戏有点像。
题目链接：55. 跳跃游戏 - 力扣（LeetCode） 题解链接： 力扣55-跳跃游戏（java具体题解）-CSDN博客
如有须要，请自取。
我们可以将每一个字母所出现的最大下标位置给求出，然后遍历该字符串，并在原来的最大范围内并扩大该范围，只有该范围不能再扩大了（即遍历到该片段的最大范围），那么这时求的就是最小的字符片段。
举个例子。
https://i-blog.csdnimg.cn/direct/83eccbbf477a4417a9d1d805f6647255.png#pic_center
那么肯定就有人想，我们不是要求最小的片段吗，那这个片段的范围不是越小越好吗？怎么要求最大范围。
如果不如许，固然你的片段范围是小了，但是你的这个片段并不符合题意，题目要求不同片段内，同一字母只能出现一次。
你只有将该片段内的最大的字母下标位置确定下来，你才能确定该片段内所有的字母不会出现在其他的片段内。
核心思路就是要维护一个最大的边界范围，确定他的停止位置。
最终代码：
class Solution {
public List<Integer> partitionLabels(String s) {
//该题我们要寻找字符串尽可能多的片段，怎么求呢？
//只要知道我们当前字母的最大范围，然后在我们的这个范围内再不断的扩大我们这个范围，只到我们不能再扩大了,那么我们就得到了这样一个最小的字符片段。
//局部最优：根据范围来获得最小的片段
//全局最优：获得尽可能多的片段
int [] hashArr = new int ;
List<Integer> result = new ArrayList<>();
//利用哈希思想，让每一个数组下标跟字母做映射，给每一个字母得出最大的位置下标
for(int i = 0;i < s.length();i ++){
hashArr = i;
}
//在这里我们用双指针来获取每一个片段的长度
//left记录起始位置 right记录终止位置
int left = 0,right = 0;
for(int i = 0;i <s.length();i ++){
//首先 我们移动终止位置，知道终止位置移动到我们这个片段的最大下标位置就停止，收集结果
//并让下一段起始位置移动到上一段终止位置的下一个
right = Math.max(hashArr,right);
if(right == i){
result.add(right - left + 1);
left = i + 1;
}
}
return result;
}
}
这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，大概私信我。
我很乐意为你解答。那么我们下篇再见！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]