当前位置：首页 > article >正文

【玩转贪心算法专题】763. 划分字母区间【中等】

article 2025/2/22 2:04:38

【玩转贪心算法专题】763. 划分字母区间【中等】

1、力扣链接

https://leetcode.cn/problems/partition-labels/description/

2、题目描述

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。
示例 2：

输入：s = “eccbbbbdec”
输出：[10]

提示：

1 <= s.length <= 500
s 仅由小写英文字母组成

3、题目分析

对于贪心算法的题目，可从寻求局部最优解入手，以局部最优解，得到全局最优解
本题思路：

统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

4、代码实现

1、Java

class Solution {
    public List<Integer> partitionLabels(String s) {
            //记录最后结果
            List<Integer> list = new LinkedList<>();
            //记录每个字母出现的最远位置
            int[] edge = new int[26];
            char[] chars = s.toCharArray();
            for(int i=0;i < chars.length; i++){
                //'a'-'a' edge[0] = 8;
                edge[chars[i] - 'a'] = i;
            }
            //右边界
            int idx = 0;
            //左边界
            int last = -1;
            for(int i=0; i< chars.length;i++){
                //本次遍历到的idx 最远距离
                idx = Math.max(idx,edge[chars[i] - 'a']);
                //如果相等
                if(i == idx){
                    //记录一个片段
                    list.add(i-last);
                    last = i;
                }
            }
            return list;
    }
}

2、C++

class Solution {
public:
    static bool cmp(vector<int> &a, vector<int> &b) {
        return a[0] < b[0];
    }
    // 记录每个字母出现的区间
    vector<vector<int>> countLabels(string s) {
        vector<vector<int>> hash(26, vector<int>(2, INT_MIN));
        vector<vector<int>> hash_filter;
        for (int i = 0; i < s.size(); ++i) {
            if (hash[s[i] - 'a'][0] == INT_MIN) {
                hash[s[i] - 'a'][0] = i;
            }
            hash[s[i] - 'a'][1] = i;
        }
        // 去除字符串中未出现的字母所占用区间
        for (int i = 0; i < hash.size(); ++i) {
            if (hash[i][0] != INT_MIN) {
                hash_filter.push_back(hash[i]);
            }
        }
        return hash_filter;
    }
    vector<int> partitionLabels(string s) {
        vector<int> res;
        // 这一步得到的 hash 即为无重叠区间题意中的输入样例格式：区间列表
        // 只不过现在我们要求的是区间分割点
        vector<vector<int>> hash = countLabels(s);
        // 按照左边界从小到大排序
        sort(hash.begin(), hash.end(), cmp);
        // 记录最大右边界
        int rightBoard = hash[0][1];
        int leftBoard = 0;
        for (int i = 1; i < hash.size(); ++i) {
            // 由于字符串一定能分割，因此,
            // 一旦下一区间左边界大于当前右边界，即可认为出现分割点
            if (hash[i][0] > rightBoard) {
                res.push_back(rightBoard - leftBoard + 1);
                leftBoard = hash[i][0];
            }
            rightBoard = max(rightBoard, hash[i][1]);
        }
        // 最右端
        res.push_back(rightBoard - leftBoard + 1);
        return res;
    }
};

3、python

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_occurrence = {}  # 存储每个字符最后出现的位置
        for i, ch in enumerate(s):
            last_occurrence[ch] = i

        result = []
        start = 0
        end = 0
        for i, ch in enumerate(s):
            end = max(end, last_occurrence[ch])  # 找到当前字符出现的最远位置
            if i == end:  # 如果当前位置是最远位置，表示可以分割出一个区间
                result.append(end - start + 1)
                start = i + 1

        return result

4、go

func partitionLabels(s string) []int {
    var res []int;
    var marks [26]int;
    size, left, right := len(s), 0, 0;
    for i := 0; i < size; i++ {
        marks[s[i] - 'a'] = i;
    }
    for i := 0; i < size; i++ {
        right = max(right, marks[s[i] - 'a']);
        if i == right {
            res = append(res, right - left + 1);
            left = i + 1;
        }
    }
    return res;
}

func max(a, b int) int {
    if a < b {
        a = b;
    }
    return a;
}