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

一、题目粗心

标签: 贪婪

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