题解 | #分品种#

知识点

贪心

解题思路

这道题的意思是每一组出现的单词字符不能在其他组出现，并且还需要将字符串s划分成尽可能多的组，返回每组字符串长度的数组。

为了解决这个问题，我们可以使用贪心算法。首先，我们需要统计每个字母在字符串中最后一次出现的位置。然后，我们可以遍历字符串，维护一个当前分组的结束位置。当遍历到一个字符时，我们更新当前分组的结束位置为该字符的最后一次出现位置和当前分组的结束位置中的较大值。如果当前位置遍历到了当前分组的结束位置，说明当前分组已经遍历完毕，我们将当前分组的长度添加到结果列表中，并将当前位置作为下一个分组的开始位置。最后，返回结果列表。

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> result = 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) {
                result.add(end - start + 1);
                start = end + 1;
            }
        }
        // 将结果列表转换为数组
        int[] partitions = new int[result.size()];
        for (int i = 0; i < partitions.length; i++) {
            partitions[i] = result.get(i);
        }
        return partitions;
    }
}