LeetCode 题目解答—— 第 311 到 371 题

public class Solution {
    public int getSum(int a, int b) {
        if (a==0)
            return b;

        int x = a ^ b;
        int c = (a & b) << 1;

        return getSum(c, x);
    }
}

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        if (nums.length==0)
            return new ArrayList<>();

        // lens[i] means the largest divisible subset which is in asc sort and ended with nums[i]
        List<List<Integer>> lens = new ArrayList<>();

        Arrays.sort(nums);
        List<Integer> first = new ArrayList<>(1);
        first.add(nums[0]);
        lens.add(first);

        for (int i=1; i<nums.length; i++) {
            Integer maxIndex = null;

            for (int j=0; j<i; j++) {
                List<Integer> list = lens.get(j);
                if (maxIndex!=null && list.size() <= lens.get(maxIndex).size())
                    continue;

                int prevMax = list.get(list.size()-1);
                if (nums[i] % prevMax == 0) {
                    maxIndex = j;
                }
            }

            List<Integer> newList;
            if (maxIndex==null)
                newList = new ArrayList<>();
            else
                newList = new ArrayList<>(lens.get(maxIndex));

            newList.add(nums[i]);
            lens.add(newList);
        }

        List<Integer> result = null;
        for (List<Integer> list : lens) {
            if (result==null || result.size()<list.size())
                result = list;
        }

        return result;
    }
}

public class Solution {
    public boolean isPerfectSquare(int num) {
        if (num==0 || num==1)
            return true;

        int half = num/2;
        for (long i=half; i>0; i--) { // long
            if (i*i>num)
                continue;
            else if (i*i==num)
                return true;
            else
                return false;
        }

        return false;
    }
}

public class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        //limit brought by the statement that water is finallly in one or both buckets
        if(x + y < z) return false;
        //case x or y is zero
        if( x == z || y == z || x + y == z ) return true;

        //get GCD, then we can use the property of Bézout's identity
        return z%GCD(x, y) == 0;
    }

    public int GCD(int a, int b){
        while(b != 0 ){
            int temp = b;
            b = a%b;
            a = temp;
        }
        return a;
    }
}

/* first  consider the situation matrix is 1D
    we can save every sum of 0~i(0<=i<len) and binary search previous sum to find 
    possible result for every index, time complexity is O(NlogN).
    so in 2D matrix, we can sum up all values from row i to row j and create a 1D array 
    to use 1D array solution.
    If col number is less than row number, we can sum up all values from col i to col j 
    then use 1D array solution.
*/
public int maxSumSubmatrix(int[][] matrix, int target) {
    int row = matrix.length;
    if(row==0)return 0;
    int col = matrix[0].length;
    int m = Math.min(row,col);
    int n = Math.max(row,col);
    //indicating sum up in every row or every column
    boolean colIsBig = col>row;
    int res = Integer.MIN_VALUE;
    for(int i = 0;i<m;i++){
        int[] array = new int[n];
        // sum from row j to row i
        for(int j = i;j>=0;j--){
            int val = 0;
            TreeSet<Integer> set = new TreeSet<Integer>();
            set.add(0);
            //traverse every column/row and sum up
            for(int k = 0;k<n;k++){
                array[k]=array[k]+(colIsBig?matrix[j][k]:matrix[k][j]);
                val = val + array[k];
                //use  TreeMap to binary search previous sum to get possible result 
                Integer subres = set.ceiling(val-target);
                if(null!=subres){
                    res=Math.max(res,val-subres);
                }
                set.add(val);
            }
        }
    }
    return res;
}

public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        int total = 0;
        if (n>0)
            total += countNumbersWithUniqueDigits(n-1);
        else
            return 1;

        if (n>10)
            return total;

        int product = 1;
        int numberToSelect = 10;
        for (int i=n; i>=1 ; i--) {
            // the highest digit, 0 is disallowed
            if (i==n) {
                product *= 9;
            } else {
                product *= numberToSelect;
            }
            numberToSelect--;
        }

        return total + product;
    }
}

class TweetItem implements Comparable<TweetItem> {
    int time;
    int tweetId;

    public TweetItem (int time, int tweetId) {
        this.time = time;
        this.tweetId = tweetId;
    }

    @Override
    public int compareTo(TweetItem that) {
        if (this.time < that.time)
            return 1;
        else if (this.time == that.time)
            return 0;
        else
            return -1;
    }
}

public class Twitter {
    private Map<Integer, List<TweetItem>> tweets = new HashMap<>();
    private Map<Integer, Set<Integer>> follows = new HashMap<>();
    private int time = 0;
    private static int RECENT_TWEET_COUNT = 10;

    /** Initialize your data structure here. */
    public Twitter() {

    }

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if (!tweets.containsKey(userId))
            tweets.put(userId, new ArrayList<>());

