Added 3 solutions & modified 1 solution

varunu28 · varunu28 · commit 9761fa07cc6c · 2019-07-03T19:01:38.000-07:00
diff --git a/Medium/Construct Quad Tree.java b/Medium/Construct Quad Tree.java
@@ -0,0 +1,52 @@
+/*
+// Definition for a QuadTree node.
+class Node {
+    public boolean val;
+    public boolean isLeaf;
+    public Node topLeft;
+    public Node topRight;
+    public Node bottomLeft;
+    public Node bottomRight;
+
+    public Node() {}
+
+    public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
+        val = _val;
+        isLeaf = _isLeaf;
+        topLeft = _topLeft;
+        topRight = _topRight;
+        bottomLeft = _bottomLeft;
+        bottomRight = _bottomRight;
+    }
+};
+*/
+class Solution {
+    public Node construct(int[][] grid) {
+        return helper(grid, 0, 0, grid.length);
+    }
+    
+    private Node helper(int[][] grid, int x, int y, int len) {
+        if (len == 1) {
+            return new Node(grid[x][y] != 0, true, null, null, null, null);
+        }
+        
+        Node result = new Node();
+        Node topLeft = helper(grid, x, y, len / 2);
+        Node topRight = helper(grid, x, y + len / 2, len / 2);
+        Node bottomLeft = helper(grid, x + len / 2, y, len / 2);
+        Node bottomRight = helper(grid, x + len / 2, y + len / 2, len / 2);
+        
+        if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf
+           && topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {
+            result.isLeaf = true;
+            result.val = topLeft.val;
+        } else {
+            result.topLeft = topLeft;
+            result.topRight = topRight;
+            result.bottomLeft = bottomLeft;
+            result.bottomRight = bottomRight;
+        }
+        
+        return result;
+    }
+}
diff --git a/Medium/Fraction to Recurring Decimal.java b/Medium/Fraction to Recurring Decimal.java
@@ -0,0 +1,39 @@
+class Solution {
+    public String fractionToDecimal(int numerator, int denominator) {
+        if (numerator == 0) {
+            return "0";
+        }
+        
+        StringBuilder fraction = new StringBuilder();
+        if (numerator < 0 ^ denominator < 0) {
+            fraction.append("-");
+        }
+        
+        long dividend = Math.abs(Long.valueOf(numerator));
+        long divisor = Math.abs(Long.valueOf(denominator));
+        
+        fraction.append(String.valueOf(dividend / divisor));
+        long remainder = dividend % divisor;
+        
+        if (remainder == 0) {
+            return fraction.toString();
+        }
+        
+        fraction.append('.');
+        Map<Long, Integer> map = new HashMap<>();
+        while (remainder != 0) {
+            if (map.containsKey(remainder)) {
+                fraction.insert(map.get(remainder), "(");
+                fraction.append(')');
+                break;
+            }
+            
+            map.put(remainder, fraction.length());
+            remainder *= 10;
+            fraction.append(String.valueOf(remainder / divisor));
+            remainder %= divisor;
+        }
+        
+        return fraction.toString();
+    }
+}
diff --git a/Medium/Interval List Intersections.java b/Medium/Interval List Intersections.java
@@ -1,48 +1,37 @@
-/**
- * Definition for an interval.
- * public class Interval {
- *     int start;
- *     int end;
- *     Interval() { start = 0; end = 0; }
- *     Interval(int s, int e) { start = s; end = e; }
- * }
- */
 class Solution {
-    public Interval[] intervalIntersection(Interval[] A, Interval[] B) {
-        int startA = 0;
-        int startB = 0;
-        int endA = A.length;
-        int endB = B.length;
-        
-        List<Interval> intervals = new ArrayList<>();
-        
-        while (startA < endA && startB < endB) {
-            if (A[startA].end < B[startB].start) {
-                startA++;
+    public int[][] intervalIntersection(int[][] A, int[][] B) {
+        List<int[]> intersections = new ArrayList<>();
+        int idx1 = 0;
+        int idx2 = 0;
+    
+        while (idx1 < A.length && idx2 < B.length) {
+            if (A[idx1][0] > B[idx2][1]) {
+                idx2++;
                 continue;
             }
             
-            if (A[startA].start > B[startB].end) {
-                startB++;
+            if (A[idx1][1] < B[idx2][0]) {
+                idx1++;
                 continue;
             }
             
-            int intervalStart = Math.max(A[startA].start, B[startB].start);
-            int intervalEnd = Math.min(A[startA].end, B[startB].end);
+            int maxStart = Math.max(A[idx1][0], B[idx2][0]);
+            int minEnd = Math.min(A[idx1][1], B[idx2][1]);
             
-            intervals.add(new Interval(intervalStart, intervalEnd));
+            int[] interval = {maxStart, minEnd};
+            intersections.add(interval);
             
-            if (A[startA].end < B[startB].end) {
-                startA++;
+            if (A[idx1][1] > B[idx2][1]) {
+                idx2++;
             }
             else {
-                startB++;
+                idx1++;
             }
         }
         
-        Interval[] ans = new Interval[intervals.size()];
-        for (int i=0; i<ans.length; i++) {
-            ans[i] = intervals.get(i);
+        int[][] ans = new int[intersections.size()][2];
+        for (int i = 0; i < intersections.size(); i++) {
+            ans[i] = intersections.get(i);
         }
         
         return ans;
diff --git a/Medium/Next Greater Node In Linked List.java b/Medium/Next Greater Node In Linked List.java
@@ -0,0 +1,47 @@
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public int[] nextLargerNodes(ListNode head) {
+        ListNode rev = reverse(head);
+        Stack<Integer> stack = new Stack<>();
+        List<Integer> list = new ArrayList<>();
+        
+        while (rev != null) {
+            while (!stack.isEmpty() && stack.peek() <= rev.val) {
+                stack.pop();
+            }
+            
+            list.add(stack.isEmpty() ? 0 : stack.peek());
+            stack.push(rev.val);
+            rev = rev.next;
+        }
+        
+        int[] arr = new int[list.size()];
+        for (int i = 0, j=list.size() - 1; i < list.size(); i++,j--) {
+            arr[i] = list.get(j);
+        }
+        
+        return arr;
+    }
+    
+    private ListNode reverse(ListNode head) {
+        ListNode curr = head;
+        ListNode prev = null;
+        ListNode next = null;
+        
+        while (curr != null) {
+            next = curr.next;
+            curr.next = prev;
+            prev = curr;
+            curr = next;
+        }
+        
+        return prev;
+    }
+}
