logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
老公的回答
avatar
老公的回答# Joke - 肚皮舞运动
i*d
1 楼
you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
只能想到brute force的方法。有什么好的办法来做么？
谢谢了。
avatar
m*k
2 楼
请教各位：
I-140批准后，H1-B 回国签证好签吗？都要带些什么？
先谢了！
avatar
t*g
3 楼
$861.70 Closing Costs
因该lock吗，还是再等等？这几天好像rate一直在降。
avatar
a*e
4 楼
【 以下文字转载自 Family 讨论区 】
发信人: platinum05 (Kym), 信区: Family
标 题: 老公的回答
发信站: BBS 未名空间站 (Mon Jul 4 18:09:41 2011, 美东)
少语的老公，有些话让你很惊艳。
一日晚上，我在灌水，抱怨：“我一直都没学会打字。到现在还只会用两个手指敲。你
打得多好阿！我就不会十个手指打字。”
老公：“我老板也这样两个手指打。做老板不用会打字。”
我很开心，“你才厉害。你已经把我这只鹰养成了你身边的雀鸟。离开你我都不知如何
生活。”
老公依旧盯着他的电脑。
avatar
m*l
5 楼
why not put it in a hash first
then get rid of those that has no neighbor,
then get the max sequence.

.:

【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
avatar
d*o
6 楼
好签，就看了I-797和护照。
avatar
l*n
7 楼
not including initial deposit for escrow account,prepaid interest or title
services?
avatar
N*m
8 楼
精艳在哪里？

【在 a******e 的大作中提到】
: 【 以下文字转载自 Family 讨论区 】
: 发信人: platinum05 (Kym), 信区: Family
: 标 题: 老公的回答
: 发信站: BBS 未名空间站 (Mon Jul 4 18:09:41 2011, 美东)
: 少语的老公，有些话让你很惊艳。
: 一日晚上，我在灌水，抱怨：“我一直都没学会打字。到现在还只会用两个手指敲。你
: 打得多好阿！我就不会十个手指打字。”
: 老公：“我老板也这样两个手指打。做老板不用会打字。”
: 我很开心，“你才厉害。你已经把我这只鹰养成了你身边的雀鸟。离开你我都不知如何
: 生活。”
avatar
d*l
9 楼
我能想到nlogn的办法，二分窗口的长度，对每个长度l检查是否有某个长为l的
subarray满足条件，这个有点tricky但我觉得应该可以O(n)做到。

.:

【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
avatar
n*r
10 楼
签H1和140批准没有关系
H1只要有正当工作不容易据
但是以前读书容易check的签H1一样容易check
要准备工作相关材料和简历
avatar
b*d
11 楼
既然利率在降，可以再等等看。

【在 t***g 的大作中提到】
: $861.70 Closing Costs
: 因该lock吗，还是再等等？这几天好像rate一直在降。
avatar
b*c
12 楼
n log(n) 的算法能否详细说说，我看不明白，谢谢