        tweets.get(userId).add(new TweetItem(time++, tweetId));
    }

    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> set;
        if (!follows.containsKey(userId))
            set = new HashSet<>();
        else
            set = follows.get(userId);

        // himself/herself
        set.add(userId);

        List<TweetItem> newTweets = new ArrayList<>();
        for (int fId : set) {
            if (!tweets.containsKey(fId))
                continue;

            List<TweetItem> subList;
            if (tweets.get(fId).size() > RECENT_TWEET_COUNT){
                // latest 10 records
                subList = tweets.get(fId).subList(tweets.get(fId).size()-RECENT_TWEET_COUNT, tweets.get(fId).size());
            } else {
                subList = tweets.get(fId).subList(0, tweets.get(fId).size());
            }

            newTweets.addAll(subList);
        }

        Collections.sort(newTweets);
        List<TweetItem> subTweets;
        if (newTweets.size() > RECENT_TWEET_COUNT) {
            subTweets = newTweets.subList(0, RECENT_TWEET_COUNT);
        } else {
            subTweets = newTweets;
        }

        List<Integer> retList = new ArrayList<>();
        for (TweetItem item : subTweets) {
            retList.add(item.tweetId);
        }

        return retList;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        if (!follows.containsKey(followerId))
            follows.put(followerId, new HashSet<>());

        follows.get(followerId).add(followeeId);
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if (!follows.containsKey(followerId))
            return;

        follows.get(followerId).remove(followeeId);
    }
}

public class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null)
            throw new IllegalArgumentException();

        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] left, int[] right) {
                if (left[0] != right[0]) {
                    return left[0] - right[0];
                } else {
                    return left[1] - right[1];
                }
            }
        });

        int max = 0;
        int[] numberArray = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; i++) {
            numberArray[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                    numberArray[i] = Math.max(numberArray[i], numberArray[j] + 1);
                }
            }
            max = Math.max(max, numberArray[i]);
        }

        return max;
    }
}

public class SummaryRanges {
    private static final Integer RANGE_START = 0;
    private static final Integer RANGE_END = 1;
    private static final Integer RANGE_START_AND_END = 2;

    private TreeMap<Integer, Integer> tm = new TreeMap<>();

    /** Initialize your data structure here. */
    public SummaryRanges() {
    }

    public void addNum(int val) {
        Map.Entry<Integer, Integer> ceiling = tm.ceilingEntry(val);
        Map.Entry<Integer, Integer> floor = tm.floorEntry(val);

        if (ceiling == null && floor == null) { // case 1: the tree map is empty
            tm.put(val, RANGE_START_AND_END);
        } else if (ceiling == null) { // case 2: put the value at the end of the ranges
            if (floor.getKey() == val) {
                ;
            } else if (floor.getKey() == val-1) {
                tm.put(val, RANGE_END);
                if (floor.getValue() == RANGE_END)
                	tm.remove(floor.getKey());
                else // floor.getValue() == RANGE_START_AND_END
                	tm.put(floor.getKey(), RANGE_START);
            } else {
                tm.put(val, RANGE_START_AND_END);
            }
        } else if (floor == null) { // case 3: put the value at the beginning of the ranges
            if (ceiling.getKey() == val) {
                ;
            } else if (ceiling.getKey() == val+1) {
                tm.put(val, RANGE_START);
                if (ceiling.getValue() == RANGE_START)
                	tm.remove(ceiling.getKey());
                else // ceiling.getValue() == RANGE_START_AND_END
                	tm.put(ceiling.getKey(), RANGE_END);
            } else {
                tm.put(val, RANGE_START_AND_END);
            }
        } else if (floor.getKey() == val || ceiling.getKey() == val) { // case 4: the value is already existed as the boundary of a range
            ;
        } else if (floor.getKey() == val-1) { // case 5: the value extends a lower range
            if (floor.getValue() == RANGE_START){
                ;
            } else {
                if (floor.getValue() == RANGE_END) {
                    tm.remove(floor.getKey());
                } else { // floor.getValue() == RANGE_START_AND_END
                    tm.put(val-1, RANGE_START);
                }

                if (ceiling.getKey() == val+1) {
                    if (ceiling.getValue() == RANGE_START) {
                        tm.remove(ceiling.getKey());
                    } else { // ceiling.getValue() == RANGE_START_AND_END
                        tm.put(val+1, RANGE_END);
                    }
                } else {
                    tm.put(val, RANGE_END);
                }
            }
        } else if (ceiling.getKey() == val+1) { // case 6: the value extends a higher range
            if (ceiling.getValue() == RANGE_END) {
                ;
            } else {
                if (ceiling.getValue() == RANGE_START) {
                    tm.remove(ceiling.getKey());
                } else { // ceiling.getValue == RANGE_START_AND_END
                    tm.put(val+1, RANGE_END);
                }

                if (floor.getKey() == val-1) {
                    if (floor.getValue() == RANGE_END) {
                        tm.remove(floor.getKey());
                    } else { // floor.getValue == RANGE_START_AND_END
                        tm.put(val-1, RANGE_START);
                    }
                } else {
                    tm.put(val, RANGE_START);
                }
            }
        } else { // case 7: single point
            tm.put(val, RANGE_START_AND_END);
        }
    }

    public List<Interval> getIntervals() {
        List<Interval> list = new ArrayList<>();
        Interval inter = null;
        for (Map.Entry<Integer, Integer> entry : tm.entrySet()) {
            if (entry.getValue() == RANGE_START_AND_END) {
                list.add(new Interval(entry.getKey(), entry.getKey()));
            } else if (entry.getValue() == RANGE_START) {
                inter = new Interval();
                inter.start = entry.getKey();
            } else {
                inter.end = entry.getKey();
                list.add(inter);
            }
        }

        return list;
    }
}

public class SummaryRanges {
    TreeMap<Integer, Interval> tree;

