add 763

fishercoder1534 · fishercoder1534 · commit bb36eaf0e8ce · 2018-01-14T09:14:47.000-08:00
diff --git a/README.md b/README.md
@@ -22,6 +22,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
+|763|[Partition Labels](https://leetcode.com/problems/partition-labels/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_763.java) | O(n) | O(1) | |Medium|
 |760|[Find Anagram Mappings](https://leetcode.com/problems/find-anagram-mappings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_760.java) | O(n^2) | O(1) | |Easy| 
 |755|[Reach a Number](https://leetcode.com/problems/reach-a-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_755.java) | O(n) | O(1) | |Medium| Math
 |750|[Number Of Corner Rectangles](https://leetcode.com/problems/number-of-corner-rectangles/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_750.java) | O((m*n)^2) | O(1) | |Medium|
diff --git a/src/main/java/com/fishercoder/solutions/_763.java b/src/main/java/com/fishercoder/solutions/_763.java
@@ -0,0 +1,52 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * 763. 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:
+ S will have length in range [1, 500].
+ S will consist of lowercase letters ('a' to 'z') only.
+ */
+public class _763 {
+
+  public static class Solution1 {
+    public List<Integer> partitionLabels(String S) {
+      List<Integer> result = new ArrayList<>();
+      int[] last = new int[26];
+      /**This is the key step:
+       * we find the last occurrence of each letter and record them in last[]*/
+      for (int i = 0; i < S.length(); i++) {
+        last[S.charAt(i) - 'a'] = i;
+      }
+      int start = -1;
+      int end = -1;
+      for (int i = 0; i < S.length(); i++) {
+        if (start == -1) {
+          start = i;
+        }
+        end = Math.max(end, last[S.charAt(i) - 'a']);
+        if (end == i) {
+          result.add(end - start + 1);
+          start = -1;
+        }
+      }
+      return result;
+    }
+  }
+
+}
diff --git a/src/test/java/com/fishercoder/_763Test.java b/src/test/java/com/fishercoder/_763Test.java
@@ -0,0 +1,27 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._763;
+import java.util.Arrays;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _763Test {
+  private static _763.Solution1 solution1;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _763.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    assertEquals(Arrays.asList(9, 7, 8), solution1.partitionLabels("ababcbacadefegdehijhklij"));
+  }
+
+  @Test
+  public void test2() {
+    assertEquals(Arrays.asList(9, 7, 8), solution1.partitionLabels("ababcbacadefegdehijhklij"));
+  }
+}
