add 335

fishercoder1534 · fishercoder1534 · commit ffe2aee721d1 · 2017-07-29T08:54:44.000-07:00
diff --git a/README.md b/README.md
@@ -264,6 +264,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |338|[Counting Bits](https://leetcode.com/problems/counting-bits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_338.java)| O(nlogn)|O(h) | Medium| 
 |337|[House Robber III](https://leetcode.com/problems/house-robber-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_337.java)| O(n)|O(n)| Medium | DP
 |336|[Palindrome Pairs](https://leetcode.com/problems/palindrome-pairs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_336.java)| O(n^2)|O(n) | Hard|
+|335|[Self Crossing](https://leetcode.com/problems/self-crossing/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_335.java)| O(n)|O(1) | Hard| Math
 |334|[Increasing Triplet Subsequence](https://leetcode.com/problems/increasing-triplet-subsequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_334.java)| O(n^2)|O(1) | Medium|
 |333|[Largest BST Subtree](https://leetcode.com/problems/largest-bst-subtree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_333.java)| O(n)|O(n) | Medium| Tree 
 |332|[Reconstruct Itinerary](https://leetcode.com/problems/reconstruct-itinerary/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_332.java)| O(n)|O(n) | Medium| Graph, DFS
diff --git a/src/main/java/com/fishercoder/solutions/_335.java b/src/main/java/com/fishercoder/solutions/_335.java
@@ -0,0 +1,71 @@
+package com.fishercoder.solutions;
+
+/**
+ * 335. Self Crossing
+ *
+ * You are given an array x of n positive numbers.
+ * You start at point (0,0) and moves x[0] metres to the north,
+ * then x[1] metres to the west,
+ * x[2] metres to the south,
+ * x[3] metres to the east and so on.
+ * In other words, after each move your direction changes counter-clockwise.
+
+ Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.
+
+ Example 1:
+ Given x =
+ [2, 1, 1, 2]
+ ,
+ ?????
+ ?   ?
+ ???????>
+ ?
+
+ Return true (self crossing)
+ Example 2:
+ Given x =
+ [1, 2, 3, 4]
+ ,
+ ????????
+ ?      ?
+ ?
+ ?
+ ?????????????>
+
+ Return false (not self crossing)
+ Example 3:
+ Given x =
+ [1, 1, 1, 1]
+ ,
+ ?????
+ ?   ?
+ ?????>
+
+ Return true (self crossing)
+
+ */
+public class _335 {
+
+    /**reference: https://discuss.leetcode.com/topic/38014/java-oms-with-explanation/2*/
+    public boolean isSelfCrossing(int[] x) {
+        int l = x.length;
+        if (l <= 3) return false;
+
+        for (int i = 3; i < l; i++) {
+            if (x[i] >= x[i - 2] && x[i - 1] <= x[i - 3]) {
+                return true;  //Fourth line crosses first line and onward
+            }
+            if (i >= 4) {
+                if (x[i - 1] == x[i - 3] && x[i] + x[i - 4] >= x[i - 2]) {
+                    return true; // Fifth line meets first line and onward
+                }
+            }
+            if (i >= 5) {
+                if (x[i - 2] - x[i - 4] >= 0 && x[i] >= x[i - 2] - x[i - 4] && x[i - 1] >= x[i - 3] - x[i - 5] && x[i - 1] <= x[i - 3]) {
+                    return true;  // Sixth line crosses first line and onward
+                }
+            }
+        }
+        return false;
+    }
+}
