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

老规矩，跳过需要付费的题目。题目是越来越不好做，我尽量把自己的思路写下来。

Sum of Two Integers

【题目】

Calculate the sum of two integers   a   and   b , but you are   not allowed   to use the operator   +   and   - .

Example:
Given   a   = 1 and   b   = 2, return 3.

【解答】俩数相加，不许用加减号。

不能用加减号，于是考虑用位操作。但是怎样做呢？考虑位操作的几种方式，与、或、非、异或、左移、右移，哪些可以联合起来模拟加法呢？

1. 首先a和b异或一下得到x，因为每一位上相加，如果两个都是0，结果就是0，如果两个都是1，结果还是0，只有一个1一个0，结果才是1。
2. 但是单单异或是不够的，因为这样做完全没有考虑进位的问题。于是a和b与一下，因为每一位上相加，如果都是0，不需要进位，如果一个1一个0，也不需要进位，只有两个都是1才需要进位。相与之后还需要左移一位，因为进位的关系，进位的”1″必须要作用在更高一位才有用。
3. 上面这两个结果，作为新的参数继续去调用getSum计算，反复进行，直到没有进位为止。

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);
    }
}

Largest Divisible Subset

【题目】 Given a set of   distinct   positive integers, find the largest subset such that every pair (S _i , S _j ) of elements in this subset satisfies: S _i   % S _j   = 0 or S _j   % S _i   = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]

【解答】要找这样的一个子集合，使得所有元素都可以互为整除或者被整除的关系。

在一切开始前，大脑里面大致有这样一个方向：我需要把nums排序，然后从较小的一端开始逐个审查归类，因为每查看一个新数的时候，我应该在手边有一个不断构建着的集合，这个集合根据整除关系包含了若干个分类，而且里面的数都比当前审查的数小，所以我会挨个从集合里拿出数来去尝试整除这个被审查数，根据结果去更新这个集合。

于是我建立这样一个数据结构：一个list，其中第i个元素表示以nums[i]作为最大值且必须包含它的最大分类；而每个分类又是由一串数组成，它们互为整除或被整除关系，并且升序排列。为什么要升序排列？因为排列以后，每个分类最大的那个数，可以作为分类的代表，如果有新数要比较，和它比就可以，如果它和新数存在前面提到的整除关系，那么这个分类中任何一个数都会和新数存在整除关系。这一点是解题的关键。

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;
    }
}

Valid Perfect Square

【题目】 Given a positive integer   num , write a function which returns True if   num   is a perfect square else False.

Note:   Do not   use any built-in library function such as   sqrt .

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

【解答】判断一个数是不是完全平方数。

我记得小时候老师就说，要证明一个大于1的数x是不是完全平方数，可以从x/2开始试起，慢慢减小。这个可以减小计算量。结论应该是对的，但是需要证明一下以严谨一点：

x^2 – 2*x = x^2 – 2*x + 1 – 1 = (x-1)^2 -1 >= -1, when x>=2 it’s >= 0

so x^2 >= 2*x when x>=2

好了，这就可以写代码了。使用long型，防止平方的时候溢出：

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;
    }
}

Water and Jug Problem

【题目】 You are given two jugs with capacities   x   and   y   litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly   z   litres using these two jugs.

If   z   liters of water is measurable, you must have   z   liters of water contained within   one or both buckets   by the end.

Operations allowed:

• Fill any of the jugs completely with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1:   (From the famous   “Die Hard”   example )

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

【解答】看起来很熟悉，小学里就接触这一类问题的简单版。有两个壶，分别可以装x和y升水，能提供无限水的情况下，问能不能弄出z升水来。

题目描述那么简单，通用性那么强，很容易给人一个“数学定理”的感觉。事实上，还真有一个数学定理来帮助解决这个问题，如果不知道那个定理，这个题目做起来就会非常痛苦，如果知道，那就非常简单。这个定理，就叫做 裴蜀定理 （维基百科上有证明）：

对任何整数a、b和它们的最大公约数d，关于未知数x和y的裴蜀等式：

ax + by = m

有整数解时当且仅当m是d的倍数。

裴蜀等式有解时必然有无穷多个整数解。

而这个问题，就可以映射到上面这个式子中去。于是我们可以求这两个壶容量的最大公约数，看看要弄出的水升数z是不是这个最大公约数的倍数。这种题居然不是hard真是天理难容……

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;
    }
}

Max Sum of Rectangle No Larger Than K

【题目】 Given a non-empty 2D matrix   matrix   and an integer   k , find the max sum of a rectangle in the   matrix   such that its sum is no larger than   k .

Example:

Given matrix = [
  [1,  0, 1],
  [0, -2, 3]
]
k = 2

The answer is   2 . Because the sum of rectangle   [[0, 1], [-2, 3]]   is 2 and 2 is the max number no larger than k (k = 2).

Note:

1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?

【解答】要找一个矩形，让矩形框起来的范围内，所有数的和能够不超过k，但是又要尽量大。这道题我折腾了挺长时间也没有做对，我觉得还是比较难的。下面这个解法来自讨论区的 这个帖子 ，我认为是我看到的几个解法里面比较好的。就着代码做一个说明。为了简化理解的复杂度，不妨假设列数>行数。

通过i从0到m的循环，和j从i到0的循环，形成[j, i]这样一个区间，在这样的循环内部我们会看到二维问题被转化为一维问题来求解。

• 数组array用来记录这样一种累加值：array[k]表示在i已经锁定的情况下，随着j不断变小，行区间[i, j]跨度不断变大，又有从第0列到第k列[0, k]形成了列区间，对于仅仅第k列这单列，在不同行跨度下的累加值。
• val则是在i、j都锁定的情况下，即行区间完全确定的情况下，对不同k的时候，array[k]的累加。也就是说，即随着k从0变化到n，val表示从第0列到第k列，以及从第j行到i行，所形成的的这样一个矩形包含所有数的累加值。这个val是要被不断放入一个TreeSet的。
• val-target就是这个矩形值和目标值的差距，使用这个TreeSet的ceiling方法（这也是使用TreeSet的原因，查找的复杂度是log n），去找一个必须大于等于这个差距的最小值subres。这里减去target再去TreeSet里面找就是为了保证在计算差距的时候始终预留好目标值的空间。
• 用val这个矩形值减去subres，就是小于目标值，但是又尽量大的结果了。

