Lintcode: The Smallest Difference

Given two array of integers(the first array is array A, the second array is array B), now we are going to find a element in array A which is A[i], and another element in array B which is B[j], so that the difference between A[i] and B[j] (|A[i] – B[j]|) is as small as possible, return their smallest difference.

---

Solution 1: 将两个array合并，排序后比较相邻的两个数即可

public class Solution {
    public int smallestDifference(int[] A, int[] B) {
        ArrayList<Node> nodes = new ArrayList<Node>(A.length + B.length);
        for (int a : A) {
            nodes.add(new Node(a, true));
        }
        for (int b : B) {
            nodes.add(new Node(b, false));
        }
        Collections.sort(nodes, new Comparator<Node>(){
            public int compare(Node n1, Node n2) {
                return n1.val - n2.val;
            }
        });
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nodes.size(); i++) {
            if (i + 1 < nodes.size() && nodes.get(i).fromA != nodes.get(i+1).fromA) {
                res = Math.min(res, nodes.get(i+1).val - nodes.get(i).val);
            }
        }
        return res;
    }
    class Node {
        int val;
        boolean fromA;
        public Node(int val, boolean fromA) {
            this.val = val;
            this.fromA = fromA;
        }
    }
}

Solution 2:将两个array分别排序，再用two pointers比较两个元素

public class Solution {
    public int smallestDifference(int[] A, int[] B) {
        Arrays.sort(A);
        Arrays.sort(B);
        int p1 = 0, p2 = 0;
        int res = Integer.MAX_VALUE;
        while (p1 < A.length && p2 < B.length) {
            if (A[p1]<=B[p2]) {
                res = Math.min(res, B[p2] - A[p1++]);
                if (p1< A.length && A[p1] > B[p2]) {
                    res = Math.min(res, A[p1] - B[p2]);
                }
            } else {
                res = Math.min(res, A[p1] - B[p2++]);
                if (p2 < B.length && B[p2] > A[p1]) {
                    res = Math.min(res, B[p2] - A[p1]);
                }
            }
        }
        return res;
    }
}

Lintcode: Median

非常基础的一道题，考的时quick select，但是不容易写对，一定要多练习！

public class Solution {
    public int median(int[] nums) {
        return sub(nums, 0, nums.length - 1, (nums.length + 1)/2);
    }
    private int sub(int[] nums, int start, int end, int size) {
        int mid = (start + end) / 2;
        int pivot = nums[mid];
        int i = start - 1, j = end + 1;
        for (int k = start; k < j; k++) {
            if (nums[k] < pivot) {
                i++;
                int tmp = nums[i];
                nums[i] = nums[k];
                nums[k] = tmp;
            } else if (nums[k] > pivot) {
                j--;
                int tmp = nums[j];
                nums[j] = nums[k];
                nums[k] = tmp;
                k--;
            }
        }
        if (i - start + 1 >= size) {
            return sub(nums, start, i, size);
        } else if (j - start >= size) {
            return nums[j-1];
        } else {
            return sub(nums, j, end, size - (j - start));
        }
    }
}

Lintcode: Median II

Numbers keep coming, return the median of numbers at every time a new number added.
Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is A[(n-1)/2].
用到了heap，i.e. Java里是priorityqueue，平时很少用到，需要练习。

public class Solution {
    public int[] medianII(int[] nums) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        class maxComparator implements Comparator<Integer> {
            public int compare(Integer a, Integer b) {
                return Integer.compare(b, a);
            }
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(nums.length, new maxComparator());
        int[] result = new int[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            if (minHeap.size() < maxHeap.size()) {
                if (nums[i] < maxHeap.peek()) {
                    minHeap.offer(maxHeap.poll());
                    maxHeap.offer(nums[i]);
                } else {
                    minHeap.offer(nums[i]);
                }
            } else {
                if (minHeap.size() > 0 && nums[i] > minHeap.peek()) {
                    maxHeap.offer(minHeap.poll());
                    minHeap.offer(nums[i]);
                } else {
                    maxHeap.offer(nums[i]);
                }
            }
            result[i] = maxHeap.peek();
        }
        return result;
    }
}

