[LeetCode] 763. Partition Labels

iliyaku 發(fā)布于2019-08-16 13:58 / 1630人閱讀

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/72653.html

【LeetCode】貪心算法--劃分字母區(qū)間（763）

摘要：寫在前面今天這篇文章是貪心算法系列的第三篇劃分字母區(qū)間。前文回顧貪心算法分發(fā)糖果刷題匯總匯總貼今日題目字符串由小寫字母組成。返回一個表示每個字符串片段的長度的列表。示例輸入輸出解釋劃分結(jié)果為。每個字母最多出現(xiàn)在一個片段中。寫在前面今天這篇文章是貪心算法系列的第三篇--劃分字母區(qū)間。前文回顧：【LeetCode】貪心算法--分發(fā)糖果（135）刷題匯總：【LeetCode】匯總...

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

摘要：返回一個表示每個字符串片段的長度的列表。示例輸入輸出解釋劃分結(jié)果為。每個字母最多出現(xiàn)在一個片段中。像的劃分是錯誤的，因為劃分的片段數(shù)較少。把交叉的區(qū)間不斷擴大，然后并保存，最后輸出所有合并后的區(qū)間的重點起點。題目地址：https://leetcode-cn.com/probl...題目描述：字符串 S 由小寫字母組成。我們要把這個字符串劃分為盡可能多的片段，同一個字母只會出現(xiàn)在其中的...

stdying 2019-08-16 15:15 評論0 收藏0
leetcode86. Partition List

摘要：當前節(jié)點的前一個節(jié)點插入位置的前一個節(jié)點，以及記錄初始位置的節(jié)點。當發(fā)現(xiàn)一個需要交換的節(jié)點時，先獲得這個節(jié)點，然后將指向節(jié)點的后一個節(jié)點。最后將兩個鏈表連接。代碼相比于第一種更加清晰一些。題目要求 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

摘要：題目鏈接題目分析本題給了一個數(shù)組，要求將數(shù)組分為個只有個元素的一對。因此，要使每組中最大的數(shù)字和最小的數(shù)組之差最小，這樣才能使損失最小。當分為兩組時，每組取最小后，會得到。求和后為，比大。 561. Array Partition I 題目鏈接 561. Array Partition I 題目分析本題給了一個數(shù)組，要求將數(shù)組分為n個只有2個元素的一對。使得每對數(shù)字中最小的數(shù)加起...

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