    public SummaryRanges() {
        tree = new TreeMap<>();
    }

    public void addNum(int val) {
        if(tree.containsKey(val)) return;
        Integer l = tree.lowerKey(val);
        Integer h = tree.higherKey(val);
        if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) {
            tree.get(l).end = tree.get(h).end;
            tree.remove(h);
        } else if(l != null && tree.get(l).end + 1 >= val) {
            tree.get(l).end = Math.max(tree.get(l).end, val);
        } else if(h != null && h == val + 1) {
            tree.put(val, new Interval(val, tree.get(h).end));
            tree.remove(h);
        } else {
            tree.put(val, new Interval(val, val));
        }
    }

    public List<Interval> getIntervals() {
        return new ArrayList<>(tree.values());
    }
}

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums1) {
            if (!map.containsKey(num))
                map.put(num, 0);

            map.put(num, map.get(num)+1);
        }

        List<Integer> list = new ArrayList<>();
        for (int num : nums2) {
            Integer val = map.get(num);
            if (val!=null && val!=0) {
                list.add(num);
                map.put(num, val-1);
            }
        }

        int[] ret = new int[list.size()];
        for (int i=0; i<list.size(); i++) {
            ret[i] = list.get(i);
        }

        return ret;
    }
}

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1==null || nums2==null)
            throw new IllegalArgumentException();

        Set<Integer> set2 = new HashSet<>();
        for (int n : nums2) {
            set2.add(n);
        }

        Set<Integer> set3 = new HashSet<>();
        for (int n : nums1) {
            if (set2.contains(n))
                set3.add(n);
        }

        int[] intersection = new int[set3.size()];
        int i=0;
        for (int n : set3) {
            intersection[i] = n;
            i++;
        }

        return intersection;
    }
}

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        if (nums==null || nums.length==0 || k<=0)
            return new ArrayList<>();

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.get(num) == null)
                map.put(num, 0);

            map.put(num, map.get(num)+1);
        }

        TreeMap<Integer, Set<Integer>> reverseMap = new TreeMap<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (reverseMap.get(entry.getValue()) == null)
                reverseMap.put(entry.getValue(), new HashSet<>());

            Set<Integer> set = reverseMap.get(entry.getValue());
            set.add(entry.getKey());
            reverseMap.put(entry.getValue(), set);
        }

        List<Integer> ret = new ArrayList<>(k);
        while(k>0) {
            Integer key = reverseMap.lastKey();
            if (key==null)
                break;

            Set<Integer> set = reverseMap.get(key);
            reverseMap.remove(key);

            if (set.size()<=k) {
                ret.addAll(set);
                k -= set.size();
            }
            else {
                for (int s : set) {
                    ret.add(s);

                    k--;
                    if (k==0)
                        break;
                }
            }
        }

        return ret;
    }
}

public class Solution {
    public String reverseVowels(String s) {
        if (null==s)
            return s;

        int i=0, j=s.length()-1;
        char[] arr = s.toCharArray();
        while (i<j) {
            if (!isVowel(arr[i])) {
                i++;
                continue;
            }

            if (!isVowel(arr[j])) {
                j--;
                continue;
            }

            swap(arr, i, j);
            i++;
            j--;
        }

        return new String(arr);
    }

    private boolean isVowel(char c) {
        return c=='a' || c=='e' || c=='i' || c=='o' || c=='u' || c=='A' || c=='E' || c=='I' || c=='O' || c=='U';
    }

    private void swap(char[] arr, int i, int j) {
        arr[i] ^= arr[j];
        arr[j] ^= arr[i];
        arr[i] ^= arr[j];
    }
}

public class Solution {
    public String reverseString(String s) {
        if (null==s)
            return null;

        int len = s.length();
        char[] arr = new char[len];
        for (int i=len-1; i>=0; i--) {
            arr[len-i-1] = s.charAt(i);
        }

        return new String(arr);
    }
}

public class Solution {
    public int integerBreak(int n) {
        int max = -1;
        for (int k=2; k<=n; k++) {
            int res = cal(n, k);
            if (res>max)
                max = res;
            else
                return max;
        }

        return max;
    }

    private int cal(int n, int k) {
        int c = n/k;
        int adding = (n - c*k);
        int result = 1;

        if (c==0)
            return -1;

        for (int i=1; i<=k; i++) {
            if (adding>0) {
                adding--;
                result *= c+1;
            }
            else {
                result *= c;
            }
        }

        return result;
    }
}

public class Solution {
    public boolean isPowerOfFour(int num) {
        if(num<=0)
            return false;

        // powers of 2
        // 10000000...
        if ((num & (num-1)) != 0)
            return false;

        //  4^n - 1 = (4-1) (4^(n-1) + 4^(n-2) + 4^(n-3) + ... + 4 + 1)
        if ((num-1) % 3 != 0)
            return false;

        return true;
    }
}

class Item {
    List<NestedInteger> list;
    int index;
}
public class NestedIterator implements Iterator<Integer> {

    private boolean checked;
    private Integer nextVal;
    private Stack<Item> stack = new Stack<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        checked = false;
        nextVal = null;

        Item item = new Item();
        item.list = nestedList;
        item.index = 0;

