[LeetCode] 763. Partition Labels

iliyaku 发布于2019-08-16 13:58 / 1622人阅读

Problem

A string S of lowercase 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.
Note:

S will have length in range [1, 500].
S will consist of lowercase letters ("a" to "z") only.

Solution Solution 0 - preferred

using char array is so much faster

class Solution {
    public List partitionLabels(String S) {
        List res = new ArrayList<>();
        int[] dict = new int[26];
        char[] str = S.toCharArray();
        for (char ch: str) {
            dict[ch-"a"]++;
        }
        int i = 0, j = 0, count = 0;
        Set set = new HashSet<>();
        while (j < S.length()) {
            char ch = str[j];
            if (!set.contains(ch)) {
                set.add(ch);
                count++;
            }
            dict[ch-"a"]--;
            j++;
            
            if (dict[ch-"a"] == 0) {
                count--;
                set.remove(ch);
            }
            
            if (count == 0) {
                res.add(j-i);
                i = j;
            }
        }
        return res;
    }
}

Solution 1

class Solution {
    public List partitionLabels(String S) {
        List res = new ArrayList<>();
        int[] index = new int[26];
        for (int i = 0; i < S.length(); i++) {
            index[S.charAt(i) - "a"] = i;
        }
        int start = 0;
        int end = 0;
        for (int i = 0; i < S.length(); i++) {
            int c = S.charAt(i) - "a";
            if (index[c] != i) {
                if (index[c] > end) {
                    end = index[c];
                }
            } else if (i == end){
                res.add(i - start + 1);
                start = i + 1;
                end = i + 1;
            }
        }
        return res;
    }
}

Solution 2 - Sliding Window + 2 HashMap

class Solution {
    public List partitionLabels(String S) {
        List res = new ArrayList<>();
        if (S == null || S.length() == 0) return res;
        
        Map map = new HashMap<>();
        for (char ch: S.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0)+1);
        }
        
        Map record = new HashMap<>();
        int start = 0, end = 0;
        while (end < S.length()) {
            char ch = S.charAt(end);
            if (!record.containsKey(ch)) record.put(ch, map.get(ch));
            record.put(ch, record.get(ch)-1);
            if (record.get(ch) == 0) record.remove(ch);
            if (record.keySet().size() == 0) {
                res.add(end-start+1);
                start = end+1;
            }
            end++;
        }
        
        return res;
    }
}

GPU云服务器云服务器 Labels LeetCode Partition LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72653.html

【LeetCode】贪心算法--划分字母区间（763）

摘要：写在前面今天这篇文章是贪心算法系列的第三篇划分字母区间。前文回顾贪心算法分发糖果刷题汇总汇总贴今日题目字符串由小写字母组成。返回一个表示每个字符串片段的长度的列表。示例输入输出解释划分结果为。每个字母最多出现在一个片段中。写在前面今天这篇文章是贪心算法系列的第三篇--划分字母区间。前文回顾：【LeetCode】贪心算法--分发糖果（135）刷题汇总：【LeetCode】汇总...

honhon 2019-07-31 11:21 评论0 收藏0
力扣(LeetCode)763

摘要：返回一个表示每个字符串片段的长度的列表。示例输入输出解释划分结果为。每个字母最多出现在一个片段中。像的划分是错误的，因为划分的片段数较少。把交叉的区间不断扩大，然后并保存，最后输出所有合并后的区间的重点起点。题目地址：https://leetcode-cn.com/probl...题目描述：字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的...

stdying 2019-08-16 15:15 评论0 收藏0
leetcode86. Partition List

摘要：当前节点的前一个节点插入位置的前一个节点，以及记录初始位置的节点。当发现一个需要交换的节点时，先获得这个节点，然后将指向节点的后一个节点。最后将两个链表连接。代码相比于第一种更加清晰一些。题目要求 Given a linked list and a value x, partition it such that all nodes less than x come before no...

layman 2019-08-15 10:45 评论0 收藏0
Leetcode PHP题解--D14 561. Array Partition I

摘要：题目链接题目分析本题给了一个数组，要求将数组分为个只有个元素的一对。因此，要使每组中最大的数字和最小的数组之差最小，这样才能使损失最小。当分为两组时，每组取最小后，会得到。求和后为，比大。 561. Array Partition I 题目链接 561. Array Partition I 题目分析本题给了一个数组，要求将数组分为n个只有2个元素的一对。使得每对数字中最小的数加起...

stonezhu 2019-07-01 12:36 评论0 收藏0
[LeetCode] 86. Partition List

Problem Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in ea...

Yuqi 2019-08-16 13:54 评论0 收藏0