Leetcode: Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return [“0->2″,”4->5″,”7”].

---

public class Solution {
    public List<String> summaryRanges(int[] nums) {
    	List<String> res = new ArrayList<String>();
    	if (nums.length == 0) {
    		return res;
    	}
        int start = 0;
        for (int i = 1; i < nums.length; i++) {
        	if (nums[i] == nums[i-1] + 1) {
        		continue;
        	}
        	if (i - 1 == start) {
        		res.add(String.valueOf(nums[start]));
        	} else {
        		res.add(nums[start] + "->" + nums[i-1]);
        	}
        	start = i;
        }
        if (nums.length - 1 == start) {
    		res.add(String.valueOf(nums[start]));
    	} else {
    		res.add(nums[start] + "->" + nums[nums.length - 1]);
    	}
        return res;
    }
}

Implement Stack Using Queues

不容易写对

class MyStack {
    // Push element x onto stack.
    Queue<Integer> normalQueue = new LinkedList<Integer>();
    Queue<Integer> reverseQueue = new LinkedList<Integer>();
    public void push(int x) {
        if (!reverseQueue.isEmpty()) {
            normalQueue.offer(reverseQueue.poll());
        }
        normalQueue.offer(x);
    }

    // Removes the element on top of the stack.
    public void pop() {
        move();
        reverseQueue.poll();
    }

    // Get the top element.
    public int top() {
        move();
        return reverseQueue.peek();
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return normalQueue.isEmpty() && reverseQueue.isEmpty();
    }

    private void move() {
        if (reverseQueue.isEmpty()) {
            while (normalQueue.size() > 1) {
                reverseQueue.offer(normalQueue.poll());
            }
            Queue<Integer> tmp = reverseQueue;
            reverseQueue = normalQueue;
            normalQueue = tmp;
        }
    }
}

Leetcode: Rectangle Area

先算两个rectangle的面积，再减去重叠面积

public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int areaA = (C-A)*(D-B);
        int areaB = (G-E)*(H-F);
        int overLapWidth = 0;
        if (E <= C && G > A) {
            int leftBar = E < A ? A : E;
            int rightBar = G > C ? C : G;
            overLapWidth = rightBar-leftBar;
        }
        int overLapHeight = 0;
        if (F <= D && H > B) {
            int downBar = F < B ? B : F;
            int upBar = H > D ? D : H;
            overLapHeight = upBar - downBar;
        }
        return areaA -overLapHeight*overLapWidth + areaB; 
    }
}

Lintcode: Longest Words

class Solution {
    ArrayList<String> longestWords(String[] dictionary) {
        ArrayList<String> res = new ArrayList<String>();
        for (String str : dictionary) {
            if (res.isEmpty() || res.get(0).length() < str.length()) {
                res.clear();
                res.add(str);
            } else if (res.get(0).length() == str.length()) {
                res.add(str);
            }
        }
        return res;
    }
};

Leetcode: Maximal Square

和maximal rectangle类似，算面积的时候用长和宽的短边即可。

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        	return 0;
        }
        int[] store = new int[matrix[0].length];
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {
        	for (int j = 0; j < matrix[0].length; j++) {
        		if (matrix[i][j] == '0') {
        			store[j] = 0;
        		} else {
        			store[j]++;
        		}
        	}
        	res = Math.max(res, getRes(store));
        }
        return res;
    }
    private int getRes(int[] store) {
    	Stack<Integer> stack = new Stack<Integer>();
    	int res = 0;
    	for (int i = 0; i < store.length; i++) {
    		while (!stack.isEmpty() && store[i] < store[stack.peek()]) {
    			int index = stack.pop();
    			int height = store[index];
    			int preIndex = stack.isEmpty() ? -1 : stack.peek();
    			int width = i - preIndex - 1;
    			res = Math.max(res, height < width ? height*height : width *width);
    		}
    		stack.push(i);
    	}
    	while (!stack.isEmpty()) {
    		int index = stack.pop();
			int height = store[index];
			int preIndex = stack.isEmpty() ? -1 : stack.peek();
			int width = store.length - preIndex - 1;
    		res = Math.max(res, height < width ? height*height : width *width);
    	}
    	return res;
    }
}

Lintcode: Continuous Subarray Sum

public class Solution {
    public ArrayList<Integer> continuousSubarraySum(int[] A) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (A == null || A.length == 0) {
            return res;
        }
        int sum = A[0];
        int max = sum;
        int start = 0, end = 0;
        res.add(0);
        res.add(0);
        for (int i = 1; i < A.length; i++) {
            if (sum > max) {
                res.set(0, start);
                res.set(1, i-1);
                max = sum;
            }
            if (sum < 0) {
                sum = 0;
                start = i;
                end = i;
            }
            sum += A[i];
        }
        if (sum > max) {
            res.set(0, start);
            res.set(1, A.length-1);
        }
        return res;
    }
}

Lintcode: Nuts & Bolts Problem