分析一下复杂度：min(m,n)^2 * max(m,n) * log(max(m,n))，还是假设列数>行数以简化描述。

1. i和j的不断变化，形成[j, i]这样的行区间，这里有i和j的循环嵌套，因此这一步复杂度是m的平方；
2. k从0变化到n，因此这一步复杂度是n；
3. 对于TreeSet的使用，时间复杂度是log n。

因此，三者相乘，就形成了这样的复杂度。

/* 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;
}

Count Numbers with Unique Digits

【题目】 Given a   non-negative   integer n, count all numbers with unique digits, x, where 0 ≤ x < 10 ⁿ .

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding   [11,22,33,44,55,66,77,88,99] )

【解答】要找不包含重复数字的数。主要思路还是分类讨论。

这里有一个比较容易想到的递归关系，比如n=3的时候，如果我能够拿到n=2的结果，即0≤x<100，再加上101≤x<1000之间的部分，就可以得到结果。也就是说，是对于所有一位数和两位数的解，再加上新增加的三位数的部分。

但是怎么得到这个三位数部分的解，有两种方向可以考虑（起码我是这样想的）：（1）已知的所有两位数，或者是十位为0并拼接一位数的所有可能，合并起来再在百位上放一个非0的数，这样形成的三位数里面，去掉重复数字的部分；（2）单独考虑满足条件的三位数形成的所有组合，不和两位数的关联关系挂钩。如果按照思路（1）走，也许也能得出结果，但是逻辑会非常复杂；下面是按照（2）的思路来进行的步骤：

• 先递归拿到n如果是n-1的时候的解。
• 然后考虑n位数部分，最高位只有从1到9这9种可能，因为0不能选；次高位有0到9，但是去除最高位已经用过的数，因此也是9种可能；再往下，则是8种可能；再往下是7种……把这些可能累加起来即可。
• 注意的是，由于数字只有从0到9这10个，因此如果n>10了，随着n的增加，结果无法再增加了。

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;
    }
}

Design Twitter

【题目】 Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

1. postTweet(userId, tweetId) : Compose a new tweet.
2. getNewsFeed(userId) : 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.
3. follow(followerId, followeeId) : Follower follows a followee.
4. unfollow(followerId, followeeId) : Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

【解答】这一类问题还是比较有趣的，因为和实际问题（需求）更接近。仔细斟酌题目中的四个case，其中3和4看起来似乎单纯和简单一些：用map就可以解决，一个用户id映射到一串用户id，以表示follow的关系。和tweet相关的1和2中，1似乎也比较容易处理，也是一个map的映射关系。麻烦的是2，一个用户可以follow若干个不同的其它用户，要返回这堆用户中最近的10条tweet，看起来似乎没有特别好的办法。因为这10条可能集中在某一个人身上，也可能分散在不同的人当中。

不过，一点是肯定的，无论是集中还是分散，任何一个人所发的tweet中，不可能取回超过10条。因此可以从该用户关注的所有人中，每个人都取得最多10条最近的tweet，然后把结果汇总起来按时间排序，返回最近的10条即可。这个思路看起来很像MapReduce那个经典的取top xx的问题。

最后，既然要涉及单个人的“最近”10条tweet，那就需要在存储这些tweet的时候：（1）按照不同的用户来归类；（2）按照时间顺序来存放。

有了这些思路，整理一下，这道题还是比较容易解出来的。这样的问题，把具体问题抽象成可以解决的数学问题，特别是找到合适的数据结构来表示这些物件之间的关系，是解决问题的关键。同为算法问题，有些问题“算”本身的逻辑比较复杂，有些问题则是把复杂性放在模型的建立上。

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);
    }
}

Russian Doll Envelopes

【题目】 You have a number of envelopes with widths and heights given as a pair of integers   (w, h) . One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:
Given envelopes =   [[5,4],[6,4],[6,7],[2,3]] , the maximum number of envelopes you can Russian doll is   3   ([2,3] => [5,4] => [6,7]).

【解答】像俄罗斯套娃一样的套信封问题，怎样套到最多的信封。如果是一维的问题，这道题是非常简单的，从最小的信封开始，每次都尽可能去挑最小的信封套。但是现在是二维的问题（宽和高），也是题目相对来说难度增加的地方。如果把单独一维抽出来讨论，是肯定无法做到最优解的。下面是我的思路，相对简单，但是可以优化。

• 首先排序，优先考虑宽，宽一样的时候考虑高。
• 然后两重循环，第一层从序列的头到末尾，也就是说宽度是递增的；第二层从i-1到0，也就是说宽度是递减的（因为 ≥i 的部分宽度更大，显然无法放到当前的信封内）。使用numberArray存储排序完之后，第i个信封为最外层时，最多可以套到多少个信封。
• 在循环内判断宽和高，要求外层的宽大于内层的宽，外层的高大于内层的高。

也就是说，整个过程里面，宽这一维做到了减少暴力解法带来的过多计算问题，因为第二层比较时只需要从i-1遍历到0；但是高这一维度却没有。

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;
    }
}

Data Stream as Disjoint Intervals

【题目】 Given a data stream input of non-negative integers a ₁ , a ₂ , …, a _n , …, summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, …, then the summary will be:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

Follow up:
What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

【解答】首先要理解题意，随着数据流不断地流入，要把不断添加进来的数据进行分段，凡是连着的整数就算一段，每次调用getIntervals要打印出现在所有的数据段。

下面的方法是我开始思考的方法，使用TreeMap，也就是红黑树，使用它有一个好处，在于key是排序了的，这样可以用log n的复杂度找到邻近的数据段。这个map的key是数值，value是这个点的类型，分为三种：数据段开头、数据段结尾，以及数据点（即即为开头又为结尾）。然后分类讨论，用这种方法大致的方向是对的，但是下面分类讨论的case非常多，导致代码非常复杂。最后有一个巨长的测试case过不去，也不是很好调试了。为了记录思路，我把这个不好的代码例子先放在下面。

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;
    }
}

上面啰嗦的方法没再研究下去，而下面则祭出“Top Solutions”的第一个，思路就明显简洁清晰很多。也是用TreeMap，key是数值，表示的是这个数据段的开头，但是value直接放Interval对象了，这样在TreeMap中一下就可以少最多一半的数据量，因为key只需要存放开头数，不需要存放结尾数。同时，更重要的是，case也简洁很多，只需要讨论这样四种case：

1. 左段和右段当前是分开的，但是加上这个新数以后，就接上了；
2. 右段无影响，但是左段的结尾可能会被新数延长；
3. 左段无影响，但是右段的开头可能会被新数延长；
4. 左右都挨不着，新数成为孤岛数段。

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());
    }
}

Intersection of Two Arrays II

【题目】 Given two arrays, write a function to compute their intersection.

Example:
Given   nums1   =   [1, 2, 2, 1] ,   nums2   =   [2, 2] , return   [2, 2] .

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if   nums1 ‘s size is small compared to   nums2 ‘s size? Which algorithm is better?
• What if elements of   nums2   are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

【解答】和Intersection of Two Arrays就一点区别，就是不需要去重。那就用HashMap来替代HashSet就好了，key是数字，value是该数字出现的次数。

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;
    }
}

Intersection of Two Arrays

【题目】 Given two arrays, write a function to compute their intersection.

Example:
Given   nums1   =   [1, 2, 2, 1] ,   nums2   =   [2, 2] , return   [2] .

Note:

• Each element in the result must be unique.
• The result can be in any order.

【解答】求交集。用HashSet就好了，既可以找交集，又可以去重。

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;
    }
}

Top K Frequent Elements

【题目】 Given a non-empty array of integers, return the   k   most frequent elements.

Note:  

• You may assume   k   is always valid, 1 ≤   k   ≤ number of unique elements.
• Your algorithm’s time complexity   must be   better than O( n   log   n ), where   n   is the array’s size.

【解答】从一堆数中寻找k个出现次数最多的，首先出现在大脑里的思路是，先用一个map记录下每个元素的出现次数，然后再排序一下，这样复杂度就是n*logn。下面我用的是TreeMap（红黑树）的做法，TreeMap本身提供的是具有排序key的map这样的功能，它的put/get的时间复杂度都是log n，因而对于n个元素这样的情况来看，理论上的时间复杂度量级依然是n*logn。因此兴许它的时间开销会比map记录下所有元素出现次数以后，再排序一下这种方法好一些，也通过了所有的测试用例，但依然是同一级别的。也就是说，并不能算是满足题目note里面的要求使用比O(n log n)更好的复杂度，欢迎提供更佳的解法。

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;
    }
}

Reverse Vowels of a String

【题目】 Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

Note:
The vowels does not include the letter “y”.

【解答】要把元音反转。思路就是准备两个指针，一个从前往后，一个从后往前，找到元音就互换位置。

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];
    }
}

Reverse String

【题目】 Write a function that takes a string as input and returns the string reversed.

Example:
Given s = “hello”, return “olleh”.

【解答】这个题没有太多可说的。

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);
    }
}

Integer Break

【题目】 Given a positive integer   n , break it into the sum of   at least   two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given   n   = 2, return 1 (2 = 1 + 1); given   n   = 10, return 36 (10 = 3 + 3 + 4).

Note : You may assume that   n   is not less than 2 and not larger than 58.

【解答】把一个数拆分成若干个数的和，最后要求使得这几个数的乘积最大。

现在假设这个数n，需要拆成k个数，那么一点是肯定的，一旦k被确定下来，这几个数越平均越好。因为拆出来的这几个数，越是接近，乘积就越大。

因此考虑所有k的可能，拆数的时候，n/k未必能够整除，但是能够得到一个“基数”，即这种最平均的拆分法，拆出来的数要么是n/k向下取整，要么是n/k向下取整+1，也就是说任意两个数之间的差别不会超过1。

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;
    }
}

Power of Four

【题目】 Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up : Could you solve it without loops/recursion?

【解答】要看一个数是不是4的幂。做法有很多，利用一些数的性质可以简化计算：

（1）如果一个数num是2的幂，那它应该是这样的数：

1 -> 1

2  -> 10

4 -> 100

8 -> 1000

……

因此 num & (num-1) 应该得到0。

（2）考虑这样的因数分解：

4^n – 1 = (4-1) (4^(n-1) + 4^(n-2) + 4^(n-3) + … + 4 + 1)

因此取3的模应该为0。

我觉得这二个条件的必要性应该是正确的，但是惭愧的是充分性我并没有证明出来。即，上面的（1）和（2）可以说是“一个数是4的幂”的必要条件，但是如何证明它们也是充分条件呢？

其实，通过（1）的筛选可以找到符合“2的幂”这个条件，而想想2的幂如果它同时也是4的幂，那肯定能被3整除，这一点已经被（2）说明，现在问题转化为，如何说明2的幂但不为4的幂的时候，是无法被3整除的呢？

如果你知道怎样证明，或者有别的思路，我们可以讨论。

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;
    }
}

Flatten Nested List Iterator

【题目】 Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list   [[1,1],2,[1,1]] ,

By calling   next   repeatedly until   hasNext   returns false, the order of elements returned by   next   should be:   [1,1,2,1,1] .

Example 2:
Given the list   [1,[4,[6]]] ,

By calling   next   repeatedly until   hasNext   returns false, the order of elements returned by   next   should be:   [1,4,6] .

【解答】使用一个栈stack来存放外层的链表节点。每次调用next的时候，都从stack里面pop一个元素出来，然后让它的index往后走。不过如果走不了了，即已经全部遍历过了，那就只能出栈了。

有一个注意的地方是对于hasNext方法的设计。我的做法是在hasNext方法的时候把下一个元素应该返回什么的工作做好，并且使用一个标识量checked表示是否已经通过hasNext检查过了，这样在调用next方法的时候就不用做

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;
    }
}

Counting Bits

【题目】 Given a non negative integer number   num . For every numbers   i   in the range   0 ≤ i ≤ num   calculate the number of 1′s in their binary representation and return them as an array.

Example:
For   num = 5   you should return   [0,1,1,2,1,2] .

Follow up:

• It is very easy to come up with a solution with run time   O(n*sizeof(integer)) . But can you do it in linear time   O(n)   /possibly in a single pass?
• Space complexity should be   O(n) .
• Can you do it like a boss? Do it without using any builtin function like   __builtin_popcount   in c++ or in any other language

【解答】要数1的个数，再看题目里对复杂度的要求，对1到n的每一个数拿出来，必须要在常数时间复杂度内就得出结果。因此考虑1到n中每一个数和它之前的数之间的关系，利用之前的数已经算得的结果（存在数组array中），再加上变化的增量，以减少计算量。

array[0] = 0，1的数量：0

array[1] = 1 -> 2^0 -> 1，1的数量：1

array[2] = 2 -> 2^1 -> 10，1的数量：array[0] + 1

array[3] = 3 -> 2^1 + 1 -> 11，1的数量：array[1] + 1

array[4] = 4 -> 2^2 -> 100，1的数量：array[0] + 1

array[5] = 5 -> 2^2 + 1 -> 101，1的数量：array[1] + 1

array[6] = 6 -> 2^2 + 2 -> 110，1的数量：array[2] + 1

array[7] = 7 -> 2^2 + 3 -> 111，1的数量：array[3] + 1

array[8] = 8 -> 2^3 -> 1000，1的数量：array[0] + 1

在纸上写出如上，寻找思路：

1. 任意一个数出现的时候，比如1101010101，只有最高位的1是个新东西，去掉最高位之后，101010101在之前已经出现过了，因此使用一个数组array来存储已经计算过的结果；
2. 使用pos下标来表示当前这个数去掉最高位以后，剩下的数在array出现的位置，那么加上1就可以得到当前这个数的1的数量；
3. 用cycleLength来记录一个表示2的cycleCount次方的结果，在cycleCount没有变化的时候，1的数量是去掉最高位以后的值+1，但是如果cycleCount变化（即cycleLength≤pos），需要把pos清零，把cycleCount自增1，并更新cycleLength。

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;
    }
}

House Robber III

【题目】 The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

     3
    / /
   2   3
    /   / 
     3   1

Maximum amount of money the thief can rob =   3   +   3   +   1   =   7 .

Example 2:

     3
    / /
   4   5
  / /   / 
 1   3   1

Maximum amount of money the thief can rob =   4   +   5   =   9 .

【解答】这道题思路相对还是比较简单的。建立两个map，一个用来存放指定节点被抢劫的最优解，一个用来存放指定节点不被抢劫的最优解。

然后就可以从root开始递归遍历，注意递归方法需要传入一个boolean变量表示在某种情况下，这次的递归调用所对应的节点是否可以被抢劫：

• 如果可以被抢劫就需要在两个map中分别存放被抢劫和不被抢劫的最优解；
• 如果不可以被抢劫，就只需要在后一个map中存放不被抢劫的最优解。

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);
    }
}

Palindrome Pairs

【题目】 Given a list of   unique   words, find all pairs of   distinct   indices   (i, j)   in the given list, so that the concatenation of the two words, i.e.   words[i] + words[j]   is a palindrome.

Example 1:
Given   words   =   ["bat", "tab", "cat"]
Return   [[0, 1], [1, 0]]
The palindromes are   ["battab", "tabbat"]

Example 2:
Given   words   =   ["abcd", "dcba", "lls", "s", "sssll"]
Return   [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are   ["dcbaabcd", "abcddcba", "slls", "llssssll"]

【解答】从一堆单词里面找出两个，连接在一起组成回文，要列出所有这样的可能性。

最暴力的解法就是两两组合，考虑所有的可能性，但是复杂度在n平方。

因此思考改进的方式。两个单词连接，如果较短的那一个已经确定，再去取较长的那一个的时候，满足如下条件：

• 较短字符串必须以逆序出现在较长串的一端；
• 同时，长串减去短串后剩下的部分，必须自成回文。

对于长串和短串的关系，具体说，有两种情况：

1. 短串出现在长串的左端，比如“abc”和“ba”，ba的逆序就出现在abc的左端，而长串减去短串为c，自成回文串，这种情况下可行的连接是把较短串放到右边，组成abcba；
2. 短串出现在长串的右端，比如“cdcab”和“ba”，ba的逆序就出现在cdcab的右端，而长串减去短串为cbc，自成回文串，这种情况下可行的连接是把较短串放到左边，组成bacdcab。

明确这个关系以后，改进的方式就在心中浮现了：如果拿到任意一个串，视之为短串，能够不需要遍历剩余所有的串，而比较快速地得到以他的反串为前缀或者后缀的对应长串，再来判断长串减去短串后余下部分是否是回文即可。

对下面的代码做一个简要说明，首先构造如下的数据结构：

• 根据字符串中字符的前后关系，分别建立两棵树，一棵是正序遍历，一棵是逆序遍历，而下面的Node即为树的节点。
• stringToIndex这个map是从字符串到位置下标的映射，toReversed是字符串正序向逆序的映射，toOriginal则反之，这两个是用空间换时间，用来减少反复操作逆序的运算量的。
• stringToNodeForward和stringToNodeBackward分别是字符串像正序遍历树和逆序遍历树中终点节点映射的map。

构造以上结构完成之后，以这样的输入来举例：[ae, ab, bac, ca]。

• 左图是顺序树，右图是逆序树。
• 如果要找短串出现在长串右端的情况，需要把源串逆序，然后到顺序树中去找，比如ab，逆序为ba，到左图去找，找到中间的ba，继续往下还有c，而c自成回文，因此bac+ab满足题意；
• 如果要找短串出现在长串左端的情况，需要保持源串顺序，但是去逆序树中找，比如ca，到右图去找，第三列找到ca，继续往下还有b，而b自成回文，因此ca+bac满足题意。

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);
    }
}

Self Crossing

【题目】 You are given an array   x   of   n   positive numbers. You start at point   (0,0)   and moves   x[0]   metres to the north, then   x[1]   metres to the west,   x[2]   metres to the south,   x[3]   metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with   O(1)   extra space to determine, if your path crosses itself, or not.

Example 1:

Given x = [2, 1, 1, 2],
┌───┐
│   │
└───┼──>
    │

Return true (self crossing)

Example 2:

Given x = [1, 2, 3, 4],
┌──────┐
│      │
│
│
└────────────>

Return false (not self crossing)

Example 3:

Given x = [1, 1, 1, 1],
┌───┐
│   │
└───┼>

Return true (self crossing)

【解答】题目本身很清晰，这道题hard难度，我确实折腾了好一会儿。我发现LeetCode的题目是越来越难做了，是我思维退步了还是出题人心理越来越阴暗了？……

用的还是分类case来归纳讨论的思路。虽然结果通过了，但是我并非很有信心，因为这里的case实在是折腾得我有点思路混乱。无论如何，我把我的解法放在了下面。

首先，大类上可以归纳为这样三种，我觉得这点是不会有错的：

1. 膨胀型
2. 收缩型
3. 先膨胀再收缩型

一旦收缩以后就无法再膨胀了，因此没有“先收缩再膨胀”这种类型。下面代码的shrink变量表示是收缩还是膨胀，而inflateToShrink变量用来表示从膨胀到收缩那个临界变化的位置，在那个位置有很多特殊的case。

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;
    }
}

在 讨论区 有非常清晰简洁的解法，我就不贴在这里了，也是分类讨论的办法，但是清晰很多，而且不需要状态变量。兴许这一类题目有某种思路简单的套路可以采用呢？

Increasing Triplet Subsequence

【题目】 Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k

such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n -1 else return false.

Your algorithm should run in O( n ) time complexity and O( 1 ) space complexity.

Examples:

Given [1, 2, 3, 4, 5] ,

return true .

Given [5, 4, 3, 2, 1] ,

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;
    }
}

Reconstruct Itinerary

【题目】 Given a list of airline tickets represented by pairs of departure and arrival airports   [from, to] , reconstruct the itinerary in order. All of the tickets belong to a man who departs from   JFK . Thus, the itinerary must begin with   JFK .

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary   ["JFK", "LGA"]   has a smaller lexical order than   ["JFK", "LGB"] .
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

【解答】寻找一个以JFK为首的连续路径，要求把机票都用完，每张机票只用一次。

一开始思路是，使用一个名为visited的map来存储机票是不是用过了，然后使用一个value为list的map来存储出发点和终点之间的对应关系。接着从JFK出发，遍历所有可能性。写代码的时候就觉得有些忐忑，因为看起来整个方法平平淡淡，并不优雅，结果不出意外地超时了。

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;
    }
}

如何简化？其实和下面的那道二叉树先序遍历的题类似，图和路径的问题与树一样，也可以考虑使用入度和出度之间的关系来简化。

下面的简明无比的思路来自 这里 ，核心是根据入度和出度的关系，入口的入度-1=出度，而出口的入度+1=出度。

还是使用map来存储出发点和终点的对应关系，但是使用优先级队列来存储终点列表，以免去手动sort之苦。

在下面的递归调用visit的方法中，传入当前所在的地点，只要map中还包含，就从它对应的终点中poll一个出来继续visit，以此while不断进行，直到无法进行下去为止。为什么有了递归还需要这个while？因为一个地点有可能遍历到好几次，即有多张机票的起点相同。

但是形成最终路径的时候，要在while循环之后，在已有路径的头部插入当前地点，因为当前地点是已生成路径的出发点。

// 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);
    }
}

Verify Preorder Serialization of a Binary Tree

【题目】 One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as   # .

     _9_
    /   /
   3     2
  / /   / /
 4   1  #  6
/ / / /   / /
# # # #   # #

For example, the above binary tree can be serialized to the string   "9,3,4,#,#,1,#,#,2,#,6,#,#" , where   #   represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character   '#'   representing   null   pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as   "1,,3" .

【解答】开始的思路是，既然是先序遍历，那给定串的第一个数肯定是root，剩下的部分拆分成左子树和右子树，考虑所有拆分可能，并且用一个布尔型二维数组来表示一段区间是否是合法的二叉树以避免重复计算：

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;
    }
}

这个思路确实容易想到，可是很快超时了。在 讨论区 我看到了一种巧妙的办法，而且具有一定的典型性，对于树的问题可以通过利用入度和出度之间的关系来简化计算：

对于每一个节点，我们认定从父节点来的路径为入，通往子节点的路径为出，

• 那么显而易见root的入度为0，而出度为2；
• 其它非叶子节点的入度为1，出度为2；
• 叶子节点的入度为1，出度为0。

有了这样的关系，我们就可以沿着先序遍历的顺序从root开始挨个遍历，使用diff来跟踪当前(入度-出度)的值，并且给定一个初始补偿值1，这就意味着，如果这个先序遍历是合法的，那么整个便利过程中，应该不会出现diff小于0的情况，并且，在遍历完成后，diff应该等于0。

这个解法的复杂度只有O(n)，而且不用考虑使用额外占用空间复杂度的布尔数组来存储中间值。

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;
    }
}

Patching Array

【题目】 Given a sorted positive integer array   nums   and an integer   n , add/patch elements to the array such that any number in range   [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums   =   [1, 3] ,   n   =   6
Return   1 .

Example 3:
nums   =   [1, 2, 2] ,   n   =   5
Return   0 .

【解答】要给一个升序正整数数组打补丁，即添加上若干个数以后，使得使用这些数能够相加组合出从1到n所有的值来。

如果按照正向的思路去想，当前这个正整数组能够产生在1到n之间的哪些数，还差哪些数，添加怎样的数去覆盖这些差的数，就会走入死路，非常难解。但是如果从另外一个角度去看这个问题，问题就好办很多。把1到n这些数从小到大挨个拿出来看，第一个数能不能生成，第二个数能不能生成……一直到第n个：

• x表示当前需要被生成的数；
• max表示现在这些数里面能够连续覆盖到的最大的数，即覆盖1到max；
• index表示现有升序正整数数组的下标。

好，考虑这样的递推关系：当前[1, max]是可以被覆盖的，那么下面我要从nums中去取下一个数，

• 如果这个数取出来和max+1一样大，那就说明这个能覆盖数的范围正好接上了，即从原来的[1,max]变成了[1,max+1]；
• 但是如果这个数大于max+1，说明接不上了，即max+1没有办法生成，这就需要打patch，而这个patch就是max+1。

上面这一步的思考非常重要，想到的话基本上解题就顺理成章了。

那么如果打了max+1这个patch，新的覆盖范围会变成多少呢？原来的范围是[1,max]，现在有了max+1，这就意味着原来的范围中的每一个数都加上max+1也可以生成了，即可以覆盖[1+(max+1), max+(max+1)]，再加上原来就已经覆盖的[1,max]，于是最新的覆盖范围是[1, max+(max+1)]。

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;
    }
}

Longest Increasing Path in a Matrix

【题目】 Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return   4
The longest increasing path is   [1, 2, 6, 9] .

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return   4
The longest increasing path is   [3, 4, 5, 6] . Moving diagonally is not allowed.

【解答】这道题比较简单。要找出最长的递增路径。基本思路是尝试以每一个点为起点去遍历寻找，但是如果已经找过的部分，就不要重复找了。因此用一个map来存储这个已经找过的结果，lenMap[i][j]表示以matrix[i][j]为起点的最长路径的长度。

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];
    }
}

Odd Even Linked List

【题目】 Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

【解答】题目本身没有什么特别的，只不过要求O(1)的空间复杂度，这就意味着基本上只能用简单的指针来解决，不能用辅助栈或者辅助数组。题目比较简单，注意对奇数链表和偶数链表头和尾的把握。

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;
    }
}

Count of Range Sum

【题目】 Given an integer array nums , return the number of range sums that lie in [lower, upper] inclusive.

Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j ( i ≤ j ), inclusive.

Example:

Given nums = [-2, 5, -1] , lower = -2 , upper = 2 ,

Return 3 .

The three ranges are : [0, 0] , [2, 2] , [0, 2] and their respective sums are: -2, -1, 2 .

【解答】要找数组满足条件的区间数，要求区间内数之和在i和j之间。确实很容易想到n平方的解法，很清晰也很简单，但是如果要进一步优化时间复杂度，数组并非有序，就不是那么好办了。于是思路开始自然地往动态规划上面靠，可是怎样减少计算量呢？任意一个区间的和，可以由它邻近区间的一个已知结果加减差异元素来得出，可是这样的算法依然要求遍历每一个区间的可能，并未减小复杂度的量级。

这个问题的常规解法有两种，第一种是树状数组（Fenwick tree，或者Binary Indexed Tree – BIT），对于它这个问题是很有代表性的。它用来解决的问题是数组元素更新和连续的N个数求和之间性能开销的平衡问题，换言之，如果我总是需要对某个数组的元素进行更新，而更新以后我有需要得到它任意区间和的最新值，那么用树状数组往往可以获得比较好的性能。定义上不是那么直观，如果原数组是array，树状数组BIT元素的通式为：BIT[i] = array[i–2^k+ 1] + … + array[i]，其中2^k=i&(i^(i-1))，即i&(-i)。但是转换成图示可能会容易理解一点，下面这张图来自 维基百科 ，非常形象地说明了树状数组的构件过程：有这样一个数组[1,2,3,4,5]，从左往右每次取一个元素，每一个BIT的元素都代表了其中一段的和。这样在扫描数组的时候，可以一段一段扫描，而不是像普通数组那样一个一个数地扫描；在更新的时候，也只需要遍历从BIT树的叶子节点一路往上走，直到根为止，没有遍历到的节点不需要更新。这个复杂度就可以降到nlogn。

下面这张图（来自 这里 ）更容易看出每一个BIT元素所代表的哪一段的区间和：

遗憾的是，BIT树在JDK里面没有实现，因此即便好不容易想到了用它来解，还需要自己去实现（ 参考实现 ）BIT，这就让这道题变成hard难度。

另一种解法来自这个讨论中的 高票回答 ，不需要BIT的知识，却巧妙借用归并排序的思想，二分归并这个行为本身的复杂度log n，乘以每一个子数组遍历的复杂度n，因此复杂度就是nlogn。如果我们能对原数组进行排序，这样就可以利用二分查找的方法把复杂度降下来，但是因为我们需要找的是区间的和，区间意味着连续的数串，因此对原数组排序是不可行的。但是，如果我们定义一个和数组sums，sums[i]表示的是原数组签名i个元素的和，那么我们就可以对sums[i]来进行归并排序，这一思路是解题的关键：

• 取中点，然后对中点之前的前半段进行归并排序，并返回符合要求的元素个数，再对后半段做同样的事；
• 对于每个给定的i，对数组中区间和小于下限的个数记为k，小于上限的个数记为j，那么符合要求的元素个数就是所有(j-k)的累加。

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;
    }
}

【题目】 Given an integer, write a function to determine if it is a power of three.

Follow up:

Could you do it without using any loop / recursion?

【解答】其实3的乘方数很少，因为乘方的大小上涨得很快，所以完全可以在初始化的时候就找出所有3的乘方数来。当心溢出就好。

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);
    }
}

Wiggle Sort II

【题目】 Given an unsorted array nums , reorder it such that nums[0] < nums[1] > nums[2] < nums[3]... .

Example:

(1) Given nums = [1, 5, 1, 1, 6, 4] , one possible answer is [1, 4, 1, 5, 1, 6] .

(2) Given nums = [1, 3, 2, 2, 3, 1] , one possible answer is [2, 3, 1, 3, 1, 2] .

Note:

You may assume all input has valid answer.

Follow Up:

Can you do it in O(n) time and/or in-place with O(1) extra space?

【解答】要最终排成一大一小依次排列的结果。我的做法是：

• 先排序；
• 然后把大的一半先拿出来，放到最终结果的奇数位置上去；
• 再把剩下小的一半拿出来，放到最终结果的偶数位置上去。

要着重说明的一点就是，上面这个过程，遍历都是逆序的。也就是说，排好序之后从左到右是从小到大，但是取数的时候是从右到左，即从大到小来取的。

为什么要这样做？

因为排序以后的数组是从小到大的，因此第一遍拿大的一半，那么最大的数会在结果数组靠左的位置，而原数组中居中的数会在结果数组靠右的位置；第二遍拿小的一半，于是原数组中居中的数会在结果数组靠左的位置，而最小的数会在结果数组中靠右的位置——于是居中的数被拆开了，分别在结果数组的最左边和最右边。这样就避免了重复的数落在了结果数组中相邻的位置。

比如说4，5，5，6：如果按照上面的方法逆序遍历会得到5，6，4，5，但是如果顺序遍历，会得到4，5，5，6，于是问题就出在相邻的两个5上。

// 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--;
        }
    }
}

Coin Change

【题目】 You are given coins of different denominations and a total amount of money amount . Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1 .

Note :

You may assume that you have an infinite number of each kind of coin.

【解答】要求最少钱币的数目。

如果有1、2、5三枚面值不同的硬币，那么对于任意目标值x，我如果能知道(x-1)、(x-2)和(x-5)这三个值所用到的最少钱币数目就好了。

想到这里，就可以用动态规划来解答了。

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;
    }
}

Create Maximum Number

【题目】 Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

【解答】给两串数m和n，分别取几个，加起来的个数不超过k，并且从m和n中取的子串保持在原串中顺序相对位置，然后任意位置merge起来。要求最后得到的那一串数所代表的那个数尽可能大。

看起来，这道题给人的第一印象是，从m中选一串数，从n中也选一串数，这两个是变化点。但是如果这两串数定下来，那么下面的行为类似于归并排序，每一个子串都有一个指针记录当前位置，从这两个子串中取数每次都取尽量大的数。

顺着这样的思路，我一开始建立了一个比较复杂的模型，一个三维的动态规划。但是我们一般只会接触到最多二维的动态规划，所以当时的感觉就觉得可能走到歪路上去了。果然，还是过于复杂，执行超时了。简单介绍当时的思路。

建立dp[x][y][k]表示第一个子串从m的[x, m.length)中取，第二个子串从n的[y, n.length)中取，那么分析如下四种case：

• case 1，m[x]是结果中的一部分，因此当我拿掉m[x]的时候，两个子串和k分别变成了m[x+1, m.length)，n[y, n.length)，k-1
• case 2，n[y]是结果中的一部分，因此当我拿掉n[y]的时候，两个子串和k分别变成了m[x, m.length)，n[y+1, n.length)，k-1
• case 3，m[x]不是结果中的一部分，因此当我拿掉m[x]，对结果没有影响，两个子串和k分别为m[x+1, m.length)，n[y, n.length)，k
• case 4，n[y]不是结果中的一部分，因此当我拿掉n[y]，对结果没有影响，两个子串和k分别为m[x, m.length)，n[y+1, n.length)，k

也就是说，当前的子串状态，可能源于上面四个case，发生变化得到，具体哪一个呢，需要再去比较以上这4个case情况下的大小，取最大的结果……很多数组拷贝，看着就很冗长。

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;
    }
}

在这个网站上有一个 好的解法 ，我拿过来了。基本思路是：

• 不管怎么取，要从nums1中取 i 个数组成的子数组A，要从nums2中取 k-i 个数组成的子数组B；
• 那么当给定某一个 i 的时候，A要尽量大，而这个尽量大和B无关；同样，B要尽量大，也和A无关，因此，在给定某一个 i 的时候，可以得到唯一的最佳解A和最佳解B——这个强化条件然后分治的思路是简化这个问题的核心；
• 接着计算A和B，即要从一个给定数组中，挑出给定数目的数所组成的子数组，使之所表示的数最大，就比较简单了；
• 最后再遍历所有 i 的取值，得出最终结果。

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;
    }
}

Bulb Switcher

【题目】 There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i th round, you toggle every i bulb. For the n th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

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.

【解答】如果你和我开始一样，尝试用循环去模拟所有的灯泡开关行为，能得到答案，但是大的case肯定会超时。

在讨论区找打了一个精妙的 解答 。任意一个数，如果可以分解成两个数a和b的乘积，那么当a和b不等的时候，就意味着成对出现了灯状态改变的行为。例如36=4x9，36=9x4，即偶数次的改变相当于不变。但是，如果a=b，在这种唯一的情况下，这种状态改变是成单的，并最终导致了灯泡状态的改变。也就是说，这种情况一定意味着该数可以被开平方。

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

Maximum Product of Word Lengths

【题目】 Given a string array words , find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn" .

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd" .

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

【解答】要找出互无重复字母的两个单词长度之积的最大值，很容易想到的是，不存在大小和递推关系，只有等和不等，因此如果没有特殊的方法，要两两比较，O(n²)这样的复杂度是少不了的。

那如果是这样的话，下面要解决的问题就是：从中给出两个单词，要比较这两个单词之间是否有字母重复，怎样让时间和空间复杂度尽量小。

开始尝试用HashSet来解决，即把一个单词中出现的字母全部找出来放到HashSet里面，如果另一个单词中的字母能从这个HashSet中找到，就说明有重复，反之则没有。我照着思路做了以后，超时了。

于是使用BitMap来改进：一个整数有32位，因此有32个位置可以表示0或者1，但是字母只有26个，因此如果某字母出现过，那么在相应位上面就为1而不为0，这样一个整数就可以表示任意一个单词中出现的字母种类。把单词转换成整数的方法可以作为“预处理”的步骤之一，而实际在实际的比较中，只需要先看两个单词所代表的整数相“与”，如果全0则表示无重复字母。用这种方法可比比较整个HashSet效率高多了。

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');
    }
}

Remove Duplicate Letters

【题目】 Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

【解答】要求去重复字母，并且去重完毕之后，要求得到的字符串字典字母序最小。

下面这个是我一开始的解答，思路是：

• 用一个map来存放字母出现的位置：key为字母，value为出现位置下标的数组（因为可能出现多次，所以用数组）。
• 这个map构造完成之后，从a开始遍历检查到z，期间用lastPos保存上一个字母选取的位置：如果当前字母的位置都在lastPos的左边，那就选一个最小的；如果有存在在lastPos右边的，就二分查找取一个最接近且大于lastPos的。

举例来说：对于字符串“acbab”，构造这样的map：

• a -> [0, 3]
• b -> [2, 4]
• c -> [1]

然后开始从a-z遍历：

• 对a，有两个，但是lastPos为初始值-1，因此直接取最小的，就是下标为0的a，赋值lastPos=0；
• 对b，出现位置有lastPos右边的，二分查找取最接近且比0大的，于是取了下标2的b，赋值lastPos=2；
• 对c，发现全都在lastPos左边的，取最小的（也只有一个），于是去了下标为1的，赋值lastPos=1。

于是结果为“acb”，看起来逻辑是对的。

但是写完代码跑用例的时候傻眼了，有一个case用这个方法是过不去的，比如“cbacdcbc”，用上面的办法得到的是“adbc”，但实际应该是“acdb”。

原因在于，选a的时候没问题，选b的时候也没问题，但是选c的时候，上面的方法本质上是一种贪心的策略，因此挑了一个出现在b右侧的c，而在这里用贪心是行不通的，因为d的关系。

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);
    }
}

在题目的讨论中有一种正确而且简洁的 解法 。思路是：

• 用一个数组cnt记录每个字母出现的次数；
• 用pos表示是当前s中最小字母出现的位置，遍历s中的每一个字母，如果当前位置i的字母的字典序比pos所代表的字母更小，就更新pos；
• cnt中表示该位置i的字母的次数减一，如果为0了就跳出遍历；
• 以pos上所指的字母为本次方法调用所选择的字母，余下字母继续递归调用执行以上逻辑。

这种方法也是贪心，但是每次贪心选出来的字母却不一定是从a到z这样的顺序的，原因在于：不是根据字典序，而是从左至右遍历s，每次因为某一个字母的所有位置都被找出来了，就跳出循环，但是选中的字却确不是当时遍历到的字母，而是当时状态下遍历过的的最小字母。该字母左边的全部子串都删掉，右边则把重复出现的该字母删掉。

还用上面的“cbacdcbc”举例：

• 第一次遍历完a以后跳出，选出a来，然后把a左边的子串“cd”删掉，余下子串“cdcbc”；
• 第二次便利完d以后跳出，选出c中的第一个来，这个c左边没有子串，右边子串中的c删掉，因此余下子串“db”；
• 第三次便利完d以后跳出，选出d来，余下子串“d”；
• 第四次选出c来，于是结果就是“acdb”。

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), ""));
    }
}

Count of Smaller Numbers After Self

【题目】 You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i] .

Example:

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.

Return the array [2, 1, 1, 0] .

【解答】每次取nums数组的最右边的x个数，形成数列arr，把其中比arr[0]小的数的个数统计出来为y，随着x从n变到1，得出这个统计值y变化的结果并形成数组返回。

这个x如果是从1变到n，可能会更好计算。因为我每时每刻只要维护一个有序数组用来表示当前arr中所有的数们，只不过他们是被排序了的，x每次递增则意味着要从nums里面取一个新数放到这个有序数组里面去。根据放进去的位置，就能够知道当时有多少个数比它小。

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;
    }
}

Super Ugly Number

【题目】 Write a program to find the n th super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k . For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:

(1) 1 is a super ugly number for any given primes .

(2) The given numbers in primes are in ascending order.

(3) 0 < k ≤ 100, 0 < n ≤ 10 6 , 0 < primes[i] < 1000.

【解答】首先读懂题意。Super Ugly数是指一串正数，他们的质因数由给定的prime list组成，现在给定一个prime list，要求第k个Super Ugly数。

建立这个Super Ugly数序列的数组arr，并且首元素置为1。

再创建一个indexArr数组，其中的下标i表示在primes中的第i个质数，而存放的值表示arr中的下标。为什么要建立它，主要是因为对于任何一个在primes中的质数，如果要乘以arr中的某一个数的时候，需要用一个数记录当前在哪个数上面，而它前面的已经乘过了，因此现在要乘以primes[x]的话，需要从arr[indexArr[x]]开始。也就是说，这是一个存放的是下标的数组。这个思路其实有点绕，也是这个题目的关键，如果这一步想出来了这个题就没有难度了。

最后，注意去重的处理。

总的来说，我觉得这道题要做对挺难的啊，不止Medium难度。

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];
    }
}

Burst Balloons

【题目】 Given n balloons, indexed from 0 to n-1 . Each balloon is painted with a number on it represented by array nums . You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i . After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

(1) You may imagine nums[-1] = nums[n] = 1 . They are not real therefore you can not burst them.

(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

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

【解答】这道题其实难度我觉得Medium比较合适。

直观上，要使结果尽可能大，那么大的数要晚些引爆，这样不断参与乘法运算，就能使结果尽可能大。

对于首尾气球的处理，题目已经给了提示，nums[-1] = nums[n] = 1，因此创建一个长度为nums.length+2的数组。动态规划的记忆数组cache[from][to]表示从from个气球到to个气球，全部爆炸以后得到的值是多少。

接着，每次爆炸的时候，考虑根据切分点i把当前气球序列分成leftPart和rightPart两部分，其中leftPart为[from, i)，rightPart为(i, to]，因此递归求出leftPart和rightPart的值，并和nums[i]相乘，取不同i取值下的最大值。

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;
    }
}