Leetcode日记–763. Partition Labels

发布于 2020-10-22  112 次阅读


碎碎念:明天运动会放假一天(虽然只有一节一上午的微信开发课),起飞~~

题目如下:

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]

Explanation:


The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

思路:

按照题目标签,本题考察的是贪心算法

所谓贪心算法就是,把问题分解为小的问题,然后在每个小问题(每一步)中取局部最优解(也就是最有利)的选择。

若是对于某个问题,局部最优解等同于最优解,或是所需的精度不高,则可以使用贪心算法。

贪心算法动态规划的区别:贪心算法在每一步会直接进行选择,进入下一个状态而不会回退;动态规划则会记录下来前面步骤的结果,并根据情况进行选择,有可能回退。

本题要求的是,每个字母只能出现在一个分段中;在满足上一个要求的条件下,尽可能多地进行分段。

为了满足第一个必要条件,我们必须维护一个数据结构(选择合适的容器也非常重要,关于这点我们后面再说)记录每个字母的最后出现位置。

之后我们设立一个end值和一个start值,一步一步地对字符串进行遍历。对于每轮遍历,我们取end为end和当前字母出现的最后位置中的最大值,这样我们可以保证每个字母只存在于一个分段中。

同时,若我们遍历的位置i等于end了,则说明达到了最小可分段之中。那么这时赶紧分为一段(贪心),此时的段长为end-start+1.

我和官方的代码实现唯一的区别就在于,我使用了一个 map 来存储每个字符对于的最后出现位置。且我是从后往前遍历,若contains函数返回true则不更新,这样的方法调用函数次数较多,导致运算时间和空间都没有官方方法这么漂亮。

官方的方法就是建立一个size为26的int数组,0对应a,1对于b以此类推。每次计算位置的时候,S.charAt(i) - 'a'便可以找到数组中对应的最后出现位置。

我的代码如下:

class Solution {
    public List<Integer> partitionLabels(String S) {
        HashMap<Character,Integer> last = new HashMap<Character,Integer>();
        for(int i = S.length()-1 ; i>=0;i--){
            if(last.containsKey(S.charAt(i)))
                continue;
            else
                last.put(S.charAt(i),i);
        }
        int start = 0;
        int end = 0;
        List<Integer> res = new ArrayList<Integer>();
        for(int i = 0; i<S.length();i++){
            end = Math.max(end,last.get(S.charAt(i)));
            if(i==end){
                res.add(end-start+1);
                end = i+1;
                start = end;
            }
        }
        return res;
    }
}

官方题解代码如下:

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

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/partition-labels/solution/hua-fen-zi-mu-qu-jian-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

你好哇!欢迎来到雷公马碎碎念的地方:)