        stack.push(item);
    }

    private void check() {
        if (stack.isEmpty()) {
            checked = true;
            nextVal = null;
            return;
        }

        Item item = stack.peek();
        if (item.list.size()<=item.index) {
            stack.pop();
            this.check();
        } else {
            NestedInteger nestedInteger = item.list.get(item.index);
            item.index++;

            if (nestedInteger.isInteger()) {
                nextVal = nestedInteger.getInteger();
                checked = true;
            } else {
                Item subItem = new Item();
                subItem.list = nestedInteger.getList();
                subItem.index = 0;

                stack.push(subItem);
                this.check();
            }
        }
    }

    @Override
    public Integer next() {
        if (!checked)
            this.check();

        return nextVal;
    }

    @Override
    public boolean hasNext() {
        this.check();

        return nextVal != null;
    }
}

public class Solution {
    public int[] countBits(int num) {
        if (num==0)
            return new int[]{0};
        else if (num==1)
            return new int[]{0, 1};

        int cycleCount = 1;
        int pos = 0;
        int[] array = new int[num+1];
        array[0] = 0;
        array[1] = 1;

        int cycleLength = (int)Math.pow(2, cycleCount);
        for (int i=2; i<array.length; i++) {
            array[i] = array[pos] + 1;
            pos++;

            if (pos>=cycleLength) {
                pos = 0;
                cycleCount++;
                cycleLength = (int)Math.pow(2, cycleCount);
            }
        }

        return array;
    }
}

public class Solution {
    public int rob(TreeNode root) {
        return rob(root, true, new HashMap<>(), new HashMap<>());
    }

    private int rob(TreeNode root, boolean robbable, Map<TreeNode, Integer> robbedCache, Map<TreeNode, Integer> unrobbedCache) {
        if (root==null)
            return 0;

        int robbed = 0;
        if (robbable) {
            if (robbedCache.get(root) != null) {
                robbed = robbedCache.get(root);
            } else {
                robbed += root.val;
                robbed += rob(root.left, false, robbedCache, unrobbedCache);
                robbed += rob(root.right, false, robbedCache, unrobbedCache);

                robbedCache.put(root, robbed);
            }
        }

        int unrobbed = 0;
        if (unrobbedCache.get(root) != null) {
            unrobbed = unrobbedCache.get(root);
        } else {
            unrobbed += rob(root.left, true, robbedCache, unrobbedCache);
            unrobbed += rob(root.right, true, robbedCache, unrobbedCache);

            unrobbedCache.put(root, unrobbed);
        }

        return Math.max(robbed, unrobbed);
    }
}

class Node {
    Character ch;
    Map<Character, Node> nextMap = new HashMap<>();
    String word;

    public Node(Character ch) {
        this.ch = ch;
    }

    @Override
    public String toString() {
        return "\"" + word + "\"-" + nextMap;
    }
}
public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        Map<String, Integer> stringToIndex = new HashMap<>();

        Map<String, String> toReversed = new HashMap<>();
        Map<String, String> toOriginal = new HashMap<>();

        // key: reversed word, value: end node in the word letters iteration tree
        Map<String, Node> stringToNodeForward = new HashMap<>();
        // key: word, value: end node in the word letters backward iteration tree
        Map<String, Node> stringToNodeBackward = new HashMap<>();

        Node forwardRoot = new Node(null);
        Node backwardRoot = new Node(null);

        for (int i=0; i<words.length; i++) {
            String word = words[i];
            stringToIndex.put(word, i);

            // forward
            Node cursor = forwardRoot;
            for (int j=0; j<word.length(); j++) {
                Character ch = word.charAt(j);
                if (!cursor.nextMap.containsKey(ch))
                    cursor.nextMap.put(ch, new Node(ch));

                cursor = cursor.nextMap.get(ch);
            }
            String reverse = new StringBuilder(word).reverse().toString();
            toReversed.put(word, reverse);
            toOriginal.put(reverse, word);

            cursor.word = word;
            stringToNodeForward.put(reverse, cursor);

            // backward
            cursor = backwardRoot;
            for (int j=word.length()-1; j>=0; j--) {
                Character ch = word.charAt(j);
                if (!cursor.nextMap.containsKey(ch))
                    cursor.nextMap.put(ch, new Node(ch));

                cursor = cursor.nextMap.get(ch);
            }
            cursor.word = word;
            stringToNodeBackward.put(word, cursor);
        }

        List<List<Integer>> list = new ArrayList<>();
        for (String word : words) {
            // case 1
            String reverse = toReversed.get(word);
            Node node = getNode(reverse, forwardRoot);

            if (node != null) {
                Set<String> set = new HashSet<>();
                recursiveSearch(node, set, word.length(), true);

                for (String p : set) {
                    List<Integer> item = new ArrayList<>(2);
                    item.add(stringToIndex.get(p));
                    item.add(stringToIndex.get(word));

                    if (item.get(0) != item.get(1)) // filter out the map to itself
                        list.add(item);
                }
            }

            // case 2
            node = getNode(word, backwardRoot);

            if (node != null) {
                Set<String> set = new HashSet<>();
                recursiveSearch(node, set, word.length(), false);

                for (String p : set) {
                    List<Integer> item = new ArrayList<>(2);
                    item.add(stringToIndex.get(word));
                    item.add(stringToIndex.get(p));

                    if (item.get(0) != item.get(1)) // filter out the map to itself
                        list.add(item);
                }
            }
        }

        return list;
    }

    private Node getNode(String s, Node root) {
        Node n = root;
        for (int i=0; i<s.length(); i++) {
            Character ch = s.charAt(i);
            Node next = n.nextMap.get(ch);
            if (next != null)
                n = next;
            else
                return null;
        }

        return n;
    }

    private void recursiveSearch(Node node, Set<String> set, int baseLength, boolean forward) {
        if (node == null)
            return;

        if (node.word != null) {
            String rest = null;
            if (forward)
                rest = node.word.substring(baseLength);
            else if (node.word.length() != baseLength) // dedup
                rest = node.word.substring(0, node.word.length() - baseLength);

            // if the rest is palindrome
            if (rest != null && new StringBuilder(rest).reverse().toString().equals(rest))
                set.add(node.word);
        }

        for (Node next : node.nextMap.values())
            recursiveSearch(next, set, baseLength, forward);
    }
}

