2025年- H78-Lc186--763.划分字符串区间(贪心）--Java版

1.题目描述

2.思路

（1)存储子串的索引和该字符出现的最远位置

3.代码实现

class Solution {public List<Integer> partitionLabels(String s) {//初始化一个字母索引的数组，总共26个字母int[] letterIndex=new int[26];//把每个字母出现的最远下标进行标记。用assii码计算for(int i=0;i<s.length();i++){//Java 中字符串 s 不能像数组 s[i] 那样访问字符，应该使用 s.charAt(i)。letterIndex[s.charAt(i)-'a']=i;//例子：比如可以得到每个a的索引，最终最远的a会将起始a覆盖。}int n=s.length();//遍历字符串，寻找区间的分割点List<Integer> result=new ArrayList<>();//定义左右指针int left=0;int right=0;for(int i=0;i<s.length();i++){//不断更新右边界，取一个最大值right=Math.max(right,letterIndex[s.charAt(i)-'a']);//当我们遍历到最远处的时候if(i==right){//result数组里面存放区间的长度result.add(right-left+1);//更新left指针，找下一个区间,也就是right边界右邻居left=i+1;}}//最后返回结果数组。return result; }
}