quick sort非常好的题。用bolts[start]将nuts partition成两部分，得到中间值pivot，再用nuts[pivot]将bolts分成两部分。再对pivot两边进行recursion

public class Solution {
    public void sortNutsAndBolts(int[] nuts, int[] bolts) {
        if (nuts == null || nuts.length <= 1) {
            return;
        }
        sub(nuts, bolts, 0, bolts.length - 1);
    }
    private void sub(int[] nuts, int[] bolts, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = bolts[start];
        //sort nuts using bolt as pivot
        int index = sortNuts(nuts, pivot, start, end);
        //sort bolts using nuts[j-1] as pivot
        pivot = nuts[index];
        sortBolts(bolts, pivot, start, end);
        sub(nuts, bolts, start, index - 1);
        sub(nuts, bolts, index+1, end);
    }
    private int sortNuts(int[] nuts, int pivot, int start, int end) {
        int i = start-1, j = end+1;
        for (int index = start; index < j; index++) {
            if (Compare.cmp(nuts[index], pivot) == -1) {
                int tmp = nuts[++i];
                nuts[i] = nuts[index];
                nuts[index] = tmp;
            } else if (Compare.cmp(nuts[index], pivot) == 1) {
                int tmp = nuts[--j];
                nuts[j] = nuts[index];
                nuts[index] = tmp;
                index--;
            }
        }
        return j-1;
    }
    private int sortBolts(int[] bolts, int pivot, int start, int end) {
        int i = start-1, j = end+1;
        for (int index = start; index < j; index++) {
            if (Compare.cmp(pivot, bolts[index]) == -1) {
                int tmp = bolts[--j];
                bolts[j] = bolts[index];
                bolts[index] = tmp;
                index--;
            } else if (Compare.cmp(pivot, bolts[index]) == 1) {
                int tmp = bolts[++i];
                bolts[i] = bolts[index];
                bolts[index] = tmp;
            }
        }
        return j-1;
    }
};

Leetcode: Contains Duplicate III

用BST来维护前k个数，因此对于每个数，删除第i-k-1个数是lgn，得到ceiling和lower key分别是lgn，最后将当前数加入BST是lgn。

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null) {
            return false;
        }
        TreeMap<Long, Integer> map = new TreeMap<Long, Integer>();//pair: value-index
        for (int i = 0; i < nums.length; i++) {
            if (i > k) {
                map.remove((long)nums[i-k-1]);
            }
            long val = (long)nums[i];
            Long greater = map.ceilingKey(val);
            if (greater != null && greater - val <= t) {
                return true;
            }
            Long smaller = map.lowerKey(val);
            if (smaller != null && val - smaller <= t) {
                return true;
            }
            map.put(val, i);
        }
        return false;
    }
}

Leetcode: Contains Duplicate II

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }
}

Leetcode: The Skyline Problem & Lintcode: Building Outline

把每一个building拆成两个edge，一个入一个出。所有的edge加入到一个list中。再对这个list进行排序，排序顺序为：如果两个边的position不一样，那么按pos排，否则根据edge是入还是出来排。
根据position从前到后扫描每一个edge，将edge根据是入还是出来将当前height加入或者移除heap。再得到当前最高点来决定是否加入最终结果。非常巧妙，值得思考。

public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> res = new ArrayList<int[]>();
        if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
            return res;
        }
        List<Edge> edges = new ArrayList<Edge>();
        for (int[] building : buildings) {
            Edge startEdge = new Edge(building[0], building[2], true);
            edges.add(startEdge);
            Edge endEdge = new Edge(building[1], building[2], false);
            edges.add(endEdge);
        }
        //sort edges according to position, height, and if the edge is start or end
        edges.sort(new Comparator<Edge>(){
            public int compare(Edge l1, Edge l2) {
                if (l1.pos != l2.pos)
                    return Integer.compare(l1.pos, l2.pos);
                if (l1.isStart && l2.isStart) {
                    return Integer.compare(l2.height, l1.height);
                }
                if (!l1.isStart && !l2.isStart) {
                    return Integer.compare(l1.height, l2.height);
                }
                return l1.isStart ? -1 : 1;
            }
        });
        //heap of height
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(10, Collections.reverseOrder());
        for (Edge edge : edges) {
            if (edge.isStart) {
                if (heap.isEmpty() || edge.height > heap.peek()) {
                    res.add(new int[]{edge.pos, edge.height});
                }
                heap.add(edge.height);
            } else {
                heap.remove(edge.height);
                if (heap.isEmpty() || edge.height > heap.peek()) {
                    res.add(heap.isEmpty() ? new int[]{edge.pos,0} : new int[]{edge.pos, heap.peek()});
                }
            }
        }
        return res;
    }
    class Edge implements Comparable<Edge>{
        int pos;
        int height;
        boolean isStart;
        public Edge(int pos, int height, boolean isStart) {
            this.pos = pos;
            this.height = height;
            this.isStart = isStart;
        }
    }
}