Added 5 solutions

varunu28 · varunu28 · commit ad9e9cd2063c · 2018-10-10T11:15:03.000-07:00
diff --git a/Easy/Max Stack.java b/Easy/Max Stack.java
@@ -0,0 +1,57 @@
+class MaxStack {
+
+    /** initialize your data structure here. */
+    PriorityQueue<Integer> pr;
+    List<Integer> list;
+    public MaxStack() {
+        pr = new PriorityQueue<>((a,b) -> b-a);
+        list = new ArrayList<>();
+    }
+
+    public void push(int x) {
+        pr.add(x);
+        list.add(x);
+    }
+
+    public int pop() {
+        int res = list.get(list.size()-1);
+        list.remove(list.size()-1);
+        pr.remove(res);
+        return res;
+    }
+
+    public int top() {
+        return list.get(list.size()-1);
+    }
+
+    public int peekMax() {
+        return pr.peek();
+    }
+
+    public int popMax() {
+        int res = pr.poll();
+        int i = list.size()-1;
+
+        while (i >= 0) {
+            if (list.get(i) == res) {
+                break;
+            }
+
+            i--;
+        }
+
+        list.remove(i);
+
+        return res;
+    }
+}
+
+/**
+ * Your MaxStack object will be instantiated and called as such:
+ * MaxStack obj = new MaxStack();
+ * obj.push(x);
+ * int param_2 = obj.pop();
+ * int param_3 = obj.top();
+ * int param_4 = obj.peekMax();
+ * int param_5 = obj.popMax();
+ */
diff --git a/Medium/Binary Tree Longest Consecutive Sequence.java b/Medium/Binary Tree Longest Consecutive Sequence.java
@@ -0,0 +1,40 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public int longestConsecutive(TreeNode root) {
+        if (root == null) {
+            return 0;
+        }
+        
+        int[] ans = {1};
+        helper(root, ans, null, 1);
+        
+        return ans[0];
+    }
+    
+    private void helper(TreeNode root, int[] ans, TreeNode parent, int count) {
+        if (root == null) {
+            return;
+        }
+        
+        if (parent != null) {
+            if (root.val == parent.val + 1) {
+                count++;
+                ans[0] = Math.max(ans[0], count);
+            }
+            else {
+                count = 1;
+            }
+        }
+        
+        helper(root.left, ans, root, count);
+        helper(root.right, ans, root, count);
+    }
+}
diff --git a/Medium/Coin Change 2.java b/Medium/Coin Change 2.java
@@ -0,0 +1,14 @@
+class Solution {
+    public static int change(int amount, int[] coins) {
+        int[] combinations = new int[amount+1];
+        combinations[0] = 1;
+
+        for (int coin : coins) {
+            for (int i=coin; i<amount+1; i++) {
+                combinations[i] += combinations[i-coin];
+            }
+        }
+
+        return combinations[amount];
+    }
+}
diff --git a/Medium/Design Phone Directory.java b/Medium/Design Phone Directory.java
@@ -0,0 +1,49 @@
+class PhoneDirectory {
+
+    /** Initialize your data structure here
+     @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
+    int[] directory;
+    int pos;
+    public PhoneDirectory(int maxNumbers) {
+        directory = new int[maxNumbers];
+        for (int i=0; i<maxNumbers; i++) {
+            directory[i] = (i+1)%maxNumbers;
+        }
+        pos = 0;
+    }
+
+    /** Provide a number which is not assigned to anyone.
+     @return - Return an available number. Return -1 if none is available. */
+    public int get() {
+        if (directory[pos] == -1) {
+            return -1;
+        }
+
+        int val = pos;
+        pos = directory[pos];
+        directory[val] = -1;
+        return val;
+    }
+
+    /** Check if a number is available or not. */
+    public boolean check(int number) {
+        return directory[number] != -1;
+    }
+
+    /** Recycle or release a number. */
+    public void release(int number) {
+        if (directory[number] != -1) {
+            return;
+        }
+        directory[number] = pos;
+        pos = number;
+    }
+}
+
+/**
+ * Your PhoneDirectory object will be instantiated and called as such:
+ * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
+ * int param_1 = obj.get();
+ * boolean param_2 = obj.check(number);
+ * obj.release(number);
+ */
diff --git a/Medium/Implement Trie (Prefix Tree).java b/Medium/Implement Trie (Prefix Tree).java
@@ -0,0 +1,73 @@
+class Trie {
+
+    Node trie;
+    /** Initialize your data structure here. */
+    public Trie() {
+        trie = new Node("");
+    }
+
+    /** Inserts a word into the trie. */
+    public void insert(String word) {
+        Node curr = trie;
+        for(int i=0; i<word.length(); i++) {
+            if (!curr.childrens.containsKey(word.charAt(i))) {
+                curr.childrens.put(word.charAt(i), new Node(word.substring(0, i+1)));
+            }
+
+            curr = curr.childrens.get(word.charAt(i));
+
+            if (i == word.length() - 1) {
+                curr.isWord = true;
+            }
+        }
+    }
+
+    /** Returns if the word is in the trie. */
+    public boolean search(String word) {
+        Node curr = trie;
+        for (int i=0; i<word.length(); i++) {
+            if (curr.childrens.containsKey(word.charAt(i))) {
+                curr = curr.childrens.get(word.charAt(i));
+            }
+            else {
+                return false;
+            }
+        }
+
+        return curr.isWord;
+    }
+
+    /** Returns if there is any word in the trie that starts with the given prefix. */
+    public boolean startsWith(String prefix) {
+        Node curr = trie;
+
+        for (int i=0; i<prefix.length(); i++) {
+            if (curr.childrens.containsKey(prefix.charAt(i))) {
+                curr = curr.childrens.get(prefix.charAt(i));
+            }
+            else {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+    private static final class Node {
+        String prefix;
+        Map<Character, Node> childrens;
+        boolean isWord;
+
+        public Node(String prefix) {
+            this.prefix = prefix;
+            this.childrens = new HashMap<>();
+        }
+    }
+}
+/**
+ * Your Trie object will be instantiated and called as such:
+ * Trie obj = new Trie();
+ * obj.insert(word);
+ * boolean param_2 = obj.search(word);
+ * boolean param_3 = obj.startsWith(prefix);
+ */
