Implement a fix-sized queue using array

Implement a fix-sized queue using array.


import java.util.*;

public class Queue<T> {
private int front;
private int rear;
private int size;
private final T[] queue;

public Queue(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("Size cannot be less than or equal to zero.");
}
size = 0;
front = 0;
rear = -1;
queue = (T[])new Object[capacity];
}

public int size() {
return size;
}

public void enQueue(T item) {
if (size == queue.length) {
throw new IllegalStateException("Queue is full.");
}
rear = (rear + 1) % queue.length;
queue[rear] = item;
size++;
}

public T deQueue() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty.");
}
T value = queue[front];
front = (front + 1) % queue.length;
size--;
return value;
}

public boolean isEmpty() {
return size == 0;
}

public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Queue is Empty.");
}
return queue[front];
}

@Override
public String toString() {
int s = size;
int head = front;
String str = "[";
while (s > 1) {
str += queue[head];
str += ", ";
s--;
head = (head + 1) % queue.length;
}
if (s == 1) {
str += queue[head];
}
str += "]";
return str;
}

    public static void main(String[] args) {
        Queue<Integer> newQueue = new Queue<>(5);
        newQueue.enQueue(10);
        newQueue.enQueue(20);
        newQueue.enQueue(30);
        newQueue.enQueue(40);
        newQueue.enQueue(50);
        System.out.println(newQueue.toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.toString());
        newQueue.enQueue(60);
        newQueue.enQueue(70);
        System.out.println("Size should be 5, the result is " + newQueue.size());
        System.out.println("Should be false, the result is " + newQueue.isEmpty());
        System.out.println(newQueue.toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.deQueue().toString());
        System.out.println(newQueue.toString());
        System.out.println("Size should be 0, the result is " + newQueue.size());
        System.out.println("Should be true, the result is " + newQueue.isEmpty());
    }
}

Roman to Integer

/*

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

*/

//time: O(n), space:O(1)
public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int res = map.get(s.charAt(s.length() - 1));
        for (int i = s.length() - 2; i >= 0; i--) {
            if (map.get(s.charAt(i)) >= map.get(s.charAt(i + 1))) {
                res += map.get(s.charAt(i));
            } else {
                res -= map.get(s.charAt(i));
            }
        }
        return res;
    }
}

Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

//DFS, time:O(n^2), space:O(1)
public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        subsetsHelper(nums, ans, new ArrayList<Integer>(), 0);
        return ans;
    }
    public void subsetsHelper(int[] nums, List<List<Integer>> ans,                                 List<Integer> list, int start) {
        ans.add(new ArrayList<Integer>(list));
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            subsetsHelper(nums, ans, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}


/*
bfs:
First, adding an empty list to the ans, then iterate the input array, each time adding the number to all the existed subsets. The new subsets and the previous subsets together make up the new ans. 

time:O(n^2), space:O(1)
*/

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        List<Integer> list = new ArrayList<>();
        ans.add(list);
        for (int i = 0; i < nums.length; i++) {
            int size = ans.size();
            for (int j = 0; j < size; j++) {
                list = new ArrayList<>(ans.get(j));
                list.add(nums[i]);
                ans.add(list);
            }
        }
        return ans;
    }
}

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

/*

A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Also, we can use three pointers with one pass solution. In each step during the iteration, we do either of three things. Swap with the left, swap with the right, or move forward.

time:O(n), space:O(1)

*/

public class Solution {

    public void sortColors(int[] nums) {

        if (nums == null || nums.length == 0) {

            return;

        }

        int left = 0;

        int right = nums.length - 1;

        int i = 0;

        while (i <= right) {

            if (nums[i] == 1) {

                i++;

            } else if (nums[i] == 0) {

                swap(nums, left, i); 

                left++;

                i++;

            } else {

                swap(nums, right, i);

                right--;

            }

        }

    }

    public void swap(int[] nums, int a, int b) {

        int tmp = nums[a];

        nums[a] = nums[b];

        nums[b] = tmp;

    }

}

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { 
 *        label = x; 
 *        neighbors = new ArrayList<UndirectedGraphNode>(); 
 *     }
 * };
 */

/*
Use Queue to implement BFS and use HashMap to deep clone every graph node and connect their neighbors.

time:O(V+E), space:O(V), E is the number of neighbors, V is the number of nodes.
*/

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        queue.offer(node);
        map.put(node, new UndirectedGraphNode(node.label));
        while (!queue.isEmpty()) {
            UndirectedGraphNode curr = queue.poll();
            for (UndirectedGraphNode neighbor : curr.neighbors) {
                if (!map.containsKey(neighbor)) {
                    queue.offer(neighbor);
                    map.put(neighbor, new UndirectedGraphNode(neighbor.label));
                }
                map.get(curr).neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);
    }
}


//DFS, time:O(V+E), space:O(V)
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        return deepClone(map, node);
    }
    public UndirectedGraphNode deepClone(Map<UndirectedGraphNode,                                              UndirectedGraphNode> map, UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        if (map.containsKey(node)) {
            return map.get(node);
        }
        map.put(node, new UndirectedGraphNode(node.label)); 
        for (UndirectedGraphNode neighbor : node.neighbors) {
            map.get(node).neighbors.add(deepClone(map, neighbor));
        }
        return map.get(node);
    }

}

First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

/* The isBadVersion API is defined in the parent class VersionControl.

      boolean isBadVersion(int version); */

/*

time:O(logn), space:O(1)

*/

public class Solution extends VersionControl {

    public int firstBadVersion(int n) {

        if (n <= 0) {

            return 0;

        }

        int left = 1;

        int right = n;

        while (left + 1 < right) {

            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {

                right = mid;

            } else {

                left = mid;

            }

        }

        if (isBadVersion(left)) {

            return left;

        }

        return right;

    }

}

Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

/**

 * Your BSTIterator will be called like this:

 * BSTIterator i = new BSTIterator(root);

 * while (i.hasNext()) v[f()] = i.next();

 */

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

/*

Every time, we call next(), we will traverse to find the left most TreeNode of the current node if existed. If the current node is null, then we pop out a node from the stack and return its value. The first time we call next(), it takes O(h) time, but the other TreeNode in the stack will take only O(1) time when call the next(). And there are h TreeNode in the stack. So the average time complexity will be O(1) and space complexity will be O(h).

hasNext() and next(): time:O(1), space:O(h)

*/

public class BSTIterator {

    public Stack<TreeNode> stack = new Stack<>();

    public TreeNode root;

    public BSTIterator(TreeNode root) {

        this.root = root;

    }

    /** @return whether we have a next smallest number */

    public boolean hasNext() {

        return root != null || !stack.isEmpty();

    }

    /** @return the next smallest number */

    public int next() {

        while (root != null) {

            stack.push(root);

            root = root.left;

        }

        root = stack.pop();

        TreeNode node = root;

        root = root.right;

        return node.val;

    }

}