Lintcode: heapify

Given an integer array, heapify it into a min-heap array.
For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].
基础题，一定要熟练掌握

public class Solution {
    public void heapify(int[] A) {
        for (int i = A.length / 2; i >= 0; i--) {
        	heapify(A, i);
        }
    }

    private void heapify(int[] A, int i) {
    	if (i > A.length) {
    		return;
    	}
    	int left = i * 2 + 1 < A.length ? A[i*2+1] : Integer.MAX_VALUE;
    	int right = i * 2 + 2 < A.length ? A[i*2+2] : Integer.MAX_VALUE;
    	if (left < right && left < A[i]) {
    		A[i*2+1] = A[i];
    		A[i] = left;
    		heapify(A, i*2+1);
    	} else if (right <= left && right < A[i]) {
    		A[i*2+2] = A[i];
    		A[i] = right;
    		heapify(A, i*2+2);
    	}
    }
}

Leetcode & Lintcode: Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.
Solution 1: Lintcode 不能通过， parse number 出错，要用BigInteger

public class Solution {
    public String largestNumber(int[] num) {
        String[] strs = new String[num.length];
        for (int i = 0; i < num.length; i++) {
            strs[i] = String.valueOf(num[i]);
        }
        Arrays.sort(strs, new Comparator<String>() {
           public int compare(String a, String b) {
               return Integer.compare(Integer.valueOf(b+a), Integer.valueOf(a+b));
           } 
        });
        StringBuilder sb = new StringBuilder();
        for (String n : strs) {
            if (sb.length() > 0 || Integer.valueOf(n) != 0 ) {
                sb.append(n);
            }
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

Solution 2: 用BigInteger
public class Solution {
public String largestNumber(int[] num) {
if (num == null || num.length == 0) {
return “”;
}
String[] strs = new String[num.length];
for (int i = 0; i < num.length; i++) {
strs[i] = String.valueOf(num[i]);
}
Arrays.sort(strs, new Comparator() {
public int compare(String a, String b) {
return new BigInteger(b + a).compareTo(new BigInteger(a + b));
}
});
StringBuilder sb = new StringBuilder();
for (String s : strs) {
sb.append(s);
}
return sb.charAt(0) == ‘0’ ? “0” : sb.toString();
}
}

Codility 4.1 Number Of Disc Intersections

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A describing N discs as explained above, returns the number of pairs of intersecting discs.
The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

---

要考虑清楚overflow的情况，intervals里的值可能会超出integer范围。同时要记得自定义comparator的写法。
例如：
int a = Integer.MAX_VALUE;
long b = a + 1; 会溢出。需要将a写成(long)a才行。

import java.util.Comparator;
import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        long[][] intervals = new long[A.length][2];
        for (int i = 0; i < A.length; i++) {
            intervals[i][0] = (long)i - A[i];
            intervals[i][1] = (long)i + A[i];
        }
        Arrays.sort(intervals, new Comparator<long[]>() {
            public int compare(long[] a, long[] b) {
                return Long.compare(a[0],b[0]);
            }
        });
        int result = 0;
        for (int i = 0; i < A.length; i++) {
            result += findSub(intervals, intervals[i][1], i+1);
            if (result > 10000000) {
                return -1;
            }
        }
        return result;
    }
    private int findSub(long[][] intervals, long time, int index) {
        int start = index;
        int end = intervals.length - 1;
        int result = 0;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (intervals[mid][0] <= time) {
                result += mid - start + 1;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return result;
    }
}

11.2 Group anagrams

Write a method to sort an array of strings so that all the anagrams are next to each
other.

---

public void groupAnagrams(String[] array) {
	Map<String, List<String>> map = new HashMap<String, List<String>>();
	for (int i = 0; i < array.length; i++) {
		char[] chars = array[i].toCharArray();
		Arrays.sort(chars);
		String newStr = new String(chars);
		List<String> list = null;
		if (!map.containsKey(newStr)) {
			list = new ArrayList<String>();
		} else {
			list = map.get(newStr);
		}
		list.add(array[i]);
		map.put(newStr, list);
	}
	int index = 0;
	for (String key : map.keySet()) {
		List<String> list = map.get(key);
		for (String str : list) {
			array[index++] =  str;
		}
	}
}

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

---

题目的要求是用linear time。对于排序，能达到linear的算法有：bucket sort, radix sort 和 counting sort.这道题里用到了bucket sort。引自leetcode的solution “Suppose there are N elements and they range from A to B.
Then the maximum gap will be no smaller than ceiling[(B – A) / (N – 1)]
Let the length of a bucket to be len = ceiling[(B – A) / (N – 1)], then we will have at most num = (B – A) / len + 1 of bucket
for any number K in the array, we can easily find out which bucket it belongs by calculating loc = (K – A) / len and therefore maintain the maximum and minimum elements in each bucket.”
还是有不少细节要处理的。

public class Solution {
    public int maximumGap(int[] num) {
        if (num.length < 2) {
            return 0;
        }
        int max = num[0], min = num[0];
        for (int i = 1; i < num.length; i++) {
            max = Math.max(max, num[i]);
            min = Math.min(min, num[i]);
        }
        int bucketLen = (max - min) / (num.length - 1) + 1, bucketNo = (max - min) / bucketLen, result = 0;
        Map<Integer, List<Integer>> buckets = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < num.length; i++) {
            int bucketNumber = (num[i] - min) / bucketLen;
            if (buckets.containsKey(bucketNumber)) {
                List<Integer> list = buckets.get(bucketNumber);
                list.set(0, Math.min(list.get(0), num[i]));
                list.set(1, Math.max(list.get(1), num[i]));
            } else {
                List<Integer> list = new ArrayList<Integer>();
                list.add(num[i]);
                list.add(num[i]);
                buckets.put(bucketNumber, list);
            }
        }
        int prev = min;
        for (int i = 0; i < bucketNo; i++) {
            if (buckets.containsKey(i)) {
                result = Math.max(result, buckets.get(i).get(0) - prev);
                prev = buckets.get(i).get(1);
            }
        }
        result = Math.max(result, max - prev);
        return result;
    }
}

Leetcode & Lintcode: First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

---

counting sort的变形。
Solution 1: 不是constant space，比较好写

public class Solution {
    public int firstMissingPositive(int[] A) {
        boolean[] array = new boolean[A.length + 1];
        for (int a : A) {
            if (a <= A.length && a > 0) {
                array[a] = true;
            }
        }
        for (int i = 1; i < array.length; i++) {
            if (array[i] == false) {
                return i;
            }
        }
        return A.length + 1;
    }
}

Solution 2: 第一个for循环的几个条件比较难写对

public class Solution {
    public int firstMissingPositive(int[] A) {
        if (A == null || A.length == 0) {
            return 1;
        } 
        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0 && A[i] <= A.length && A[i] != i+1 && A[A[i]-1] != A[i]) {
                int tmp = A[A[i]-1];
                A[A[i]-1] = A[i];
                A[i--] = tmp;
            }
        }
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i+1) {
                return i+1;
            }
        }
        return A.length + 1;
    }
}

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

---

简单题， 先sort再合并。

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null) {
            return intervals;
        }
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        });
        List<Interval> result = new ArrayList<Interval>();
        for (int i = 0; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            Interval toCompare = result.size() == 0 ? null : result.get(result.size()-1);
            if (toCompare == null || cur.start > toCompare.end) {
                result.add(cur);
            } else if (cur.start <= toCompare.end && cur.end > toCompare.end) {
                toCompare.end = cur.end;
            }
        }
        return result;
    }
}