public class Solution {
    public boolean isSelfCrossing(int[] x) {
        if (x==null || x.length<4)
            return false;

        boolean shrink;
        if (x[2] <x[0])
            shrink = true;
        else if (x[2] > x[0])
            shrink = false;
        else if (x[3] < x[1])
            shrink = true;
        else if (x[3] > x[1])
            shrink = false;
        else
            return true; // rectangle

        boolean inflateToShrink = false;

        for (int i=3; i<x.length; i++) {
            if (shrink) {
                if (x[i] > x[i-2]) // 1
                    return true;
                else if (x[i] == x[i-2] && x[i-1] == x[i-3]) // 2
                    return true;
                else // 3
                    ;
            } else {
            	if (x[i] == x[i-2] && x[i-1] == x[i-3]) { // 4
                    return true;
                } else if (i == 3) {
                	if (x[i] == x[i-2]) // 5
                		inflateToShrink = true;
                	else if (x[i] < x[i-2]) // 6
                		shrink = true;
                	else // 7
                	    ;
            	} else if (x[i] < x[i-2]) {
                	if (x[i] + x[i-4] < x[i-2]) { // 8
                        shrink = true;
                    } else {
                    	if (inflateToShrink) // 9
                    		return true;
                    	else // 10
                    		inflateToShrink = true;
                    }
                } else { // 11
                    ;
                }
            }
        }

        return false;
    }
}

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums==null || nums.length<3)
            return false;

        int first = 0, second = -1, third = -1;
        // if there is already first and second number found (nums[first]<nums[second]),
        // and if another number x occurs and x < nums[first],
        // then we don't know if x should be put in the triplet if there is, so we put its index in a "firstBackup" variable temporarily
        int firstBackup = -1;
        for (int i=1; i<nums.length; i++) {
            // increasing
            if (nums[i]>nums[i-1]) {
                if (second==-1) {
                    second = i;
                } else {
                    if (nums[i]>nums[second])
                        return true;
                    else
                        second = i;
                }
            }
            // decreasing
            else {
                if (second==-1) {
                    if (nums[i]<=nums[first])
                        first = i;
                    else
                        second = i;
                } else {
                    if (nums[i]>nums[second]) {
                        return true; // unreachable, impossible case
                    } else {
                        if (nums[i]>nums[first]) {
                            if (firstBackup != -1) {
                                first = firstBackup;
                                firstBackup = -1;
                            }
                            second = i;
                        } else {
                            if (firstBackup==-1 || nums[i]<firstBackup)
                                firstBackup = i;
                            else
                                ; // ignore
                        }
                    }
                }
            }
        }

        return false;
    }
}

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        List<String> result = new ArrayList<>();
        if (null==tickets)
            return null;
        else if(tickets.length==0)
            return result;

        Map<String, Boolean> visited = new HashMap<>();
        Map<String, List<String>> paths = new HashMap<>();
        for (String[] pair : tickets) {
            if (!paths.containsKey(pair[0]))
                paths.put(pair[0], new ArrayList<String>());

            paths.get(pair[0]).add(pair[1]);
            visited.put(pair[0]+pair[1], false);
        }

        for (List<String> list : paths.values()) {
            Collections.sort(list);
        }

        String key = "JFK";
        result.add(key);
        if (traverse(paths, visited, key, result))
            return result;
        else
            return null;
    }

    private boolean traverse(Map<String, List<String>> paths, Map<String, Boolean> visited, String key, List<String> result) {
        if (result.size()-1 == visited.size())
            return true;

        List<String> list = paths.get(key);
        if (list==null)
            return false;

        for (String val : list) {
            String visitedKey = key+val;
            if (!visited.get(visitedKey)) {
                visited.put(visitedKey, true);
                result.add(val);

                if (traverse(paths, visited, val, result)) {
                    return true;
                } else {
                    result.remove(result.size()-1);
                    visited.put(visitedKey, false);
                    continue;
                }
            }
        }

        return false;
    }
}

// All nodes except entrance and exit should have the same indegree and outdegree,
// if a node indegree-1 == outdegree, it's the exit, and it's also the exit of "while" and the recursion
// 
// use PriorityQueue so there's no need to sort the list explicitly
public class Solution {
    private Map<String, PriorityQueue<String>> targets = new HashMap<>();
    private List<String> route = new LinkedList<String>();

