fd

dingjikerbo · dingjikerbo · commit d38d588b5235 · 2018-12-05T15:19:23.000+08:00
diff --git a/README.md b/README.md
@@ -397,6 +397,7 @@
 |819|[Most Common Word](https://leetcode.com/problems/most-common-word/)|[Java](leetcode/solution/src/MostCommonWord.java)|85||
 |843|[Guess the Word](https://leetcode.com/problems/guess-the-word/)|[Java](leetcode/solution/src/GuessTheWord.java)|90||
 |844|[Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/)|[Java](leetcode/solution/src/BackspaceStringCompare.java)|100||
+|849|[Maximize Distance to Closest Person](https://leetcode.com/problems/maximize-distance-to-closest-person/)|[Java](leetcode/solution/src/MaximizeDistanceToClosestPerson.java)|80||
 |857|[Minimum Cost to Hire K Workers](https://leetcode.com/problems/minimum-cost-to-hire-k-workers/)|[Java](leetcode/solution/src/MinimumCostToHireKWorkers.java|70||
 |904|[Fruit Into Baskets](https://leetcode.com/problems/fruit-into-baskets/)|[Java](leetcode/solution/src/FruitIntoBaskets.java)|90||
 |929|[Unique Email Addresses](https://leetcode.com/problems/unique-email-addresses/)|[Java](leetcode/solution/src/UniqueEmailAddresses.java)|90||
diff --git a/leetcode/solution/src/MaximizeDistanceToClosestPerson.java b/leetcode/solution/src/MaximizeDistanceToClosestPerson.java
@@ -0,0 +1,46 @@
+import java.util.Arrays;
+
+public class MaximizeDistanceToClosestPerson {
+
+    /**
+     * 这题要注意两个边界的情况，因为如果是非边界的情况，要坐在中间的
+     */
+    public int maxDistToClosest(int[] seats) {
+        int max = 0;
+
+        int[] zone = new int[2];
+        for (int index = 0; index < seats.length; ) {
+            Arrays.fill(zone, -1);
+            index = nextFree(seats, index, zone);
+            if (zone[0] == 0 || zone[1] == seats.length - 1) {
+                max = Math.max(max, zone[1] - zone[0] + 1);
+            } else {
+                max = Math.max(max, (zone[1] - zone[0] + 2) / 2);
+            }
+        }
+
+        return max;
+    }
+
+    /**
+     * 返回从start开始的连续的0区间
+     */
+    private int nextFree(int[] seats, int start, int[] zone) {
+        boolean enter = false;
+        for (int i = start, j = 0; i <= seats.length; i++) {
+            if (i < seats.length && seats[i] == 0) {
+                if (!enter) {
+                    enter = true;
+                    j = i;
+                }
+            } else {
+                if (enter) {
+                    zone[0] = j;
+                    zone[1] = i - 1;
+                    return i + 1;
+                }
+            }
+        }
+        return seats.length;
+    }
+}
diff --git a/leetcode/src/Main.java b/leetcode/src/Main.java
@@ -6,31 +6,46 @@ public class Main {
 
     public static class Solution {
 
-
-        public int candy(int[] ratings) {
-            int[] candys = new int[ratings.length];
-
-            Arrays.fill(candys, 1);
-
-            for (int i = 1; i < ratings.length; i++) {
-                if (ratings[i] > ratings[i - 1]) {
-                    candys[i] = candys[i - 1] + 1;
+        public int maxDistToClosest(int[] seats) {
+            int max = 0;
+
+            int[] zone = new int[2];
+            for (int index = 0; index < seats.length; ) {
+                Arrays.fill(zone, -1);
+                index = nextFree(seats, index, zone);
+                if (zone[0] == 0 || zone[1] == seats.length - 1) {
+                    max = Math.max(max, zone[1] - zone[0] + 1);
+                } else {
+                    max = Math.max(max, (zone[1] - zone[0] + 2) / 2);
                 }
             }
-            int sum = candys[ratings.length - 1];
-            for (int i = ratings.length - 2; i >= 0; i--) {
-                if (ratings[i] > ratings[i + 1]) {
-                    candys[i] = Math.max(candys[i], candys[i + 1] + 1);
+
+            return max;
+        }
+
+        private int nextFree(int[] seats, int start, int[] zone) {
+            boolean enter = false;
+            for (int i = start, j = 0; i <= seats.length; i++) {
+                if (i < seats.length && seats[i] == 0) {
+                    if (!enter) {
+                        enter = true;
+                        j = i;
+                    }
+                } else {
+                    if (enter) {
+                        zone[0] = j;
+                        zone[1] = i - 1;
+                        return i + 1;
+                    }
                 }
-                sum += candys[i];
             }
-            return sum;
+            return seats.length;
         }
     }
 
     public static void main(String[] args) {
         Solution solution = new Solution();
-        System.out.println(solution.candy(new int[] {1, 3, 2, 2, 1}));
-//        System.out.println(solution.candy(new int[] {1, 2, 2}));
+        int s = solution.maxDistToClosest(new int[]{1,0,0,0,1,0,1});
+        System.out.println(s);
     }
 }
