leetcode 763.划分字母区间（Java 贪心）

发布时间：2020-12-15 07:42:23 所属栏目：Java 来源：网络整理

导读：https://leetcode-cn.com/problems/partition-labels/submissions/ 划分字母区间，使同一个字母只能出现在一个区间。贪心解决。 class Solution { public ListInteger partitionLabels(String S) { List Integer ans= new ArrayList(); // 储存结果 int []

https://leetcode-cn.com/problems/partition-labels/submissions/

划分字母区间，使同一个字母只能出现在一个区间。

贪心解决。

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> ans=new ArrayList<>();  //储存结果
        int[] map=new int[26];//记录每个字母出现位置的最大值
        for(int i=0;i<S.length();i++){//记录每个字母出现位置的最大值
            map[S.charAt(i)-‘a‘]=i;
        }
        int start=-1,end=0;//start记录每一区间的首字母的前一个位置，第一段首字母位置一定是0
        for(int i=0;i<S.length();i++){
            end=Math.max(end,map[S.charAt(i)-‘a‘]);//不断更新末尾指针 if(end==i){
                ans.add(end-start);
                start=end;
            }
        }
        return ans;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!