    public List<String> findItinerary(String[][] tickets) {
        for (String[] pair : tickets) {
            if (targets.get(pair[0]) == null)
                targets.put(pair[0], new PriorityQueue<String>());

            targets.get(pair[0]).add(pair[1]);
        }

        this.visit("JFK");
        return route;
    }

    private void visit(String airport) {
        while(targets.containsKey(airport) && !targets.get(airport).isEmpty())
            this.visit(targets.get(airport).poll());
        route.add(0, airport);
    }
}

class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder==null)
            return false;

        String[] arr = preorder.split(",");
        // (from, to]
        return verify(arr, 0, arr.length, new Boolean[arr.length][arr.length]);
    }

    private boolean verify(String[] arr, int from, int to, Boolean[][] cache) {
        if (from==to) {
            return true;
        } else if (from+2==to) {
            return false;
        }
        else if (from+1==to) {
            if ("#".equals(arr[from]))
                return true;
            else
                return false;
        }

        if (cache[from][to-1] != null)
            return cache[from][to-1];

        String root = arr[from];
        if ("#".equals(root)) {
            cache[from][to-1] = false;
            return false;
        }

        for (int i=from+2; i<to; i++) {
            // a tree must be ended with "#"
            if (!"#".equals(arr[i-1]))
                continue;

            boolean left = verify(arr, from+1, i, cache);
            if (!left)
                continue;

            boolean right = verify(arr, i, to, cache);

            if (right) {
                cache[from][to-1] = true;
                return true;
            }
        }

        cache[from][to-1] = false;
        return false;
    }
}

class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        int diff = 1;
        for (String node: nodes) {
            if (--diff < 0) return false;
            if (!node.equals("#")) diff += 2;
        }
        return diff == 0;
    }
}

public class Solution {
    public int minPatches(int[] nums, int n) {
        // the index indicates [1, x] needs to be covered; use long to avoid overflow
        long x = 1;
        // the index in nums
        int index = 0;
        // for now [1, max] can be covered
        long max = 0;
        int patch = 0;

        while (x<=n) {
            // a new number is needed to cover x
            if (max<x) {
                // no more existing number, or the next number can't cover max+1
                if (index>=nums.length || nums[index]>max+1) {
                    // patch needed, and the patch number is max+1
                    max = max + (max+1);
                    patch++;
                } else {
                    // the new range from max to (max+nums[index]) can be covered because
                    // before now from 1 to max can be covered, and now there's a new number nums[index]
                    // so adding nums[index] to previous range [1, max] we'll get a new covered range [nums[index]+1, nums[index]+max],
                    // union both above to get the range [1, max+nums[index]]
                    max = max + nums[index];
                    index++;
                }
            } else {
                // no new number needed
                x = max+1;
            }
        }

        return patch;
    }
}

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix==null)
            return 0;

        int h = matrix.length;
        if (h==0)
            return 0;

        int w = matrix[0].length;
        if (w==0)
            return 0;

        int[][] lenMap = new int[h][w];
        int max = 0;
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                max = Math.max(max, getLen(matrix, i, j, lenMap));
            }
        }
        return max;
    }

    private int getLen(int[][] matrix, int i, int j, int[][] lenMap) {
        int h = matrix.length;
        int w = matrix[0].length;

        if (i<0 || i>=h || j<0 || j>=w)
            return 0;

        if (lenMap[i][j]>0)
            return lenMap[i][j];

        int len = 1;

        if (i+1<h && matrix[i][j]<matrix[i+1][j]) {
            int down = getLen(matrix, i+1, j, lenMap);
            len = Math.max(len, down+1);
        }

        if (j+1<w && matrix[i][j]<matrix[i][j+1]) {
            int right = getLen(matrix, i, j+1, lenMap);
            len = Math.max(len, right+1);
        }

        if (i-1>=0 && matrix[i][j]<matrix[i-1][j]) {
            int up = getLen(matrix, i-1, j, lenMap);
            len = Math.max(len, up+1);
        }

        if (j-1>=0 && matrix[i][j]<matrix[i][j-1]) {
            int left = getLen(matrix, i, j-1, lenMap);
            len = Math.max(len, left+1);
        }

        lenMap[i][j] = len;
        return lenMap[i][j];
    }
}

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = new ListNode(0);
        ListNode tailOdd = odd;
        ListNode even = new ListNode(0);
        ListNode tailEven = even;

        boolean isOdd = true;
        ListNode cur = head;
        while (cur != null) {
            if (isOdd) {
                tailOdd.next = cur;
                tailOdd = cur;
            } else {
                tailEven.next = cur;
                tailEven = cur;
            }

            cur = cur.next;
            isOdd = !isOdd;
        }

        tailOdd.next = even.next;
        tailEven.next = null;

        return odd.next;
    }
}

public class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        long[] sums = new long[n + 1];
        for (int i = 0; i < n; ++i)
            sums[i + 1] = sums[i] + nums[i];
        return countWhileMergeSort(sums, 0, n + 1, lower, upper);
    }

    private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {
        if (end - start <= 1) return 0;
        int mid = (start + end) / 2;
        int count = countWhileMergeSort(sums, start, mid, lower, upper) 
                  + countWhileMergeSort(sums, mid, end, lower, upper);
        int j = mid, k = mid, t = mid;
        long[] cache = new long[end - start];
        for (int i = start, r = 0; i < mid; ++i, ++r) {
            while (k < end && sums[k] - sums[i] < lower) k++;
            while (j < end && sums[j] - sums[i] <= upper) j++;
            while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
            cache[r] = sums[i];
            count += j - k;
        }
        System.arraycopy(cache, 0, sums, start, t - start);
        return count;
    }
}

