【力扣-贪心】7、划分字母区间（763） 763 划分字母

发表于

「这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战」

763. 划分字母区间

题目描述

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

示例：

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

提示：

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

解析

题述中同一个字母只能出现在同一个片段中，所以可以求出每个片段中字符出现的最远位置，以这个最远位置作为分界点来进行分段。

  • 步骤
    • 定义数组vector<int> pos记录每个字符出现的最远位置
      • 这里不考虑大写字母，所以数组的大小可以指定为 26
      • 对数组进行初始化 ，值全部初始化为 0
    • 分割片段
      • 每个片段区间使用 [left,right]来记录长度
      • 分割点的确定
        • 如果字符出现的最远位置等于当前遍历到的索引，就将最远位置作为分割点
        • 更新本片段的右边界 right,更新下一个片段的左边界 left
      • 记录区间的长度并加入到结果集中

代码

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
33
34
35
36
37
38
39
40
41
c++复制代码class Solution
{
public:
    vector<int> partitionLabels(string s)
    {
        // 题述中只考虑小写字母，
        // 所以可以定义一个长度为26的数组记录每个字符出现的最远位置
        // 这里 a的下标对应为0，z的下标对应25
        int pos[26] = {0};

        // 遍历字符串中的字符，记录每个字符出现的最远位置
        for (int i = 0; i < s.size(); i++)
        {
            pos[s[i] - 'a'] = i;
        }

        // 结果集
        vector<int> result;
        // 记录区间的左边界
        int left = 0;
        // 记录区间的右边界
        int right = 0;
        
        // 遍历字符串
        for (int i = 0; i < s.size(); i++)
        {
            // 找到字符出现的最远位置，作为本片段区间的右边界
            right = max(right, pos[s[i] - 'a']);
            if (i == right)
            {
               
                // 更新下一个分割片段区间的的左边界
                left = i + 1;
                 // 记录每个片段的长度
                result.push_back(right - left + 1);
            }
        }

        return result;
    }
};

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%