关于leetcode:leetcode-763-Partition-Labels-划分字母区间中等

29次阅读

共计 1198 个字符，预计需要花费 3 分钟才能阅读完成。

标签: 贪婪

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

字符串 S 由小写字母组成。咱们要把这个字符串划分为尽可能多的片段，同一字母最多呈现在一个片段中。返回一个示意每个字符串片段的长度的列表。

示例：

输出：S = “ababcbacadefegdehijhklij”
输入：[9,7,8]
解释：
划分后果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多呈现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是谬误的，因为划分的片段数较少。

提醒：

S 的长度在 [1, 500] 之间。
S 只蕴含小写字母 ‘a’ 到 ‘z’。

二、解题思路

一个字符串 S，将其尽可能多的宰割为子字符串，条件是每种字符最多只能呈现在一个子串中。下面的示例中，字符串 S 中有多个 a，这些 a 必须只能在第一个子串中，字母 e 呈现在第二个子串中。这道题难点就是如何找到字符串的断点，即拆分成为子串的地位。察看上述例子，一旦某个字母屡次呈现，那么其最初一个呈现地位必须要在以后子串中，字母 a，e，j 别离是三个子串中的完结字母。所以咱们关注的是每个字母最初的呈现地位，咱们能够应用一个 Map 来建设字母和其最初呈现地位之间的映射，建设好映射之后，就须要开始遍历字符串 S，咱们保护一个 start 变量，是以后子串的起始地位，还有一个 last 变量，是以后子串的完结地位，每当咱们遍历到一个字母，须要在 Map 中提取出其最初一个地位，因为一旦以后子串饮食了一个字母，其必须饮食所有的雷同字母，所以咱们要不停的用以后字母的最初一个地位来更新 last 变量，只有当 i 和 last 雷同了，即 i =last 时，以后子串饮食了所有已呈现过的字母的最初一个地位，即之后的字符串不会有之前呈现过的字母了，此时就应该是断开的地位，咱们将子串长度退出到后果中。

三、解题办法

3.1 Java 实现
```
public class Solution {public List<Integer> partitionLabels(String s) {Map<Character, Integer> map = new HashMap<>();
      char[] cArr = s.toCharArray();
      for (int i = 0; i < cArr.length; i++) {map.put(cArr[i], i);
      }

      List<Integer> res = new ArrayList<>();
      int start = 0;
      int last = 0;
      for (int i = 0; i < cArr.length; i++) {last = Math.max(map.get(cArr[i]), last);
          if (i == last) {res.add(last - start + 1);
              start = last + 1;
          }
      }

      return res;
  }
}
```
四、总结小记
2022/7/28 把思路理清了，代码就牵强附会进去了