Massive Algorithms: LeetCode 354 - Russian doll envelopes

LeetCode 354 - 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]).

The first glance at this problem seems that it is not that easy. After diving into it, I found that this problem is the "Longest Common SubArray" problem.
Let me give some analysis:
There are two conditions to ensure that a smaller envelope can be wrapped into another: smaller width and smaller height. So let's first satisfy one condition:

Sort the envelopes with their width to get Array1: a1, a2, a3, a4, a5, a6, a7, a8 with O(n*logn)
Sort the envelopes with their height to get Array2: b1, b2, b3, b4, b5, b6, b7, b8 with O(n*logn)

Any list that satisfy the "Russian doll" must be the subarray of both Array1 and Array2. So our task here is to find the Longest Common SubArray of Array1 and Array2which can be accomplished with DP in O(n*n)

So the total time complexity is O(n*n).

http://www.cnblogs.com/grandyang/p/5568818.html

我们还可以使用二分查找法来优化速度，我们首先要做的还是给信封排序，但是这次排序和上面有些不同，信封的宽度还是从小到大排，但是宽度相等时，我们让高度大的在前面。那么现在问题就简化了成了找高度数字中的LIS，完全就和之前那道Longest Increasing Subsequence一样了，所以我们还是使用之前那题解法来做

一个最长升序子串的变形，先对数组以width进行升序排序，如果width相等就以height降序排序．因为这样可以保证依次遍历数组的时候后面的width始终比前面的大并且如果高度也大于前面的就一定可以包含前面的．如果不对height降序排列形如[6,4], [6,7]前面是不能包含后面一个的

https://blog.csdn.net/u014688145/article/details/69663661

此处，我们需要知道官方lib库中提供的binarySearch返回的index，如果能够找到对应的key，那么直接返回对应的下标，而当找不到当前元素时，它返回的是最大的index，使得nums[index] < key，返回-(index)-1，所以对应的＋1 取反即为我们要插入的地方。

还需要注意一个地方，即comparator的比较顺序，先比较宽度，把宽度小的放在前面，如果宽度相等，则把长度长的放在前面，这是关键！！！理由很简单，当宽度相同时，我们有理由取最大的长度，如果取最小，那么对后续的序列，会出现宽度相同，而长度大的也被放入到了dp中，这种情况并不符合。不过说实话，想到这并不容易。

https://www.jianshu.com/p/8b7aeb6b7675

https://leetcode.com/discuss/106946/java-nlogn-solution-with-explanation

Sort the array. Ascend on width and descend on height if width are same.
Find the longest increasing subsequence based on height.

Since the width is increasing, we only need to consider height.
[3, 4] cannot contains [3, 3], so we need to put [3, 4] before [3, 3] when sorting otherwise it will be counted as an increasing number if the order is [3, 3], [3, 4]

"descend on height if width are same"

public int maxEnvelopes(int[][] envelopes) { if(envelopes == null || envelopes.length == 0 || envelopes[0] == null || envelopes[0].length != 2) return 0; Arrays.sort(envelopes, new Comparator<int[]>(){ public int compare(int[] arr1, int[] arr2){ if(arr1[0] == arr2[0]) return arr2[1] - arr1[1]; else return arr1[0] - arr2[0]; } }); int dp[] = new int[envelopes.length]; int len = 0; for(int[] envelope : envelopes){ int index = Arrays.binarySearch(dp, 0, len, envelope[1]); if(index < 0) index = -(index + 1); dp[index] = envelope[1]; if(index == len) len++; } return len; }

java.util.Arrays.binarySearch

index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

http://www.cnblogs.com/tonix/p/5565733.html

http://bookshadow.com/weblog/2016/06/07/leetcode-russian-doll-envelopes/

参考Longest Increasing Subsequence（最长递增子序列）的解法。

以输入envelopes其中的一个维度进行排序，对另外一个维度求解LIS即可。

1. 对输入的envelopes进行排序：首先比较宽度，宽度小的在前；宽度相同时，高度大的在前（这样处理可以避免相同宽度的信封被重复统计）

2. 利用二分查找维护一个递增队列，以高度作为比较条件。

由于LeetCode OJ的最大测试用例规模超过4000，O(n ^ 2)的解法会超时

def maxEnvelopes(self, envelopes): """ :type envelopes: List[List[int]] :rtype: int """ nums = sorted(envelopes, cmp = lambda x,y: x[0] - y[0] if x[0] != y[0] else y[1] - x[1]) size = len(nums) dp = [] for x in range(size): low, high = 0, len(dp) - 1 while low <= high: mid = (low + high) / 2 if dp[mid][1] < nums[x][1]: low = mid + 1 else: high = mid - 1 if low < len(dp): dp[low] = nums[x] else: dp.append(nums[x]) return len(dp)

https://www.hrwhisper.me/leetcode-russian-doll-envelopes/

题意：给定一些信封的宽和长，当且仅当信封x的宽和长均小于另一个信封y时，x可以装入y，求最多可以嵌套的装几个？

思路: 看到就知道是求LIS了(最大上升子序列)，不明白为啥会是hard难度。

求LIS可以直接简单的dp，设dp[i]为以i为结尾的LIS长度，则dp[i] = max(0,dp[j] | j<i && A[j] < A[i]) + 1

复杂度为O(n^2)，但可以优化到O(nlogn)，排序然后二分。

本题需要注意排序的时候要注意第一项相同的情况下，第二项的顺序。

    def maxEnvelopes(self, envelopes):

