763. 划分字母区间

2020-04-30

LeetCode

双指针, 贪心

7 分钟读完 (大约 1064 个字) 0次访问

leetcode 763. 划分字母区间

题目：763. 划分字母区间

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

示例:

输入：S = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释:

划分结果为 “ababcbaca”, “defegde”, “hijhklij”。

每个字母最多出现在一个片段中。

像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

提示:

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

方法一：双指针（对撞指针）

思路：双指针（对撞指针），将需要划分的字符串装换成字符数组，从左到右遍历数组，假设遍历的第一个字符为’a’，再从右到左遍历数组，找到’a’最后出现的位置，依次类推找每一个字符的最后出现位置，并记录最远的字符位置，直到从左到右遍历到了当前记录的最远位置，此位置即为第一段字符串的结束位置，接着按照此方法继续找下一段字符串的结束位置。

运行数据：执行用时：10 ms，内存消耗：38.4 MB

// LeetCode指定调用方法
public List<Integer> partitionLabels(String S) {

    // 记录结果
    List<Integer> list = new ArrayList<Integer>();

    // 将需要划分的字符串转成字符数组
    char[] chars = S.toCharArray();

    // 记录字符数组chars的长度
    int charsLen = chars.length;

    // 记录当前这一段字符串最远字符位置
    int index = 0;

    // 记录前一段字符串的结束位置长度
    int preStringLength = 0;

    // 从左到右遍历字符数组
    for (int i = 0; i < charsLen; i++) {

        // 从右到左找从左到右遍历的字符最后出现的位置
        for (int j = charsLen - 1; j >= index ; j--) {
            if (chars[i] == chars[j]) {
                index = j;
                break;
            }
        }

        // 从左到右遍历到了当前记录的最远位置
        if (i == index) {

            // 将这一段字符串的结束位置长度减去前一段字符串的结束位置长度即为当前字符串的长度
            list.add(index + 1 - preStringLength);

            // 更新前一段字符串的结束位置长度
            preStringLength = index + 1;
        }
    }

    return list;
}

方法二：贪心

思路：由于字符串都是由小写字母组成，所以可以通过一个循环用一个长度为26的字符数组记录每一个字符的最后出现位置，然后遍历需要划分的字符串，更新当前字符串的结束位置，直到遍历需要划分的字符串到当前这一段字符串的结束位置时，此位置即为这一段字符串的最终结束位置，以此类推继续找下一段字符串。

运行数据：执行用时：2 ms，内存消耗：38 MB

// LeetCode指定调用方法
public List<Integer> partitionLabels(String S) {

    // 记录结果
    List<Integer> list = new ArrayList<Integer>();

    // 将需要划分的字符串转成字符数组
    char[] chars = S.toCharArray();

    // 记录字符数组chars的长度
    int charsLen = chars.length;

    // 记录每个字符出现的最后位置
    int[] lastPosition = new int[26];

    // 循环统计每个字符出现的最后位置
    for (int i = 0; i < charsLen; i++) {
        lastPosition[chars[i] - 'a'] = i;
    }

    // 记录前一段字符串的结束位置长度
    int left = 0;

    // 记录当前这一段字符串的结束位置长度
    int right = 0;

    // 计算结果
    for (int i = 0; i < charsLen; i++) {

        // 更新当前这一段字符串的结束位置
        right = Math.max(right, lastPosition[chars[i] - 'a']);

        // 当遍历到当前这一段字符串结束位置时，此位置即为这一段字符串的最终结束位置
        if (i == right) {

            // 记录这一段字符串长度
            list.add(right + 1 - left);

            // 更新前一段字符串的结束位置长度
            left = right + 1;
        }
    }

    return list;
}