java算法题解Leetcode763划分字母区间示例

下面是“java算法题解Leetcode763划分字母区间示例”的完整攻略。

题目描述

给定一个仅包含小写字母的字符串 S，将字符串 S 划分为尽可能多的区间，使得每个字母最多出现在一个区间中，求区间的个数。

解题思路

首先，我们可以使用hashmap记录每个字母最后出现的位置，然后使用两个指针，分别记录当前合法区间的左右端点。

接着，我们遍历字符串S，记录当前字符最后出现的位置，如果当前下标等于右端点下标，说明当前区间中没有重复的字符，可以将区间划分出来并将左端点置为右端点的下一个位置，继续向后遍历。

例如，针对字符串"ababcbacadefegdehijhklij"，我们可以这样进行划分：

1. 我们先使用hashmap记录每个字母最后出现的位置，得到{"a":8, "b":5, "c":7, "d":14, "e":15, "f":11, "g":13, "h":19, "i":22, "j":23, "k":20, "l":21}
2. 然后我们设置左端点和右端点都为0，开始遍历字符串S
3. 遍历到S[0]='a'，更新右端点为8
4. 遍历到S[1]='b'，更新右端点为5
5. 此时右端点等于下标1，说明当前区间中没有重复的字符，将当前区间划分出来，得到"ab"，并将左端点置为2，继续向后遍历
6. 遍历到S[2]='a'，更新右端点为8
7. 此时右端点大于下标2，继续遍历
8. 遍历到S[3]='b'，更新右端点为5
9. 此时右端点等于下标3，说明当前区间中没有重复的字符，将当前区间划分出来，得到"ab"，并将左端点置为4，继续向后遍历
10. 遍历到S[4]='c'，更新右端点为7
11. 此时右端点等于下标4，说明当前区间中没有重复的字符，将当前区间划分出来，得到"abc"，并将左端点置为5，继续向后遍历
12. 类似以上步骤，最后得到划分出的区间为["ababcbaca", "defegde", "hijhklij"]，共有3个区间

代码实现

下面是使用Java进行实现的代码，基于上述思路进行编写：

public List<Integer> partitionLabels(String S) {
    if (S == null || S.length() == 0) {
        return new ArrayList<>();
    }
    int n = S.length();
    int[] map = new int[26];
    for (int i = 0; i < n; i++) {
        map[S.charAt(i) - 'a'] = i;
    }
    List<Integer> res = new ArrayList<>();
    int start = 0, end = 0;
    for (int i = 0; i < n; i++) {
        end = Math.max(end, map[S.charAt(i) - 'a']);
        if (i == end) {
            res.add(end - start + 1);
            start = end + 1;
        }
    }
    return res;
}

示例运行

我们将以上代码放入IDE中运行，针对字符串"ababcbacadefegdehijhklij"，得到的输出为[9, 7, 8]，说明共有3个区间，分别为"ababcbaca"、"defegde"和"hijhklij"。针对字符串"aabbccdd"，得到的输出为[2, 2, 2, 2]，说明共有4个区间，分别为"aa"、"bb"、"cc"和"dd"。

总结

本题的解题思路主要依据贪心算法，使用hashmap记录每个字符最后出现的位置，遍历字符串并不断更新右端点，当右端点等于下标时，说明当前区间中没有重复字符，可以对区间进行划分。通过以上实例讲解，我们可以更好地理解和掌握题目的解法。