"""

        :type envelopes: List[List[int]]

        :rtype: int

"""

        def lower_bound(arrays, L, R, x):

            while L < R:

                mid = (L + R) >> 1

                if x <= arrays[mid]:

                    R = mid

                else:

                    L = mid + 1

            return L

        if not envelopes: return 0

        A = sorted(envelopes, lambda x, y: x[0] - y[0] if x[0] != y[0] else y[1] - x[1])

        n = len(A)

        dp = [1] * n

        g = [0x7fffffff] * (n + 1)

        for i in xrange(n):

            k = lower_bound(g, 1, n, A[i][1])

            dp[i] = k

            g[k] = A[i][1]

        return max(dp)

X. https://leetcode.com/discuss/106888/java-answer-n-lg-n-time-using-binary-search

Sort the array of envelopes by their width and heigh
construct an array f which stores the height of envelopes. and its cell means the minimum height is f[l] while the number of envelopes is l (like Longest Increasing Subsequence)
for those envelopes whose have the same width, find the exact indexes using binary search (we must firstly put them into a temp array t)
update f and ret

X. O(N^2)

这道题给了我们一堆大小不一的信封，让我们像套俄罗斯娃娃那样把这些信封都给套起来，这道题实际上是之前那道Longest Increasing Subsequence的具体应用，而且难度增加了，从一维变成了两维，但是万变不离其宗，解法还是一样的，首先来看DP的解法，这是一种brute force的解法，首先要给所有的信封按从小到大排序，首先根据宽度从小到大排，如果宽度相同，那么高度小的再前面，这是STL里面sort的默认排法，所以我们不用写其他的comparator，直接排就可以了，然后我们开始遍历，对于每一个信封，我们都遍历其前面所有的信封，如果当前信封的长和宽都比前面那个信封的大，那么我们更新dp数组，通过dp[i] = max(dp[i], dp[j] + 1)。然后我们每遍历完一个信封，都更新一下结果res

该题目属于接龙型的DP，接龙型的DP的一个巨大的特点就是按照一定的顺序排序后，后面的的可以在前面的数据的+1的基础之上完成

https://leetcode.com/discuss/107218/short-and-simple-java-solution-15-lines

https://leetcode.com/discuss/106837/clean-java-solution

https://discuss.leetcode.com/topic/47404/simple-dp-solution

public int maxEnvelopes(int[][] envelopes) { if ( envelopes == null || envelopes.length == 0 || envelopes[0] == null || envelopes[0].length == 0){ return 0; } Arrays.sort(envelopes, new Comparator<int[]>(){ @Override public int compare(int[] e1, int[] e2){ return Integer.compare(e1[0], e2[0]); } }); int n = envelopes.length; int[] dp = new int[n]; int ret = 0; for (int i = 0; i < n; i++){ dp[i] = 1; for (int j = 0; j < i; j++){ if ( envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]){ dp[i] = Math.max(dp[i], 1 + dp[j]); } } ret = Math.max(ret, dp[i]); } return ret; }

http://blog.csdn.net/u014688145/article/details/69663661

此处，我们需要知道官方lib库中提供的binarySearch返回的index，如果能够找到对应的key，那么直接返回对应的下标，而当找不到当前元素时，它返回的是最大的index，使得nums[index] < key，返回-(index)-1，所以对应的＋1 取反即为我们要插入的地方。

还需要注意一个地方，即comparator的比较顺序，先比较宽度，把宽度小的放在前面，如果宽度相等，则把长度长的放在前面，这是关键！！！理由很简单，当宽度相同时，我们有理由取最大的长度，如果取最小，那么对后续的序列，会出现宽度相同，而长度大的也被放入到了dp中，这种情况并不符合。不过说实话，想到这并不容易。

public int maxEnvelopes(int[][] envelopes) { if (envelopes == null || envelopes.length == 0 || envelopes[0] == null || envelopes[0].length != 2) return 0; Arrays.sort(envelopes, new Comparator<int[]>() { public int compare(int[] arr1, int[] arr2) { if (arr1[0] == arr2[0]) return arr2[1] - arr1[1]; else return arr1[0] - arr2[0]; } }); int dp[] = new int[envelopes.length]; int len = 0; for (int[] envelope : envelopes) { int index = Arrays.binarySearch(dp, 0, len, envelope[1]); if (index < 0) index = -(index + 1); dp[index] = envelope[1]; if (index == len) len++; } return len; }

https://blog.csdn.net/jmspan/article/details/51688907

此题和CareerCup中的马戏团是同一个问题，参见《Cracking the Coding Interview, 6th Edition》第17.8题。

这道题的关键在于能否看出是一个求最长公共子序列的问题。

方法一：使用TreeMap来查找较小的信封，此方法无法通过实现要求（TLE）

public int maxEnvelopes(int[][] envelopes) {

Arrays.sort(envelopes, new Comparator<int[]>() {

@Override

public int compare(int[] e1, int[] e2) {

return e1[0] - e2[0];

}

});

int max = 0;

int[] counts = new int[envelopes.length];

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

for (int i = 0; i < envelopes.length; i++) {

int[] envelope = envelopes[i];

Map<Integer, List<Integer>> hm = tm.headMap(envelope[1]);

for (List<Integer> list : hm.values()) {

for (int e : list) {

if (envelopes[e][0] < envelope[0])

counts[i] = Math.max(counts[i], counts[e]);

}

counts[i]++;

max = Math.max(max, counts[i]);

List<Integer> list = tm.get(envelope[1]);

if (list == null) {

list = new ArrayList<>();

tm.put(envelope[1], list);

}

list.add(i);

}

return max;

}

LeetCode 354 - Russian doll envelopes

Labels

Popular Posts