1. Intersection of Two Arrays
   求兩個array的intersection，恰好昨天剛想了想這個問題肝集，一個方法是A的每個元素和B的每個元素做對比野舶，這種情況下復(fù)雜度為O(n^2), 并且還要考慮到重復(fù)元素的問題峦耘，用HashSet來解決可能有重復(fù)的問題砌们。
   另一種方法是先將兩個array排序，在用兩個pointer挪動來獲得intersection催烘，時間復(fù)雜度是O(n lg n)沥阱。但這種情況下一定要注意重復(fù)的問題。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0, j = 0;
        List<Integer> list = new ArrayList<>();
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                list.add(nums1[i]);
                while (i < nums1.length - 1 && nums1[i] == nums1[i+1]) {
                    i++;
                }
                while (j < nums2.length - 1 && nums2[j] == nums2[j+1]) {
                    j++;
                }
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        int[] res = new int[list.size()];
        int k = 0;
        for (int e: list) {
            res[k] = e;
            k++;
        }
        return res;
    }
}

2. Largest Number
   需要比較ab大還是ba大伊群，就把這兩個concat起來再比較考杉。
   答案中比較好的方法是把他們作為String來進行比較，而不要轉(zhuǎn)化為integer舰始。
   因為原來是個int array崇棠，也必須要轉(zhuǎn)化為integer array才能利用comparator進行比較。

class Solution {
    private class LargerNumberComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            String order1 = a + b;
            String order2 = b + a;
           return order2.compareTo(order1);
        }
    }

    public String largestNumber(int[] nums) {
        // Get input integers as strings.
        String[] asStrs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            asStrs[i] = String.valueOf(nums[i]);
        }

        // Sort strings according to custom comparator.
        Arrays.sort(asStrs, new LargerNumberComparator());

        // If, after being sorted, the largest number is `0`, the entire number
        // is zero.
        if (asStrs[0].equals("0")) {
            return "0";
        }

        // Build largest number from sorted array.
        String largestNumberStr = new String();
        for (String numAsStr : asStrs) {
            largestNumberStr += numAsStr;
        }

        return largestNumberStr;
    }
}

3. Valid Anagram
   判斷s是否是t的permutation丸卷。
   先檢查兩者的長度是否相同枕稀。
   因為只包含lower case，可以用一個array來記錄每個character出現(xiàn)的次數(shù)谜嫉。
   traverse s的時候增加萎坷，traverse t的時候減少。當(dāng)其中有個數(shù)量小于0沐兰，返回false哆档。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] chars = new int[26];
        for (char c: s.toCharArray()) {
            int index = c - 'a';
            chars[index] += 1;
        }
        for (char c: t.toCharArray()) {
            int index = c - 'a';
            chars[index] -= 1;
            if (chars[index] < 0) {
                return false;
            }
        }
        return true;
    }
}

4. Maximum Gap
   bucket sort
   t = (max - min)/(n-1)
   t 是所有元素的平均距離，至少有兩個元素的距離比t要大住闯，因此我們要找的maximum gap肯定不會存在于同一個bucket中的兩個元素瓜浸，而是相鄰的兩個bucket。

class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        int minNum = Integer.MAX_VALUE, maxNum = Integer.MIN_VALUE;
        for (int num: nums) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
        }
        // consider about the case all are the same
        int bucketSize = Math.max(1, (maxNum - minNum) / (nums.length - 1));
        // need to +1 to store the maximum element
        int numOfBucket = (maxNum - minNum)/bucketSize + 1;
        // store the maximum element of the bucket
        int[] max = new int[numOfBucket];
        int[] min = new int[numOfBucket];
        Arrays.fill(max, Integer.MIN_VALUE);
        Arrays.fill(min, Integer.MAX_VALUE);
        for (int num: nums) {
            int i = (num - minNum) / bucketSize;
            max[i] = Math.max(max[i], num);
            min[i] = Math.min(min[i], num);
        }
        int pre = max[0];
        int maxGap = 0;
        for (int j = 1; j < numOfBucket; j++) {
            if (pre == Integer.MIN_VALUE) {
                pre = max[j];
            } else {
                if (min[j] == Integer.MAX_VALUE) {
                    continue;
                } else {
                    maxGap = Math.max(maxGap, min[j] - pre);
                    pre = max[j];
                }
            }
        }
        return maxGap;
    }
}