LeetCode 763 - Partition Labels


https://leetcode.com/problems/partition-labels/
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:
  1. S will have length in range [1, 500].
  2. S will consist of lowercase letters ('a' to 'z') only
https://hk.saowen.com/a/561ee16eff6c0d2649cfa7225390e10ec3481feb92c1c042e36f4c7fcbea48dd
  • 字符串中等題。滑動窗口+貪心。時間複雜度O(N),空間複雜度O(N)。
  • 首先依然是做hash,不過這次是對所有char記錄它們最後出現的位置。
  • 然後定義三個指針,window開始left和結束right,當前i。每次移動i,然後判斷當前S[i]最後出現的位置是否大於當前right,如果是,則擴展right為last[S[i]]。
  • 如果當前i == window結束right,則代表當前window中所有的字符都只在當前window中出現。所以可以把當前window的size記錄。同時移動left到下一個window的起點。
16     vector<int> partitionLabels(string S) {
17         vector<int> vResult;
18         
19         // corner case
20         if (S.empty()) return vResult;
21         
22         unordered_map<char, int> last;
23         
24         // the last occurred index of S[i]
25         for (int i = 0; i < S.size(); ++ i)
26             last[S.at(i)] = i;
27         
28         // start and end of the current window
29         int left = 0, right = 0;
30         
31         // current pointer
32         for (int i = 0; i < S.size(); ++ i) {
33             right = max(right, last[S.at(i)]); // maximum index of the current window
34             
35             // reach the end of current window
36             if (i == right) {
37                 vResult.push_back(right - left + 1); // size of the current window
38                 left = i + 1; // move to start of the next window
39             }
40         }
41         
42         return vResult;
43     }
https://blog.csdn.net/fuxuemingzhu/article/details/79265829
题意是要对一个字符串进行尽可能多的划分,并保证每个划分中的元素不在其他划分中出现。

想法比较具有技巧性。如果一段序列中每个元素的在S中最右边的序号都在某个范围内,那么就可以划分成一个段。

因此,使用字典保存每个元素出现的最靠右的位置。然后对字符串S进行遍历,找出最靠右的序号的最大值j。如果i和j重合了,说明已经到了这个划分的末尾了,然后进行划分。并开始计算下一个划分。

  vector<int>
  partitionLabels(string S) {
    map<char, int> d;
    for (int i = 0; i < S.size(); i++) d[S[i]] = i;
    int start = 0, end = 0;
    vector<int> res;
    for (int i = 0; i < S.size(); i++) {
        end = max(end, d[S[i]]);
        if (i == end) {
            res.push_back(end - start + 1);
            start = end + 1;
        }
    }
    return res;

 }
http://www.cnblogs.com/grandyang/p/8654822.html
这道题给了我们一个字符串S,然我们将其尽可能多的分割为子字符串,条件是每种字符最多只能出现在一个子串中。比如题目汇总的例子,字符串S中有多个a,这些a必须只能在第一个子串中,再比如所有的字母e值出现在了第二个子串中。那么这道题的难点就是如何找到字符串的断点,即拆分成为子串的位置。我们仔细观察题目中的例子,可以发现一旦某个字母多次出现了,那么其最后一个出现位置必须要在当前子串中,字母a,e,和j,分别是三个子串中的结束字母。所以我们关注的是每个字母最后的出现位置,我们可以使用一个HashMap来建立字母和其最后出现位置之间的映射,那么对于题目中的例子来说,我们可以得到如下映射:
a -> 8
b -> 5
c -> 7
d -> 14
e -> 15
f -> 11
g -> 13
h -> 19
i -> 22
j -> 23
k -> 20
l -> 21
建立好映射之后,就需要开始遍历字符串S了,我们维护一个start变量,是当前子串的起始位置,还有一个last变量,是当前子串的结束位置,每当我们遍历到一个字母,我们需要在HashMap中提取出其最后一个位置,因为一旦当前子串包含了一个字母,其必须包含所有的相同字母,所以我们要不停的用当前字母的最后一个位置来更新last变量,只有当i和last相同了,即当i = 8时,当前子串包含了所有已出现过的字母的最后一个位置,即之后的字符串里不会有之前出现过的字母了,此时就应该是断开的位置,我们将长度9加入结果res中
https://leetcode.com/articles/partition-labels/
Let's try to repeatedly choose the smallest left-justified partition. Consider the first label, say it's 'a'. The first partition must include it, and also the last occurrence of 'a'. However, between those two occurrences of 'a', there could be other labels that make the minimum size of this partition bigger. For example, in "abccaddbeffe", the minimum first partition is "abccaddb". This gives us the idea for the algorithm: For each letter encountered, process the last occurrence of that letter, extending the current partition [anchor, j] appropriately.
Algorithm
We need an array last[char] -> index of S where char occurs last. Then, let anchor and j be the start and end of the current partition. If we are at a label that occurs last at some index after j, we'll extend the partition j = last[c]. If we are at the end of the partition (i == j) then we'll append a partition size to our answer, and set the start of our new partition to i+1.

  public List<Integer> partitionLabels(String S) {
    int[] last = new int[26];
    for (int i = 0; i < S.length(); ++i)
      last[S.charAt(i) - 'a'] = i;

    int j = 0, anchor = 0;
    List<Integer> ans = new ArrayList();
    for (int i = 0; i < S.length(); ++i) {
      j = Math.max(j, last[S.charAt(i) - 'a']);
      if (i == j) {
        ans.add(i - anchor + 1);
        anchor = i + 1;
      }
    }
    return ans;
  }

https://zxi.mytechroad.com/blog/string/leetcode-763-partition-labels/
  public List<Integer> partitionLabels(String S) {
    int lastIndex[] = new int[128];
    for (int i = 0; i < S.length(); ++i)
      lastIndex[(int)S.charAt(i)] = i;
    List<Integer> ans = new ArrayList<>();
    int start = 0;
    int end = 0;
    for (int i = 0; i < S.length(); ++i) {
      end = Math.max(end, lastIndex[(int)S.charAt(i)]);
      if (i == end) {
        ans.add(end - start + 1);
        start = end + 1;
      }
    }
    return ans;
  }


https://segmentfault.com/a/1190000017354158

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts