求Longest_Increasing_Subsequence JAVA O(nlgn) 代码# JobHunting - 待字闺中
m*k
1 楼
m*g
2 楼
public static int longestIncreasingSubConsequence(int[] array) {
int length = array.length;
int[] valueAtLength = new int[length];
int maxNow = 1;
valueAtLength[0] = array[0];
for(int i = 1; i < length; i++) {
int updatePos = findPos(valueAtLength, maxNow, array[i]);
if(updatePos == maxNow) {
valueAtLength[maxNow++] = array[i];
} else {
valueAtLength[updatePos] = array[i];
}
}
return maxNow;
}
private static int findPos(int[] array, int length, int target) {
int low = 0;
int high = length - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(mid == low) {
if(array[mid] >= target) {
return mid;
} else {
mid = mid + 1;
if(mid > high) {
break;
}
}
}
if(array[mid] >= target && array[mid - 1] < target) {
return mid;
} else if (array[mid] < target) {
low = mid + 1;
} else if(array[mid - 1] >= target) {
high = mid - 1;
}
}
return length;
}
变量的naming不好，自己可以修改
int length = array.length;
int[] valueAtLength = new int[length];
int maxNow = 1;
valueAtLength[0] = array[0];
for(int i = 1; i < length; i++) {
int updatePos = findPos(valueAtLength, maxNow, array[i]);
if(updatePos == maxNow) {
valueAtLength[maxNow++] = array[i];
} else {
valueAtLength[updatePos] = array[i];
}
}
return maxNow;
}
private static int findPos(int[] array, int length, int target) {
int low = 0;
int high = length - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(mid == low) {
if(array[mid] >= target) {
return mid;
} else {
mid = mid + 1;
if(mid > high) {
break;
}
}
}
if(array[mid] >= target && array[mid - 1] < target) {
return mid;
} else if (array[mid] < target) {
low = mid + 1;
} else if(array[mid - 1] >= target) {
high = mid - 1;
}
}
return length;
}
变量的naming不好，自己可以修改
m*k
3 楼
谢谢myanything 大虾，
int[] array= new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7,
15
};
如何输出 0 2 6 9 11 15 呢？
int[] array= new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7,
15
};
如何输出 0 2 6 9 11 15 呢？
m*g
4 楼
每次cached的时候把整个序列都cache下来，最后print out那个最长的序列
m*k
5 楼
刚在collabedit上被问到这道题，干脆就直接拷贝了，面试官，一国人兄弟说他看到过
这段ｃｏｄｅ，
既然这样，我也不需隐瞒，直接告诉他就是我发帖要的ｃｏｄｅ，再装没见过就太掩耳
盗铃了，呵呵。
看来国人兄弟也是有意放水，谢过了哈！
这段ｃｏｄｅ，
既然这样，我也不需隐瞒，直接告诉他就是我发帖要的ｃｏｄｅ，再装没见过就太掩耳
盗铃了，呵呵。
看来国人兄弟也是有意放水，谢过了哈！
相关阅读
请问我的F签证需要延期不？接受了offer，就可以辞职了吧？电话面试真心不好搞啊背景调查填工资，是基本工资还是把benefits也加上？About Palantir Technologies向hackie大牛学习开始做Project Euler矿工们都是怎么规划未来的？请问退还sign on bonus退税问题 (转载)有谁知道IBM的Emerging Leaders Program吗？还是中国人律师好第一次求offer （更新，两个都已拿到，感谢大家）Pepperdine EMBA 怎么样啊？亚洲移民数量超过老墨yelp的programming test什么难度呢？报口头offer sr. scientist,顺便问一下，要提前多久告诉现在雇主。痛苦得等offer背景调查的中国学位问题码工们都是怎么规划将来的？急问 OPT和H1B的gapH1B 申请。加州中心5.17受理。我也受到收据。现在办PP有多大意义？