public class Solution {
    private Set<Integer> all = new HashSet<>();
    public Solution() {
        int upperLimit = Integer.MAX_VALUE/3;
        int n=1;
        while(true) {
            all.add(n);
            if (n<upperLimit)
                n = n*3;
            else
                break;
        }
    }
    public boolean isPowerOfThree(int n) {
        return all.contains(n);
    }
}

// time: O(nlogn), space: O(n)
public class Solution {
    public void wiggleSort(int[] nums) {
        // clone and sort
        int[] copy = nums.clone();
        Arrays.sort(copy);

        int index = copy.length-1;

        // fill in nums with odd index, going backward in array copy:
        // they're all large numbers
        for (int i=1; i<nums.length; i+=2) {
            nums[i] = copy[index];
            index--;
        }

        // fill in nums with even index, going backward in array copy:
        // they're all small numbers
        for (int i=0; i<nums.length; i+=2) {
            nums[i] = copy[index];
            index--;
        }
    }
}

public class Solution {
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        return coin(coins, coins.length-1, amount, new int[coins.length][amount+1]);
    }

    private int coin(int[] coins, int pos, int amount, int[][] cache) {
        if (amount==0)
            return 0;

        if (cache[pos][amount]!=0)
            return cache[pos][amount];

        int min = -1;
        for (int i=pos; i>=0; i--) {
            if (coins[i]>amount)
                continue;

            int count = coin(coins, i, amount-coins[i], cache);
            if (count!=-1 && (count<min || min==-1))
                min = count;
        }

        if (min!=-1)
            min++;

        cache[pos][amount] = min;
        return min;
    }
}

class Item {
    int[] data;
}
public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        Item[][][] dp = new Item[nums1.length+1][nums2.length+1][k+1];

        Item result = maxNumber(nums1, nums2, 0, 0, k, dp);
        return result.data;
    }

    private Item maxNumber(int[] nums1, int[] nums2, int x, int y, int k, Item[][][] dp) {
        if (dp[x][y][k]!=null)
            return dp[x][y][k];

        Item item = new Item();
        if (k==0) {
            item.data = new int[]{};
            dp[x][y][k] = item;
            return item;
        }

        if (nums1.length-x + nums2.length-y < k)
            return null;

        // case 1: pick from nums1
        Item pickNums1 = null;
        if (x<nums1.length)
            pickNums1 = buildItem(nums1[x], maxNumber(nums1, nums2, x+1, y, k-1, dp));

        // case 2: pick from nums2
        Item pickNums2 = null;
        if (y<nums2.length)
            pickNums2 = buildItem(nums2[y], maxNumber(nums1, nums2, x, y+1, k-1, dp));

        // case 3: pass in nums1
        Item passNums1 = null;
        if (x<nums1.length)
            passNums1 = maxNumber(nums1, nums2, x+1, y, k, dp);

        // case 4: pass in nums2
        Item passNums2 = null;
        if (y<nums2.length)
            passNums2 = maxNumber(nums1, nums2, x, y+1, k, dp);

        // choose the largest one
        Item result = max(pickNums1, pickNums2, passNums1, passNums2);
        dp[x][y][k] = result;
        return result;
    }

    private Item buildItem(int num, Item item) {
        if (item==null)
            return null;

        Item newItem = new Item();
        newItem.data = new int[item.data.length+1];
        System.arraycopy(item.data, 0, newItem.data, 1, item.data.length);
        newItem.data[0] = num;

        return newItem;
    }

    private Item max(Item... items) {
        Item max = null;
        for (Item item : items) {
            boolean result = compare(max, item);
            if (!result)
                max = item;
        }

        return max;
    }

    private boolean compare(Item a, Item b) {
        if (b==null) return true;
        if (a==null) return false;
        if (a.data.length > b.data.length) return true;
        if (a.data.length < b.data.length) return false;
        for (int i=0; i<a.data.length; i++) {
            if (a.data[i] > b.data[i])
                return true;
            if (a.data[i] < b.data[i])
                return false;
        }

        return true;
    }
}

public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] ans = new int[k];
        for (int i = Math.max(k - nums2.length, 0); i <= Math.min(nums1.length, k); i++) {
            int[] res1 = get_max_sub_array(nums1, i);
            int[] res2 = get_max_sub_array(nums2, k - i);
            int[] res = new int[k];
            int pos1 = 0, pos2 = 0, tpos = 0;

            while (pos1 < res1.length || pos2 < res2.length) {
                res[tpos++] = greater(res1, pos1, res2, pos2) ? res1[pos1++] : res2[pos2++];
            }

            if (!greater(ans, 0, res, 0))
                ans = res;
        }

        return ans;
    }

    public boolean greater(int[] nums1, int start1, int[] nums2, int start2) {
        for (; start1 < nums1.length && start2 < nums2.length; start1++, start2++) {
            if (nums1[start1] > nums2[start2]) return true;
            if (nums1[start1] < nums2[start2]) return false;
        }
        return start1 != nums1.length;
    }

    public int[] get_max_sub_array(int[] nums, int k) {
        int[] res = new int[k];
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            while (len > 0 && len + nums.length - i > k && res[len - 1] < nums[i]) {
                len--;
            }
            if (len < k)
                res[len++] = nums[i];
        }
        return res;
    }
}

Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.

