add a solution for 849

fishercoder1534 · fishercoder1534 · commit 34ee3d3ff5d2 · 2021-09-13T19:55:20.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_849.java b/src/main/java/com/fishercoder/solutions/_849.java
@@ -1,5 +1,7 @@
 package com.fishercoder.solutions;
 
+import java.util.TreeSet;
+
 public class _849 {
     public static class Solution1 {
         int maxDist = 0;
@@ -45,4 +47,33 @@ private void extend(int[] seats, int position) {
             maxDist = Math.max(maxDist, maxReach);
         }
     }
+
+    public static class Solution2 {
+        /**
+         * my completely original solution on 9/13/2021.
+         */
+        public int maxDistToClosest(int[] seats) {
+            int maxDistance = 0;
+            TreeSet<Integer> treeMap = new TreeSet<>();
+            for (int i = 0; i < seats.length; i++) {
+                if (seats[i] == 1) {
+                    treeMap.add(i);
+                }
+            }
+            for (int i = 0; i < seats.length; i++) {
+                if (seats[i] == 0) {
+                    Integer leftNeighbor = treeMap.floor(i);
+                    Integer rightNeighbor = treeMap.ceiling(i);
+                    if (leftNeighbor != null && rightNeighbor != null) {
+                        maxDistance = Math.max(maxDistance, Math.min(i - leftNeighbor, rightNeighbor - i));
+                    } else if (leftNeighbor == null) {
+                        maxDistance = Math.max(maxDistance, rightNeighbor - i);
+                    } else {
+                        maxDistance = Math.max(maxDistance, i - leftNeighbor);
+                    }
+                }
+            }
+            return maxDistance;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_849Test.java b/src/test/java/com/fishercoder/_849Test.java
@@ -9,19 +9,23 @@
 public class _849Test {
 
     private static _849.Solution1 solution1;
+    private static _849.Solution2 solution2;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _849.Solution1();
+        solution2 = new _849.Solution2();
     }
 
     @Test
     public void test1() {
         assertEquals(2, solution1.maxDistToClosest(new int[]{1, 0, 0, 0, 1, 0, 1}));
+        assertEquals(2, solution2.maxDistToClosest(new int[]{1, 0, 0, 0, 1, 0, 1}));
     }
 
     @Test
     public void test2() {
         assertEquals(3, solution1.maxDistToClosest(new int[]{1, 0, 0, 0}));
+        assertEquals(3, solution2.maxDistToClosest(new int[]{1, 0, 0, 0}));
     }
 }

Original file line number	Diff line number	Diff line change
`@@ -9,19 +9,23 @@`
`9`	`9`	`public class _849Test {`
`10`	`10`
`11`	`11`	`private static _849.Solution1 solution1;`
	`12`	`+ private static _849.Solution2 solution2;`
`12`	`13`
`13`	`14`	`@BeforeClass`
`14`	`15`	`public static void setup() {`
`15`	`16`	`solution1 = new _849.Solution1();`
	`17`	`+ solution2 = new _849.Solution2();`
`16`	`18`	`}`
`17`	`19`
`18`	`20`	`@Test`
`19`	`21`	`public void test1() {`
`20`	`22`	`assertEquals(2, solution1.maxDistToClosest(new int[]{1, 0, 0, 0, 1, 0, 1}));`
	`23`	`+ assertEquals(2, solution2.maxDistToClosest(new int[]{1, 0, 0, 0, 1, 0, 1}));`
`21`	`24`	`}`
`22`	`25`
`23`	`26`	`@Test`
`24`	`27`	`public void test2() {`
`25`	`28`	`assertEquals(3, solution1.maxDistToClosest(new int[]{1, 0, 0, 0}));`
	`29`	`+ assertEquals(3, solution2.maxDistToClosest(new int[]{1, 0, 0, 0}));`
`26`	`30`	`}`
`27`	`31`	`}`