【在 d*******l 的大作中提到】
: 我能想到nlogn的办法，二分窗口的长度，对每个长度l检查是否有某个长为l的
: subarray满足条件，这个有点tricky但我觉得应该可以O(n)做到。
:
: .:
avatar
v*n
13 楼
won't affect H1B
avatar
l*n
14 楼
not including initial deposit for escrow account,prepaid interest or title
services?
avatar
g*y
15 楼
这个题在本版问过，这是当时给的解，去考古一下吧
public class LongestRange {
public int[] longest(int[] a) {
int start = 0;
int maxLen = 0;

HashMap map = new HashMap();
for (int i=0; iint left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
int len = left + 1 + right;
map.put(a[i]-left, len);
map.put(a[i]+right, len);

if (len > maxLen) {
maxLen = len;
start = a[i] - left;
}
}

int[] b = new int[maxLen];
for (int i=0; ireturn b;
}
}
avatar
t*g
16 楼
no escrow, etc. But with a closing cost of about $800.

【在 l*****n 的大作中提到】
: not including initial deposit for escrow account,prepaid interest or title
: services?
avatar
H*s
17 楼
火鸡，还是你牛！PF
avatar
b*d
18 楼
这个是Refi吗？居然没有Escrow fee。

【在 t***g 的大作中提到】
: no escrow, etc. But with a closing cost of about $800.
avatar
b*c
19 楼
这是允许不连续的subarray, 问问楼主是不是想问contiguous subarray?

【在 g**********y 的大作中提到】
: 这个题在本版问过，这是当时给的解，去考古一下吧
: public class LongestRange {
: public int[] longest(int[] a) {
: int start = 0;
: int maxLen = 0;
:
: HashMap map = new HashMap();
: for (int i=0; i: int left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
: int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
avatar
d*n
20 楼
再等几天看看吧，今天rate变好的太没征兆了，估计银行也需要时间评估风险，然后再
看看是不是大幅降rate。
avatar
b*c
21 楼
题目要输出5,7,4,3,6，应该是指连续的吧，不连续的话输出34567
avatar
m*l
22 楼
嗯。。。
刚才我也看错了

【在 b*****c 的大作中提到】
: 题目要输出5,7,4,3,6，应该是指连续的吧，不连续的话输出34567
avatar
d*l
23 楼
上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
的满足条件的窗口。
对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
这样总的时间复杂度可以达到nlogn。空间复杂度O(n)。

【在 b*****c 的大作中提到】
: n log(n) 的算法能否详细说说，我看不明白，谢谢
avatar
m*l
24 楼
a = {4,5,1,5,7,4,3,6,9,8,9}
这个你怎么测？
你还是要O(N^2)吧
Dynamic Programming从后面开始应该O(n)吧

l

【在 d*******l 的大作中提到】
: 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
: 按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
: 列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
: 的满足条件的窗口。
: 对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
: 先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
: 口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
: 用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
: 个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
: 。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
avatar
b*c
25 楼
貌似长度l无法二分吧。。。。
5,7,4,3,6
不存在长度4的窗口，但有窗口5。。

l

【在 d*******l 的大作中提到】
: 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
: 按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
: 列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
: 的满足条件的窗口。
: 对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
: 先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
: 口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
: 用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
: 个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
: 。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
avatar
d*l
26 楼
我也发现了这个问题。。还是得从大到小。n^2

【在 b*****c 的大作中提到】
: 貌似长度l无法二分吧。。。。
: 5,7,4,3,6
: 不存在长度4的窗口，但有窗口5。。
:
: l
avatar
d*l
27 楼
这题dp怎么弄？好像不存在递推关系

【在 m********l 的大作中提到】
: a = {4,5,1,5,7,4,3,6,9,8,9}
: 这个你怎么测？
: 你还是要O(N^2)吧
: Dynamic Programming从后面开始应该O(n)吧
:
: l
avatar
g*y
28 楼
别，这不是我解的，我只是记下了当时大家讨论的最佳解。

【在 H****s 的大作中提到】
: 火鸡，还是你牛！PF
avatar
m*l
29 楼
我觉的这个主要是要知道什么时候该停
- keep track of remaining length
- keep track of average or sum of remaining elements.
if the difference between current number and subsequent numbers exceed a
threshold (stored), then stop
go to the next number.

【在 d*******l 的大作中提到】
: 这题dp怎么弄？好像不存在递推关系
avatar
d*l
30 楼
这个就不是dp了吧。我觉得想做到严格O(n^2)以下还是挺困难的

【在 m********l 的大作中提到】
: 我觉的这个主要是要知道什么时候该停
: - keep track of remaining length
: - keep track of average or sum of remaining elements.
: if the difference between current number and subsequent numbers exceed a
: threshold (stored), then stop
: go to the next number.
avatar
b*c
31 楼
我觉得反而怎么检测重复比较难

【在 m********l 的大作中提到】
: 我觉的这个主要是要知道什么时候该停
: - keep track of remaining length
: - keep track of average or sum of remaining elements.
: if the difference between current number and subsequent numbers exceed a
: threshold (stored), then stop
: go to the next number.
avatar
g*y
32 楼
ido not understand this problem statement
can you please elaborate?

.:

【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
avatar
r*g
33 楼
假设出现重复的数字，你是怎么处理的。
比如，1,2,2
到第一个2的时候len是依然是2，但是对应的可以转换为sequence的段应该为1了，这是
因为后面的所有的sequence，都不会用第一个2，要从第二个2重新开始计算可能的长度
，不是么？
你这个好像是算整个一段数可以组成的sequence长度，允许数字重复，但是题目要求是
选出一段不重复的可以组成sequence。

【在 g**********y 的大作中提到】
: 这个题在本版问过，这是当时给的解，去考古一下吧
: public class LongestRange {
: public int[] longest(int[] a) {
: int start = 0;
: int maxLen = 0;
:
: HashMap map = new HashMap();
: for (int i=0; i: int left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
: int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
avatar
b*c
35 楼
你就不看看我的回复么，呜呜
火鸡的算法是输出3，4，5，6，7的，不是5,7,4,3,6

【在 r*******g 的大作中提到】
: 假设出现重复的数字，你是怎么处理的。
: 比如，1,2,2
: 到第一个2的时候len是依然是2，但是对应的可以转换为sequence的段应该为1了，这是
: 因为后面的所有的sequence，都不会用第一个2，要从第二个2重新开始计算可能的长度
: ，不是么？
: 你这个好像是算整个一段数可以组成的sequence长度，允许数字重复，但是题目要求是
: 选出一段不重复的可以组成sequence。
avatar
r*g
36 楼
还是不一样把，这里是要找连续的一段sequence，这段sequence可以组成一个单调递增
1的序列。

【在 B*******1 的大作中提到】
: 火鸡的代码似乎漏了检测重复，原帖子在这里
: http://www.mitbbs.com/article_t/JobHunting/31911013.html
: 作者的代码是有检测重复的。
avatar
B*1
37 楼
恩，的确有点不一样，但是似乎把连接里面的方法改进一下就可以得到这题的答案了。

【在 r*******g 的大作中提到】
: 还是不一样把，这里是要找连续的一段sequence，这段sequence可以组成一个单调递增
: 1的序列。
avatar
s*e
38 楼
This is harder question.
For example.
int []a =new int[] {4,5,1,5,7,4,3,6,3,1,9,8};
should return {5,7,4,3,6}
rather than {3,4,5,6,7,8,9} or {5,7,4,3,6,9,8}
because it needs to consider that
the index of the elements should also
need to satisfy the condition
of longest consecutive increase sequence.

.:

【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
avatar
s*e
39 楼
A partial solution, not finished yet for the existing element.
use two hashtable,
one hashtable used for element value
another hashtable used for element index.
O(n) complexity.
static public int[] longest2(int[] a) {
int start = 0;
int maxLen = 0;

int indexStart =0;
int indexMaxLen =0;

HashMap map = new HashMap();
HashMap indexmap = new HashMap();

for (int i=0; iNode valNode = map.get(a[i]);
if(valNode==null){
Node newNode = new Node(1,i);
map.put(a[i], newNode);

indexmap.put(i, 1);

Node lowerValNode = map.get(a[i]-1);
if(lowerValNode!=null){
int newVal = lowerValNode.lenVal+1;
Node aiNode = map.get(a[i]);
aiNode.lenVal = newVal;

// map.put(a[i], newVal); //high part
Node startRangeNode = map.get(a[i]-newVal+1);
startRangeNode.lenVal = newVal;

// map.put(a[i]-newVal+1, newVal); //low part
if(newVal >maxLen){
maxLen = newVal;
start = a[i]-newVal+1;
}

//loop1, [a[i]-newVal+1, a[i]]
//check i-1
//check a[i-1] whether in loop1
if( (a[i-1]<=a[i]) && (a[i-1]>=a[i]-newVal+1) ){
//merge i with i-1 in the indexmap
Integer lowerIndexLenVal= indexmap.get(i-1);
int newIndexLenVal = lowerIndexLenVal+1;
indexmap.put(i, newIndexLenVal);
indexmap.put(i-newIndexLenVal+1, newIndexLenVal);

if(indexMaxLen < newIndexLenVal){
indexStart = i-newIndexLenVal+1;
indexMaxLen = newIndexLenVal;
}

}

}
Node highValNode = map.get(a[i]+1);
if(highValNode!=null){
int highVal = highValNode.lenVal;
Node aiNode = map.get(a[i]);
int newVal = aiNode.lenVal + highVal;
Node endRangeNode = map.get(a[i]+highVal);
endRangeNode.lenVal = newVal;

// map.put(a[i]+highValNode.lenVal, newVal);//high part
Node startRangeNode = map.get(a[i]+highVal-newVal+1);
startRangeNode.lenVal = newVal;
// map.put(a[i]+highVal-newVal+1, newVal); //low part

if(newVal >maxLen){
maxLen = newVal;
start = a[i]+highVal-newVal+1;
}

//loop1, [a[i]+highVal-newVal+1,a[i]+highVal]
//check
int p1 = highValNode.index;
Integer p1LenVal = indexmap.get(p1);
//range, [p1,p1+p1LenVal-1]
//check whether in loop1
if(a[p1+p1LenVal]>= a[i]+highVal-newVal+1 && a[p1+
p1LenVal]<= a[i]+highVal){
//merge loop2
Integer len1=indexmap.get(p1+p1LenVal);
int newLen1 = len1+p1LenVal;
indexmap.put(p1, newLen1);
indexmap.put(p1+newLen1-1, newLen1);
if(indexMaxLen < newLen1){
indexStart = p1;
indexMaxLen = newLen1;
}
}
if(a[p1-1]>= a[i]+highVal-newVal+1 && a[p1-1]<= a[i]+
highVal){
Integer len2=indexmap.get(p1-1);
Integer newp1LenVal = indexmap.get(p1);
int newLen2=len2+newp1LenVal;
indexmap.put(p1-len2, newLen2);
indexmap.put(p1-len2+newLen2-1, newLen2);
if(indexMaxLen < newLen2){
indexStart = p1-len2;
indexMaxLen = newLen2;
}
}
}
} else {
valNode.index=i;
indexmap.put(i, 1);
//more to be done

}

// Integer indexVal = indexmap.get(i);
// if(indexVal==null){
//
// }

}

int[] b = new int[maxLen];
for (int i=0; ib[i] = start + i;
System.out.print(b[i]+" ");
}
System.out.println();
for(Integer key : map.keySet()) {
Integer val = map.get(key).lenVal;
System.out.println("key: "+key+ " val: "+ val);
}

int[] b2 = new int[indexMaxLen];
for (int i=0; ib2[i] = indexStart + i;
System.out.print(a[b2[i]]+" ");
}
System.out.println();

return b;
}

.:

【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
avatar
i*d
40 楼
you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
只能想到brute force的方法。有什么好的办法来做么？
谢谢了。
avatar
m*l
41 楼
why not put it in a hash first
then get rid of those that has no neighbor,
then get the max sequence.

.:

【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
avatar
d*l
42 楼
我能想到nlogn的办法，二分窗口的长度，对每个长度l检查是否有某个长为l的
subarray满足条件，这个有点tricky但我觉得应该可以O(n)做到。

.:

【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
avatar
b*c
43 楼
n log(n) 的算法能否详细说说，我看不明白，谢谢

【在 d*******l 的大作中提到】
: 我能想到nlogn的办法，二分窗口的长度，对每个长度l检查是否有某个长为l的
: subarray满足条件，这个有点tricky但我觉得应该可以O(n)做到。
:
: .:
avatar
g*y
44 楼
这个题在本版问过，这是当时给的解，去考古一下吧
public class LongestRange {
public int[] longest(int[] a) {
int start = 0;
int maxLen = 0;

HashMap map = new HashMap();
for (int i=0; iint left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
int len = left + 1 + right;
map.put(a[i]-left, len);
map.put(a[i]+right, len);

if (len > maxLen) {
maxLen = len;
start = a[i] - left;
}
}

int[] b = new int[maxLen];
for (int i=0; ireturn b;
}
}
avatar
H*s
45 楼
火鸡，还是你牛！PF
avatar
b*c
46 楼
这是允许不连续的subarray, 问问楼主是不是想问contiguous subarray?

【在 g**********y 的大作中提到】
: 这个题在本版问过，这是当时给的解，去考古一下吧
: public class LongestRange {
: public int[] longest(int[] a) {
: int start = 0;
: int maxLen = 0;
:
: HashMap map = new HashMap();
: for (int i=0; i: int left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
: int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
avatar
b*c
47 楼
题目要输出5,7,4,3,6，应该是指连续的吧，不连续的话输出34567
avatar
m*l
48 楼
嗯。。。
刚才我也看错了

【在 b*****c 的大作中提到】
: 题目要输出5,7,4,3,6，应该是指连续的吧，不连续的话输出34567
avatar
d*l
49 楼
上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
的满足条件的窗口。
对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
这样总的时间复杂度可以达到nlogn。空间复杂度O(n)。

【在 b*****c 的大作中提到】
: n log(n) 的算法能否详细说说，我看不明白，谢谢
avatar
m*l
50 楼
a = {4,5,1,5,7,4,3,6,9,8,9}
这个你怎么测？
你还是要O(N^2)吧
Dynamic Programming从后面开始应该O(n)吧

l

【在 d*******l 的大作中提到】
: 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
: 按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
: 列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
: 的满足条件的窗口。
: 对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
: 先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
: 口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
: 用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
: 个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
: 。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
avatar
b*c
51 楼
貌似长度l无法二分吧。。。。
5,7,4,3,6
不存在长度4的窗口，但有窗口5。。

l

【在 d*******l 的大作中提到】
: 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
: 按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
: 列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
: 的满足条件的窗口。
: 对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
: 先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
: 口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
: 用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
: 个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
: 。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
avatar
d*l
52 楼
我也发现了这个问题。。还是得从大到小。n^2

【在 b*****c 的大作中提到】
: 貌似长度l无法二分吧。。。。
: 5,7,4,3,6
: 不存在长度4的窗口，但有窗口5。。
:
: l
avatar
d*l
53 楼
这题dp怎么弄？好像不存在递推关系

【在 m********l 的大作中提到】
: a = {4,5,1,5,7,4,3,6,9,8,9}
: 这个你怎么测？
: 你还是要O(N^2)吧
: Dynamic Programming从后面开始应该O(n)吧
:
: l
avatar
g*y
54 楼
别，这不是我解的，我只是记下了当时大家讨论的最佳解。

【在 H****s 的大作中提到】
: 火鸡，还是你牛！PF
avatar
m*l
55 楼
我觉的这个主要是要知道什么时候该停
- keep track of remaining length
- keep track of average or sum of remaining elements.
if the difference between current number and subsequent numbers exceed a
threshold (stored), then stop
go to the next number.

【在 d*******l 的大作中提到】
: 这题dp怎么弄？好像不存在递推关系
avatar
d*l
56 楼
这个就不是dp了吧。我觉得想做到严格O(n^2)以下还是挺困难的

【在 m********l 的大作中提到】
: 我觉的这个主要是要知道什么时候该停
: - keep track of remaining length
: - keep track of average or sum of remaining elements.
: if the difference between current number and subsequent numbers exceed a
: threshold (stored), then stop
: go to the next number.
avatar
b*c
57 楼
我觉得反而怎么检测重复比较难

【在 m********l 的大作中提到】
: 我觉的这个主要是要知道什么时候该停
: - keep track of remaining length
: - keep track of average or sum of remaining elements.
: if the difference between current number and subsequent numbers exceed a
: threshold (stored), then stop
: go to the next number.
avatar
g*y
58 楼
ido not understand this problem statement
can you please elaborate?

.:

【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
avatar
r*g
59 楼
假设出现重复的数字，你是怎么处理的。
比如，1,2,2
到第一个2的时候len是依然是2，但是对应的可以转换为sequence的段应该为1了，这是
因为后面的所有的sequence，都不会用第一个2，要从第二个2重新开始计算可能的长度
，不是么？
你这个好像是算整个一段数可以组成的sequence长度，允许数字重复，但是题目要求是
选出一段不重复的可以组成sequence。

【在 g**********y 的大作中提到】
: 这个题在本版问过，这是当时给的解，去考古一下吧
: public class LongestRange {
: public int[] longest(int[] a) {
: int start = 0;
: int maxLen = 0;
:
: HashMap map = new HashMap();
: for (int i=0; i: int left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
: int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
avatar
b*c
61 楼
你就不看看我的回复么，呜呜
火鸡的算法是输出3，4，5，6，7的，不是5,7,4,3,6

【在 r*******g 的大作中提到】
: 假设出现重复的数字，你是怎么处理的。
: 比如，1,2,2
: 到第一个2的时候len是依然是2，但是对应的可以转换为sequence的段应该为1了，这是
: 因为后面的所有的sequence，都不会用第一个2，要从第二个2重新开始计算可能的长度
: ，不是么？
: 你这个好像是算整个一段数可以组成的sequence长度，允许数字重复，但是题目要求是
: 选出一段不重复的可以组成sequence。
avatar
r*g
62 楼
还是不一样把，这里是要找连续的一段sequence，这段sequence可以组成一个单调递增
1的序列。

【在 B*******1 的大作中提到】
: 火鸡的代码似乎漏了检测重复，原帖子在这里
: http://www.mitbbs.com/article_t/JobHunting/31911013.html
: 作者的代码是有检测重复的。
avatar
B*1
63 楼
恩，的确有点不一样，但是似乎把连接里面的方法改进一下就可以得到这题的答案了。

【在 r*******g 的大作中提到】
: 还是不一样把，这里是要找连续的一段sequence，这段sequence可以组成一个单调递增
: 1的序列。
avatar
s*e
64 楼
This is harder question.
For example.
int []a =new int[] {4,5,1,5,7,4,3,6,3,1,9,8};
should return {5,7,4,3,6}
rather than {3,4,5,6,7,8,9} or {5,7,4,3,6,9,8}
because it needs to consider that
the index of the elements should also
need to satisfy the condition
of longest consecutive increase sequence.

.:

【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
avatar
s*e
65 楼
A partial solution, not finished yet for the existing element.
use two hashtable,
one hashtable used for element value
another hashtable used for element index.
O(n) complexity.
static public int[] longest2(int[] a) {
int start = 0;
int maxLen = 0;

int indexStart =0;
int indexMaxLen =0;

HashMap map = new HashMap();
HashMap indexmap = new HashMap();

for (int i=0; iNode valNode = map.get(a[i]);
if(valNode==null){
Node newNode = new Node(1,i);
map.put(a[i], newNode);

indexmap.put(i, 1);

Node lowerValNode = map.get(a[i]-1);
if(lowerValNode!=null){
int newVal = lowerValNode.lenVal+1;
Node aiNode = map.get(a[i]);
aiNode.lenVal = newVal;

// map.put(a[i], newVal); //high part
Node startRangeNode = map.get(a[i]-newVal+1);
startRangeNode.lenVal = newVal;

// map.put(a[i]-newVal+1, newVal); //low part
if(newVal >maxLen){
maxLen = newVal;
start = a[i]-newVal+1;
}

//loop1, [a[i]-newVal+1, a[i]]
//check i-1
//check a[i-1] whether in loop1
if( (a[i-1]<=a[i]) && (a[i-1]>=a[i]-newVal+1) ){
//merge i with i-1 in the indexmap
Integer lowerIndexLenVal= indexmap.get(i-1);
int newIndexLenVal = lowerIndexLenVal+1;
indexmap.put(i, newIndexLenVal);
indexmap.put(i-newIndexLenVal+1, newIndexLenVal);

if(indexMaxLen < newIndexLenVal){
indexStart = i-newIndexLenVal+1;
indexMaxLen = newIndexLenVal;
}

}

}
Node highValNode = map.get(a[i]+1);
if(highValNode!=null){
int highVal = highValNode.lenVal;
Node aiNode = map.get(a[i]);
int newVal = aiNode.lenVal + highVal;
Node endRangeNode = map.get(a[i]+highVal);
endRangeNode.lenVal = newVal;

// map.put(a[i]+highValNode.lenVal, newVal);//high part
Node startRangeNode = map.get(a[i]+highVal-newVal+1);
startRangeNode.lenVal = newVal;
// map.put(a[i]+highVal-newVal+1, newVal); //low part

if(newVal >maxLen){
maxLen = newVal;
start = a[i]+highVal-newVal+1;
}

//loop1, [a[i]+highVal-newVal+1,a[i]+highVal]
//check
int p1 = highValNode.index;
Integer p1LenVal = indexmap.get(p1);
//range, [p1,p1+p1LenVal-1]
//check whether in loop1
if(a[p1+p1LenVal]>= a[i]+highVal-newVal+1 && a[p1+
p1LenVal]<= a[i]+highVal){
//merge loop2
Integer len1=indexmap.get(p1+p1LenVal);
int newLen1 = len1+p1LenVal;
indexmap.put(p1, newLen1);
indexmap.put(p1+newLen1-1, newLen1);
if(indexMaxLen < newLen1){
indexStart = p1;
indexMaxLen = newLen1;
}
}
if(a[p1-1]>= a[i]+highVal-newVal+1 && a[p1-1]<= a[i]+
highVal){
Integer len2=indexmap.get(p1-1);
Integer newp1LenVal = indexmap.get(p1);
int newLen2=len2+newp1LenVal;
indexmap.put(p1-len2, newLen2);
indexmap.put(p1-len2+newLen2-1, newLen2);
if(indexMaxLen < newLen2){
indexStart = p1-len2;
indexMaxLen = newLen2;
}
}
}
} else {
valNode.index=i;
indexmap.put(i, 1);
//more to be done

}

// Integer indexVal = indexmap.get(i);
// if(indexVal==null){
//
// }

}

int[] b = new int[maxLen];
for (int i=0; ib[i] = start + i;
System.out.print(b[i]+" ");
}
System.out.println();
for(Integer key : map.keySet()) {
Integer val = map.get(key).lenVal;
System.out.println("key: "+key+ " val: "+ val);
}

int[] b2 = new int[indexMaxLen];
for (int i=0; ib2[i] = indexStart + i;
System.out.print(a[b2[i]]+" ");
}
System.out.println();

return b;
}

.:

【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
avatar
h*n
67 楼
my two cents:
1.先做个bit map.O(N) time. bitmap中放数在array中的位置.
bitmap(i) = position of i in Array.
2. bitmap中连续的数,按array中的位置,那bitmap的value排序. 最坏O(NlogN)
2b. 对排序的数找最长连续数列 (需要考虑重复数字). O(N)
好像重复的数字也可以.
avatar
r*g
68 楼
这个题最后讨论出来怎么弄？
相关阅读
别的不咋样，事业线挺深毛少将给广州大学题词 (转载)勇敢的心85岁生孩子是什么状况？这个是神马情况浅谈男人（女人）年龄与结婚意愿 (转载)深水炸弹之多米诺网曝北大教授孔庆东在张家界天门山寺出家zz那个荡气回肠的长镜头千万别模仿还在纠结买什么样的摩托车吗安妮宝贝笔下的男女谁吃过这种巧克力？亮了：成都军区工兵团官兵帮助灾区村民抢救家畜 (转载)忽然意识到不对劲儿：地震了的庐山怎么在四川啊？关于博导的特长，NSA founded research国家地震局专家严正公告： (转载)Re: 小日本也太逆天了 (转载)cosplayReady for snack time?
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。