题解 | #分品种# java
分品种
https://www.nowcoder.com/practice/9af4e93b04484df79d4cc7a863343b0b
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, 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; } }
ava 编程语言编写的。
知识点:字符串处理、贪心算法
代码的文字解释:
使用 lastOccurrence
数组记录每个字符最后出现的位置。然后,通过遍历字符串,使用窗口的方式来确定分组的结束位置。当窗口内的字符都在同一个分组中时,当前位置即为一个分组的结束点。我们记录该分组的长度,并更新窗口的起始位置。最后,将分组长度信息存储在整数数组中并返回。