LeetCode Hot100刷题——划分字母区间

763.划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

---

思路分析

题目要求：将字符串划分为尽可能多的片段，使得每个字母只出现在一个片段中，并返回每个片段的长度列表。

1. 同一个字母最多只能出现在一个片段中，那么同一个字母的第一次出现和最后一次出现的位置必须在同一片段。
2. 因此，需要记录每个字母在字符串中最后出现的位置（因为第一次出现的位置可以通过遍历顺序知道，但更重要的是最后出现的位置）
3. 使用贪心策略：遍历字符串，对于当前字符，需要知道当前字符最后出现的位置，这样就能知道当前片段至少应该覆盖到这个位置。
4. 具体步骤：

        a. 首先，遍历字符串，记录每个字符最后出现的位置，保存在一个数组或哈希表中（因为只有小写字母，可以用长度为26的数组）。

        b. 然后，再次遍历字符串，同时维护两个变量：当前片段的开始位置（start）和当前片段结束位置（end，初始为0）。

        c. 对于每个遍历到的字符，更新当前片段的结束位置为当前字符最后出现位置和当前end的最大值（即end = max(end, lastOccurrence[currentChar])）。

        d. 当遍历到当前片段的结束位置（即当前位置 i 等于end）时，说明当前片段已经可以结束（因为从start到end之间的所有字符的最后出现位置都不会超过end，所以可以独立成一个片段）。

        e. 计算当前片段的长度（end - start + 1），并将该长度加入结果列表，然后更新下一个片段的开始位置为end+1。

        5. 重复上述过程直到字符串结束。

---

算法步骤

1. 创建一个一个数组last，长度为26，记录每个字符最后出现的位置。
2. 遍历字符串，对于每个字符s.charAt(i)，更新last[s.charAt(i) - 'a'] = i。
3. 初始化start=0，end=0，以及一个空列表result用于存放每个片段的长度。
4. 再次遍历字符串（i从0到n-1）：
   1. end = Math.max(end, last[s.charAt(i)-'a'])
   2. 如果i == end，说明当前片段结束，将当前片段的长度（end - start + 1）加入结果列表，然后更新start为 end + 1（准备下一个片段）。
5. 返回结果列表。

注意：为什么不需要在开始新片段时重置end？因为end在每次更新时都是取最大值，而新片段开始的位置是上一个片段结束位置之后，所以新片段中的字符的最后位置一定大于等于当前i（即start），所以end会被更新为当前片段中所有字符最后出现位置的最大值。

---

程序代码

class Solution {public List<Integer> partitionLabels(String s) {//记录每个字母的最后出现位置int[] lastOccurrence = new int[26];int n = s.length();for(int i = 0; i < n; i++){char c = s.charAt(i);lastOccurrence[c - 'a'] = i;}List<Integer> result = new ArrayList<>();int start = 0;  // 当前片段的起始位置int end = 0;    // 当前片段的结束位置for(int i = 0; i < n; i++){char c = s.charAt(i);// 更新当前片段的结束位置end = Math.max(end, lastOccurrence[c - 'a']);// 当遍历到结束位置时，当前片段结束if(i == end){result.add(end - start + 1);    // 记录片段长度start = end + 1;    // 开始下一个片段}}return result;}
}

1. 记录最后位置：

   • 创建长度26的数组 lastOccurrence，对应小写字母的最后出现位置。

   • 遍历字符串，更新每个字符的最后位置。

2. 划分片段：

   • 初始化 start = 0 和 end = 0。

   • 遍历字符串，对于每个字符：

     • 更新 end 为当前字符最后位置和当前 end 的最大值。

     • 当 i == end 时，说明当前片段满足条件（所有字符的最后位置均不超过 end）。

     • 记录片段长度 end - start + 1，更新 start = end + 1。

3. 示例分析（以示例1为例）：

   • 字符串 s = "ababcbacadefegdehijhklij"。

   • 最后位置记录：a:8, b:5, c:7, d:14, e:15, f:11, g:13, h:19, i:22, j:23, k:20, l:21。

   • 遍历过程：

     • i=0（字符'a'）：end = max(0, 8) = 8。

     • i=1（字符'b'）：end = max(8, 5) = 8。

     • 继续遍历直到 i=8：end = 8，记录片段长度 8-0+1=9，更新 start=9。

     • i=9（字符'd'）：end = max(8, 14) = 14。

     • i=10（字符'e'）：end = max(14, 15)=15。

     • 继续直到 i=15：记录片段长度 15-9+1=7，更新 start=16。

     • i=16（字符'h'）：end = max(0, 19)=19（注意：end 继承自上一片段）。

     • 继续遍历更新 end 到23，i=23 时记录片段长度 23-16+1=8。

   • 输出结果 [9,7,8]。

补充：charAt()方法用于返回指定索引处的字符。索引范围从0到length() - 1。

为什么在 lastOccurrence 数组中使用 c - 'a'？

在Java中，字符是用Unicode编码表示的。小写字母'a'到'z'在Unicode中是连续的，因此我们可以通过将字符减去'a'来得到一个0到25的索引值，这样我们就可以用一个长度为26的数组来存储每个小写字母的信息。

具体来说：

- 字符'a'的ASCII码是97，那么`'a' - 'a'`等于0，对应数组的第0个位置。

- 字符'b'的ASCII码是98，那么`'b' - 'a'`等于1，对应数组的第1个位置。

- 以此类推，字符'z'的ASCII码是122，那么`'z' - 'a'`等于25，对应数组的第25个位置。

这样，我们就可以用一个长度为26的数组（索引0到25）来存储每个小写字母的最后出现位置。这是一种常见且高效的处理小写字母映射的方法。