Java编程

牛客网算法视频百度云

View Code

回归到本题的解法

import java.util.Arrays;import java.util.Comparator;/* * 题意:CackingCodingInterview上的叠罗汉问题,leetcode上的沙皇问题 * 将最长递增子序列扩展到了二维 *//* * solutions : 时间复杂度O(n+n*log(n)+n*log(n)) 也就是n*log(n) * 目标是将二维数组抽象成一维数组,再利用解最长递增子序列的解法来解决这个问题 * 首先我们需要将二维数组排序,排序策略是先按照array[i][0]排序,在array[i][0]相同的情况下,按照array[i][1]倒序排序 * 为了排序我们可将array抽象成一个类A,二元组的两个元素分别是这个类A的两个成员变量 * 将array转化为A的数组,给A自实现一个排序函数(按照上面的排序策略) * 接下来就转化为了最长递增子序列问题,将类A数组的h成员变量看作之前的一维数组就好了 */public class Leetcode354 { public int maxEnvelopes(int[][] envelopes) { if (envelopes.length 2) return envelopes.length; A[] a = new A[envelopes.length]; for (int i = 0; i envelopes.length; i++) { a[i] = new A(envelopes[i][0],envelopes[i][1]); } Arrays.sort(a,new Comparator A (){ @Override public int compare(A a, A b) { if (a.w b.w) { return 1; } else if (a.w b.w) { return -1; } else { if (b.h a.h) { return 1; } else if (b.h a.h) { return -1; } else return 0; } } }); int maxLen = 0; int[] h = new int[envelopes.length]; h[0] = a[0].h; for (int i = 1; i envelopes.length; i++) { int pos = getPos(h, 0, maxLen – 1,a[i].h); if (pos == -1) { h[maxLen++] = a[i].h; } else h[pos] = a[i].h; } return maxLen; } public int getPos(int[] h, int left, int right, int num) { if (left = right) { int mid = left + (right – left) / 2; if (h[mid] = num) { int pos = getPos(h, left, mid – 1, num); if (pos == -1) return mid; return pos; } else { return getPos(h, mid + 1, right, num); } } return -1; } public static void main(String[] args){ Leetcode354 l = new Leetcode354(); int [][] envelopes = {{5,1},{6,4},{6,7},{2,3}}; l.maxEnvelopes(envelopes); } }class A { int w = 0; int h = 0; public A(int w, int h) { this.w = w; this.h = h; }}

牛客网算法视频百度云

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注