[LeetCode] 763. Partition Labels

iliyaku 發布于2019-08-16 13:58 / 1623人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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