max number in sliding window

xiaoningning · xiaoningning · commit 11aec5af7a0e · 2012-07-21T22:20:27.000-07:00
diff --git a/MathOps/src/MathOps.java b/MathOps/src/MathOps.java
@@ -79,12 +79,37 @@ public static int divide(int dividend, int divisor) {
 
     }
 
+    public static int divide1(int dividend, int divisor) {
+        assert (divisor != 0);
+
+        boolean bNeg = false;
+        if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0))
+            bNeg = true;
+        long la = dividend;
+        long ula = la < 0 ? -la : la;
+        long lb = divisor;
+        long ulb = lb < 0 ? -lb : lb;
+
+        int msb = 0;
+        while ((ulb << msb) < ula) msb++;
+
+        int q = 0;
+        for (int i = msb; i >= 0; i--) {
+            if ((ulb << i) > ula) continue;
+            q |= (1 << i);
+            ula -= (ulb << i);
+        }
+        return bNeg ? -q : q;
+    }
+
     public static void main(String[] args) {
 
         System.out.println("add: " + add(6, -2));
         System.out.println("sqrt: " + sqrt(120.0));
         System.out.println("pow: " + pow(2.0, -3));
         System.out.println("divide: " + divide(-21474, 3));
+        System.out.println("divide: " + divide1(-10, 3));
+
 
     }
 }
diff --git a/PuzzleCoding/src/MaxInWindow.java b/PuzzleCoding/src/MaxInWindow.java
@@ -0,0 +1,50 @@
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.Queue;
+
+/**
+ * Given an array of numbers and a sliding window size,
+ * how to get the maximal numbers in all sliding windows?
+ * <p/>
+ * For example, if the input array is {2, 3, 4, 2, 6, 2, 5, 1}
+ * and the size of sliding windows is 3,
+ * the output of maximums are {4, 4, 6, 6, 6, 5}
+ */
+public class MaxInWindow {
+    public static void main(String[] args) {
+        int[] a = new int[]{2, 3, 4, 2, 6, 2, 5, 1};
+        int window = 3;
+        ArrayList<Integer> result = maxInWindow(a, window);
+        System.out.println(result.toString());
+    }
+
+    public static ArrayList<Integer> maxInWindow(int[] a, int windowSize) {
+        ArrayList<Integer> result = new ArrayList<Integer>();
+        Queue<Integer> maxIndexQueue = new LinkedList<Integer>();
+
+        if (a.length >= windowSize && windowSize > 1) {
+            int i = 0;
+            for (; i < windowSize; i++) {
+                while (!maxIndexQueue.isEmpty() && a[i] >= a[maxIndexQueue.peek()])
+                    maxIndexQueue.poll();
+
+                maxIndexQueue.add(i);
+            }
+
+            for (; i < a.length; i++) {
+                result.add(a[maxIndexQueue.peek()]);
+
+                while (!maxIndexQueue.isEmpty() && a[i] >= a[maxIndexQueue.peek()])
+                    maxIndexQueue.poll();
+
+                while (!maxIndexQueue.isEmpty() && maxIndexQueue.peek() <= i - windowSize)
+                    maxIndexQueue.poll();
+
+                maxIndexQueue.add(i);
+            }
+            result.add(maxIndexQueue.peek());
+        }
+
+        return result;
+    }
+}
