Leetcode 763划分字母区间

October 22, 2020 3414

763. 划分字母区间

题目描述

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

示例 1：

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

提示：

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

拿到这个题目，看到 把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段 ，就想到差不多是 贪心了，和 45. 跳跃游戏 II 类似 用一个 end指针 当前 解的最远 位置，并且将 把从前位置到最远位置 的所有字符 遍历，用来更新 end指针,来得到 字符串划分为尽可能多的片段。

代码实现

版本一

先来介绍一下我写的第一版，说真的，虽然通过了，但是我自己都觉得巨丑无比，不忍直视。

思路：每次先把当前字符的最远位置找出来，把当前字符 到 最远位置 的字符 遍历，更新最远位置，中间用了一个 set来优化，防止重复查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public List<Integer> partitionLabels(String S) {
    List<Integer> res = new ArrayList<>();

    int n = S.length();
    for (int i = 0; i < n; i++) {
        // 已经 试探过的字符 集合，避免后面重复试探
        Set<Character> set = new HashSet<>();
        int end = i;
        char ch = S.charAt(i);
        set.add(ch);
        for (int j = i + 1; j < n; j++) {
            // 向后更新 边界指针
            if (S.charAt(j) == ch) end = j;
        }
        
        for (int j = i + 1; j < end; j++) {
            char c = S.charAt(j);
            if (!set.contains(c)) {
                set.add(c);
                for (int k = j + 1; k < n; k++) {
                    if (S.charAt(k) == c) end = Math.max(end, k);
                }
            }
        }
        
        res.add(end - i + 1);
        i = end;
    }
    
    return res;
}

版本二

在上个版本的基础上做了点 微改动，把 set 换成了 数组，空间上确实优化了一点，时间上基本没动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public List<Integer> partitionLabels(String S) {
    List<Integer> res = new ArrayList<>();

    int n = S.length();
    for (int i = 0; i < n; i++) {
        // 已经 试探过的字符 集合，避免后面重复试探
        int[] count = new int['z' - 'a' + 1];
        int end = i;

        char ch = S.charAt(i);
        count[ch - 'a']++;
        for (int j = i + 1; j < n; j++) {
            // 向后更新 边界指针
            if (S.charAt(j) == ch) end = j;
        }

        for (int j = i + 1; j < end; j++) {
            char c = S.charAt(j);
            if (count[c - 'a'] == 0) {
                count[c - 'a']++;
                for (int k = j + 1; k < n; k++) {
                    if (S.charAt(k) == c) {
                        end = Math.max(end, k);
                    }
                }
            }
        }
        res.add(end - i + 1);
        i = end;
    }
    return res;
}

版本三

在 自己思考后，感觉已经到达能力的上限时候，不由的点开了 官方题解。官方的代码给我感觉是 怎么这么 短小精悍，读完才知道，先用了一次遍历记录每个字符最后出现的位置，省的像我一样，每次再找最后位置，浪费时间。

不得不说，能力还是不行，不过，经历了也就学到了这个，在后面的刷题中 或许就想到这种优化了。下面是我参考官方思路写出来的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> partitionLabels(String S) {
        int[] count = new int['z' - 'a' + 1];
        int n = S.length();
        // 存储 每个字母最后一次出现的 下标
        for (int i = 0; i < n; i++) count[S.charAt(i) - 'a'] = i;

        int start = 0;
        int end = 0;
        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            end = Math.max(end, count[S.charAt(i) - 'a']);
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }

        return res;
}