题解 | #分品种# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型一维数组
     */
    public int[] partitionLabels (String s) {
        // write code here
        int[] lastOccurrence = new int[26]; // 记录每个字母最后出现的位置
        for (int i = 0; i < s.length(); i++) {
            lastOccurrence[s.charAt(i) - 'a'] = i;
        }

        List<Integer> partitions = new ArrayList<>();
        int start = 0; // 当前片段的起始位置
        int end = 0;   // 当前片段的结束位置

        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, lastOccurrence[s.charAt(i) -
                                               'a']); // 更新当前片段的结束位置
            if (i == end) {
                partitions.add(end - start + 1); // 当前片段结束，加入结果列表
                start = end + 1; // 更新下一个片段的起始位置
            }
        }

        int[] result = new int[partitions.size()];
        for (int i = 0; i < partitions.size(); i++) {
            result[i] = partitions.get(i);
        }

        return result;
    }
}

使用 Java 编程语言。

该题考察了以下知识点：

1. 字符串操作
2. 贪心算法
3. 列表操作

代码的文字解释如下：

• 创建一个长度为 26 的整数数组 lastOccurrence，用于记录每个字母的最后出现位置。
• 遍历输入字符串 s，更新 lastOccurrence 数组中每个字母对应的最后出现位置。
• 创建一个空的整数列表 partitions，用于存储片段的长度。
• 初始化 start 和 end 为 0，表示当前片段的起始位置和结束位置。
• 第二次遍历字符串 s，在每个字符处，更新 end 为当前字符的最后出现位置和 end 中的较大值。
• 如果当前索引 i 等于 end，说明当前片段结束，计算片段的长度为 end - start + 1，将长度添加到 partitions 列表中。
• 更新 start 为 end + 1，为下一个片段的起始位置。
• 将列表 partitions 中的元素转化为数组，并返回结果。