add 868

fishercoder1534 · fishercoder1534 · commit f397c6d6313b · 2018-12-24T20:03:10.000-08:00
diff --git a/README.md b/README.md
@@ -41,6 +41,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |896|[Monotonic Array](https://leetcode.com/problems/monotonic-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_896.java) | O(n) | O(1) | |Easy|
 |884|[Uncommon Words from Two Sentences](https://leetcode.com/problems/uncommon-words-from-two-sentences/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_884.java) | O(n) | O(k) | |Easy|
 |876|[Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_876.java) | O(n) | O(1) | |Easy|
+|868|[Binary Gap](https://leetcode.com/problems/binary-gap/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_868.java) | O(n) | O(n) | |Easy|
 |867|[Transpose Matrix](https://leetcode.com/problems/transpose-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_867.java) | O(r*c) | O(r*c) | |Easy|
 |852|[Peak Index in a Mountain Array](https://leetcode.com/problems/peak-index-in-a-mountain-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_852.java) | O(n) | O(1) | |Easy|
 |844|[Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_844.java) | O(n) | O(1) | |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_868.java b/src/main/java/com/fishercoder/solutions/_868.java
@@ -0,0 +1,62 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * 868. Binary Gap
+ *
+ * Given a positive integer N, find and return the longest distance between two consecutive 1's in the binary representation of N.
+ *
+ * If there aren't two consecutive 1's, return 0.
+ *
+ * Example 1:
+ * Input: 22
+ * Output: 2
+ * Explanation:
+ * 22 in binary is 0b10110.
+ * In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
+ * The first consecutive pair of 1's have distance 2.
+ * The second consecutive pair of 1's have distance 1.
+ * The answer is the largest of these two distances, which is 2.
+ *
+ * Example 2:
+ * Input: 5
+ * Output: 2
+ * Explanation:
+ * 5 in binary is 0b101.
+ *
+ * Example 3:
+ * Input: 6
+ * Output: 1
+ * Explanation:
+ * 6 in binary is 0b110.
+ *
+ * Example 4:
+ * Input: 8
+ * Output: 0
+ * Explanation:
+ * 8 in binary is 0b1000.
+ * There aren't any consecutive pairs of 1's in the binary representation of 8, so we return 0.
+ *
+ * Note:
+ * 1 <= N <= 10^9
+ */
+public class _868 {
+  public static class Solution1 {
+    public int binaryGap(int N) {
+      String bin = Integer.toBinaryString(N);
+      List<Integer> oneIndexes = new ArrayList<>();
+      for (int i = 0; i < bin.length(); i++) {
+        if (bin.charAt(i) == '1') {
+          oneIndexes.add(i);
+        }
+      }
+      int maxGap = 0;
+      for (int i = 0; i < oneIndexes.size() - 1; i++) {
+        maxGap = Math.max(oneIndexes.get(i + 1) - oneIndexes.get(i), maxGap);
+      }
+      return maxGap;
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_868Test.java b/src/test/java/com/fishercoder/_868Test.java
@@ -0,0 +1,36 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._868;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _868Test {
+  private static _868.Solution1 solution1;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _868.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    assertEquals(2, solution1.binaryGap(22));
+  }
+
+  @Test
+  public void test2() {
+    assertEquals(2, solution1.binaryGap(5));
+  }
+
+  @Test
+  public void test3() {
+    assertEquals(1, solution1.binaryGap(6));
+  }
+
+  @Test
+  public void test4() {
+    assertEquals(0, solution1.binaryGap(8));
+  }
+}
