一、题目粗心

标签: 贪婪

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 把思路理清了，代码就牵强附会进去了