public class Solution {
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }
}

public class Solution {
    public int maxProduct(String[] words) {
        // bit map
        List<Integer> list = new ArrayList<>();
        for (String w : words) {
            int num = 0;
            for (int i=0; i<w.length(); i++) {
                num = num | getMask(w.charAt(i));
            }
            list.add(num);
        }

        int max = 0;
        for (int i=0; i<list.size(); i++) {
            for (int j=i+1; j<list.size(); j++) {
                if ( ( list.get(i).intValue() & list.get(j).intValue() ) != 0 )
                    continue;

                max = Math.max(words[i].length() * words[j].length(), max);
            }
        }

        return max;
    }

    private int getMask(char c) {
        return 1 << (c - 'a');
    }
}

public class Solution {
    public String removeDuplicateLetters(String s) {
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if (!map.containsKey(ch))
                map.put(ch, new ArrayList<>());

            map.get(ch).add(i);
        }

        int lastPos = -1;
        Map<Character, Integer> posMap = new HashMap<>();
        for (int i=0; i<26; i++) {
            char ch = (char)('a' + i);
            if (!map.containsKey(ch))
                continue;

            if (lastPos==-1) {
                lastPos = map.get(ch).get(0);
            } else {
                List<Integer> list = map.get(ch);
                if (list.get(list.size()-1) > lastPos) {
                    lastPos = binarySearch(map.get(ch), lastPos);
                } else {
                    lastPos = map.get(ch).get(0);
                }
            }

            posMap.put(ch, lastPos);
        }

        List<Character> resultList = new LinkedList<>();
        for (Map.Entry<Character, Integer> entry : posMap.entrySet()) {
            char ch = entry.getKey();
            int pos = entry.getValue();

            int insertPos = 0;
            while(insertPos<resultList.size() && pos>posMap.get(resultList.get(insertPos)))
                insertPos++;

            resultList.add(insertPos, ch);
        }

        String result = "";
        for (char ch : resultList) {
            result += ch;
        }

        return result;
    }

    private int binarySearch(List<Integer> list, int pivot) {
        int left = 0;
        int right = list.size()-1;
        while (left<=right) {
            int mid = (left+right)/2;
            if (list.get(mid)>pivot)
                right = mid - 1;
            else
                left = mid + 1;
        }

        return list.get(left);
    }
}

public class Solution {
    public String removeDuplicateLetters(String s) {
        int[] cnt = new int[26];
        int pos = 0;
        for (int i = 0; i < s.length(); i++)
            cnt[s.charAt(i) - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos))
                pos = i;
            if (--cnt[s.charAt(i) - 'a'] == 0)
                break;
        }
        return s.length() == 0 ? "" : s.charAt(pos)
            + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
    }
}

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> sorted = new ArrayList<>(nums.length);
        List<Integer> result = new ArrayList<>(nums.length);
        for (int i=nums.length-1; i>=0; i--) {
            int index = insert(nums[i], sorted);
            result.add(0, index);
        }

        return result;
    }

    private int insert(int num, List<Integer> sorted) {
        if (sorted.isEmpty()) {
            sorted.add(num);
            return 0;
        }

        int left = 0;
        int right = sorted.size() - 1;
        while(left<=right) {
            int mid = (left+right)/2;
            if (sorted.get(mid)>=num) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }

        sorted.add(left, num);
        return left;
    }
}

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        if (n<=0 || primes==null || primes.length==0)
            throw new IllegalArgumentException();

        int[] arr = new int[n];
        arr[0] = 1;

        // each prime owns its dedicated index on arr
        int[] indexArr = new int[primes.length];

        for (int i=1; i<n; i++) {
            int min = Integer.MAX_VALUE;
            int posToIncrease = -1;
            for (int j=0; j<primes.length; j++) {
                int index = indexArr[j];
                int prime = primes[j];

                if (prime*arr[index] < min) {
                    min = prime * arr[index];
                    posToIncrease = j;
                }
            }

            indexArr[posToIncrease] += 1;
            // dedup
            if(arr[i-1] == min)
                i--;
            else
                arr[i] = min;
        }

        return arr[arr.length-1];
    }
}

    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
   coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

public class Solution {
    public int maxCoins(int[] nums) {
        int[] clone = new int[nums.length + 2];
        clone[0] = 1;
        clone[nums.length + 1] = 1;
        for (int i = 0; i < nums.length; i++)
            clone[i + 1] = nums[i];

        int[][] cache = new int[nums.length + 2][nums.length + 2];
        return maxCoins(clone, 1, nums.length, cache);
    }

    public int maxCoins(int[] nums, int from, int to, int[][] cache) {
        if (cache[from][to] > 0)
            return cache[from][to];

        int max = 0;
        for (int i = from; i <= to; i++) {
            int leftPart = maxCoins(nums, from, i - 1, cache);
            int rightPart = maxCoins(nums, i + 1, to, cache);

            max = Math.max(max, leftPart + nums[from - 1] * nums[i] * nums[to + 1] + rightPart);
        }

        cache[from][to] = max;
        return max;
    }
}