w***y
发帖数: 6251 | 1 maximum length subarray such that maximum difference is less than k
在这里看到解法 http://effprog.blogspot.com/2010/12/maximum-length-subarray-such-that.html
需要判断很多情况, 答案看了好几遍才看懂. 不知道这种题目考的是什么? 如果面
试被问到,怎么找切入点呢? |
h********e
发帖数: 1972 | 2 两个指针扫描~这种题目没啥好说的。。就是有一些贪心(单调性)的思想，避免不必要
的计算。你给的那个网站程序写的很差。 |
w***y
发帖数: 6251 | 3 有没有好的算法啊? 我看那个implementation被绕的很晕
我现在还不太明白需要greedy和dynamic programming的问题怎么找切入点, 好搓啊,
咋办啊, 面试还有不到3周.........
【在 h********e 的大作中提到】
: 两个指针扫描~这种题目没啥好说的。。就是有一些贪心(单调性)的思想，避免不必要
: 的计算。你给的那个网站程序写的很差。
|
h********e
发帖数: 1972 | 4 这题硬算是dp也行。。算是贪心也行。。面试就爱考这种ad hoc的算法。一般都是有几
种套路，脑子要转的比较快就能知道那种适用了。。多看点题目想想吧。没什么好办法
。。这种题目无非就是那种最大substring sum的题目的变种。有时候一个指针就够了
，有时候要用两个。有时候还要用stack。。一般找出单调性，也就是哪些计算在brute
force的时候不必要重复，就能想到O(n)算法了。。 |
l***i
发帖数: 1309 | 5 dynamic programming?
dp[len][pos] = (minval, maxval) remembers minval and maxval in range pos to
pos+len-1
you can computer each len from 1 to n, for each pos from 0 to n-1
dp[len][pos] = update from dp[len-1][pos+1]
That is O(n^2)
faster solutions? |
w***y
发帖数: 6251 | 6 多谢指点了!
我再多看看题目, 好好总结一下套路
brute
【在 h********e 的大作中提到】
: 这题硬算是dp也行。。算是贪心也行。。面试就爱考这种ad hoc的算法。一般都是有几
: 种套路，脑子要转的比较快就能知道那种适用了。。多看点题目想想吧。没什么好办法
: 。。这种题目无非就是那种最大substring sum的题目的变种。有时候一个指针就够了
: ，有时候要用两个。有时候还要用stack。。一般找出单调性，也就是哪些计算在brute
: force的时候不必要重复，就能想到O(n)算法了。。
|
h********e
发帖数: 1972 | 7 这种题目会出现的非常频繁。建议熟练掌握。全是O(n)算法。 |
e*****e
发帖数: 1275 | 8 这题目一看就最好是DP，又快又简单，不会被指针绕来绕去绕晕。DP就如下情况，最大
subarray + 1, 新的最大subarray. DP 是 O(n),可以不O(n2)。就记下尾巴下新的最大
subarray就可以了。 |
h********e
发帖数: 1972 | 9 指针dp都一样的。。都是同一个算法。关键就是搞个数据结构。每次如果+1 爆仓了，能快速把尾指针挪到正确位置，也就是动态维护一个max，min的跳表之类的结构,每个max都指向该max的位置+1到头指针位置的数组元素中的max(i.e., the second largest after max's position)。 |
H****r
发帖数: 2801 | 10 数组是排序好的吗？
【在 w***y 的大作中提到】
: maximum length subarray such that maximum difference is less than k
: 在这里看到解法 http://effprog.blogspot.com/2010/12/maximum-length-subarray-such-that.html
: 需要判断很多情况, 答案看了好几遍才看懂. 不知道这种题目考的是什么? 如果面
: 试被问到,怎么找切入点呢?
|
|
|
h********e
发帖数: 1972 | |
e*****e
发帖数: 1275 | 12 这题目一看就最好是DP，又快又简单，不会被指针绕来绕去绕晕。DP就如下情况，最大
subarray + 1, 新的最大subarray. DP 是 O(n),可以不O(n2)。就记下尾巴下新的最大
subarray就可以了。 |
p*****2
发帖数: 21240 | 13
，能快速把尾指针挪到正确位置，也就是动态维护一个max，min的跳表之类的结构,每
个max都指向该max的位置+1到头指针位置的数组元素中的max(i.e., the second
largest after max's position)。
跳表用什么数据结构呢？TreeSet是不是可以？
【在 h********e 的大作中提到】
: 指针dp都一样的。。都是同一个算法。关键就是搞个数据结构。每次如果+1 爆仓了，能快速把尾指针挪到正确位置，也就是动态维护一个max，min的跳表之类的结构,每个max都指向该max的位置+1到头指针位置的数组元素中的max(i.e., the second largest after max's position)。
|
h********e
发帖数: 1972 | 14 跳表是我很早以前学数据结构国内书翻译的。。我也不知道叫啥。。就是数组指针做成的链表把。。
btw 刚才看了楼主贴的老印网站的程序。。丫的写了个平方的算法。。。 |
p*****2
发帖数: 21240 | 15
成的链表把。。
你的意思是链表每一个元素指向一个数组？
【在 h********e 的大作中提到】
: 跳表是我很早以前学数据结构国内书翻译的。。我也不知道叫啥。。就是数组指针做成的链表把。。
: btw 刚才看了楼主贴的老印网站的程序。。丫的写了个平方的算法。。。
|
h********e
发帖数: 1972 | 16 不是。。是用数组存链表哈哈哈。。。最土的那种啊。。我记得是一本90年代的数据结构的蓝色皮的书。。。。。 跟并查集差不多的那种表示法.
可恶的是这个阿三写了个加阶的程序贴到网上。。。让LZ琢磨了一阵子。。太误导人了 |
p*****2
发帖数: 21240 | 17 我用TreeSet写了一个，然后发现不能有重复的元素。看来还得自定义数据结构。
int[] Max(int[] arr, int k)
{
if (arr == null || arr.length == 0)
return arr;
TreeSet ts = new TreeSet();
int max = 0;
int mstart = 0;
int mend = 0;
int start = 0;
int end = 0;
for (int i = 0; i < arr.length; i++)
{
while (!ts.isEmpty() && Math.abs(ts.first().value - arr[i]) >= k)
{
start = Math.max(start, ts.first().index + 1);
ts.remove(ts.first());
}
while (!ts.isEmpty() && Math.abs(ts.last().value - arr[i]) >= k)
{
start = Math.max(start, ts.last().index + 1);
ts.remove(ts.last());
}
Node[] nodes = ts.toArray(new Node[0]);
for (Node node : nodes)
{
if (node.index < start)
ts.remove(node);
}
ts.add(new Node(i, arr[i]));
end = i;
if (ts.size() > max)
{
max = ts.size();
mstart = start;
mend = end;
}
}
return Arrays.copyOfRange(arr, mstart, mend + 1);
} |
e*****e
发帖数: 1275 | 18 用DP乱写了点code，发现还是得O(n2),不好意思，刚刚想歪了。
typedef struct subarray_info
{
int start;
int end;
int min;
int max;
int new_start;
}subarray_info;
void calculate_subarray_info (subarray_info * info, int input_array[], int n
, int k)
{
if ( n == 1)
{
info[0].start = 0;
info[0].end = 0;
info[0].min = input_array[0];
info[0].max = input_array[0];
info[0].new_start = 0;
return;
}
calculate_subarray_info (info, input_array, n-1, k);
subarray_info tmp_info = info[n-2];
if ( tmp_info.start == tmp_info.new_start)
{
//currently the solution is from start all the way to the end
if ( (tmp_info.max - input_array[n-1]) <= k && (input_array[n-1] -
tmp_info.min) <= k)
{
//and the soluton continue grow
info[n-1].start = tmp_info.start;
info[n-1].end = n-1;
info[n-1].min = (input_array[n-1] < tmp_info.min)? input_array[n
-1] :tmp_info.min;
info[n-1].max = (input_array[n-1]> tmp_info.max)? input_array[n-
1] :tmp_info.max;
info[n-1].new_start = tmp_info.new_start;
return;
}
else
{
//now the solution break, calculate all the way back for the new
solution start from end
int tmp_max, tmp_min;
tmp_max = input_array[n-1];
tmp_min = input_array[n-1];
int tmp_new_start = n -1;
for (int i = n -2; i >tmp_info.start; i--)
{
if ((tmp_max - input_array[i]) > k || (input_array[i] - tmp_
min ) > k)
{
tmp_new_start = i + 1;
break;
}
tmp_max = (input_array[i]>tmp_max)? input_array[i]:tmp_max;
tmp_min = (input_array[i]
}
//something went wrong here.throw a exception
info[n-1].start = tmp_info.start;
info[n-1].end = tmp_info.end;
info[n-1].min = tmp_min;
info[n-1].max = tmp_max;
info[n-1].new_start = tmp_new_start;
return;
}
}
else
{
//current best solution is a subarray in the middle and can not grow
anymore
if ( (tmp_info.max - input_array[n-1]) <= k && (input_array[n-1] -
tmp_info.min) <= k)
{
//and the new soluton continue grow, compare the new solution's
lenght with the old one
if ( (n-1 - tmp_info.new_start) > (tmp_info.end - tmp_info.start
))
{
//the new solution is the longer one, update it
info[n-1].start = tmp_info.new_start;
info[n-1].end = n-1;
info[n-1].min = (input_array[n-1] < tmp_info.min)? input_
array[n-1] :tmp_info.min;
info[n-1].max = (input_array[n-1]> tmp_info.max)? input_
array[n-1] :tmp_info.max;
info[n-1].new_start = tmp_info.new_start;
return;
}
else
{
//still the old solution is the best solution so far
info[n-1].start = tmp_info.start;
info[n-1].end = tmp_info.end;
info[n-1].min = (input_array[n-1] < tmp_info.min)? input_
array[n-1] :tmp_info.min;
info[n-1].max = (input_array[n-1]> tmp_info.max)? input_
array[n-1] :tmp_info.max;
info[n-1].new_start = tmp_info.new_start;
return;
}
}
else
{
//now the new solution break, calculate all the way back for the
new solution start from end
int tmp_max, tmp_min;
tmp_max = input_array[n-1];
tmp_min = input_array[n-1];
int tmp_new_start = n -1;
for (int i = n -2; i >tmp_info.new_start; i--)
{
if ((tmp_max - input_array[i]) > k || (input_array[i] - tmp_
min ) > k)
{
tmp_new_start = i+1;
break;
}
tmp_max = (input_array[i]>tmp_max)? input_array[i]:tmp_max;
tmp_min = (input_array[i]
}
info[n-1].start = tmp_info.start;
info[n-1].end = tmp_info.end;
info[n-1].min = tmp_min;
info[n-1].max = tmp_max;
info[n-1].new_start = tmp_new_start;
return;
}
}
}
//maximum length subarray such that maximum difference is less than k
//gonna solve this problem using dynamical programming
int get_max_len_subarray_with_maxdiff ( int input_array [] , int n, int k)
{
///remember veirfy the input: input_array, n, k
subarray_info * info = new subarray_info[n];
calculate_subarray_info (info, input_array, n, k);
int max_len = info[0].end - info[0].start + 1;
for (int i = 0; i < n; i++)
{
int new_len = info[i].end - info[i].start + 1;
if (new_len > max_len)
max_len = new_len;
}
return max_len;
}
void test_get_max_subarray (void)
{
int a [] = { 1, 2, 3, 4, 6, 11, 14, 33, 28, 29, 30, 31, 32, 28, 28, 29,
30, 1, 2, 3};
int result = get_max_len_subarray_with_maxdiff ( a , 20, 10);
printf ("result %d\n",result);
} |
h********e
发帖数: 1972 | 19 这题O(n)不难吧。。就是写起来麻烦了点。
主要是h,t 两个指针，每次h往前挪到爆了k 为止。过程中要维护如下内容：
h和t之间的 最大元素 max 的位置， max的位置到h 之间 最大元素max的位置， 第一
个用指针指向第二个，然后指向第三个，等等。
min 也同样要记下这些。
每次刷新max或者min，都从当前位置重新来建立这么一个linked list。可以直接在数
组上维护。
每次爆了如果是max 爆，去min 的linked list里面找一个对的(i.e., 最靠前面的和h
比相差小于k)然后update tail位置 （要注意tail的位置其实是linked list上一个元
素+1），然后继续挪h；
如果爆了min，就去max里面干同样的事情。 |
p*****2
发帖数: 21240 | 20
h
应该跟我写的那个意思差不多。
【在 h********e 的大作中提到】
: 这题O(n)不难吧。。就是写起来麻烦了点。
: 主要是h,t 两个指针，每次h往前挪到爆了k 为止。过程中要维护如下内容：
: h和t之间的 最大元素 max 的位置， max的位置到h 之间 最大元素max的位置， 第一
: 个用指针指向第二个，然后指向第三个，等等。
: min 也同样要记下这些。
: 每次刷新max或者min，都从当前位置重新来建立这么一个linked list。可以直接在数
: 组上维护。
: 每次爆了如果是max 爆，去min 的linked list里面找一个对的(i.e., 最靠前面的和h
: 比相差小于k)然后update tail位置 （要注意tail的位置其实是linked list上一个元
: 素+1），然后继续挪h；
|
|
|
l***i
发帖数: 1309 | 21 use hellobruce's idea, here is code
assume input is a[N] and difference is K
typedef pair pii;
// small keeps track of min while p1 is moving to right
// large keeps track of max while p1 is moving to right
deque small, large;
int p1, p2;
int ans=0, curr=0;
small.clear(); large.clear();
for(p1=p2=0; p2
{
int val = a[p2];
while(!small.empty() && val > small.front().first + K)
{
p1=small.front().second +1;
small.pop_front();
}
while(!large.empty() && val < large.front.first - K)
{
p1=max(p1, large.front().second+1);
large.pop_front();
}
curr = p2-p1+1;
ans = max(ans, curr);
while(!small.empty() && small.back().first >= val)
{ small.pop_back(); }
small.push_back(make_pair(val, p2));
while(!large.empty() && large.back().first <= val)
{ large.pop_back(); }
large.push_back(make_pair(val, p2));
}
return ans; |
m********g
发帖数: 272 | 22 这样也不是O(n)呀，每次diff超过k, 找下一个最大或最小还要遍历max_list or min_
list,which is not O(1).
h
【在 h********e 的大作中提到】
: 这题O(n)不难吧。。就是写起来麻烦了点。
: 主要是h,t 两个指针，每次h往前挪到爆了k 为止。过程中要维护如下内容：
: h和t之间的 最大元素 max 的位置， max的位置到h 之间 最大元素max的位置， 第一
: 个用指针指向第二个，然后指向第三个，等等。
: min 也同样要记下这些。
: 每次刷新max或者min，都从当前位置重新来建立这么一个linked list。可以直接在数
: 组上维护。
: 每次爆了如果是max 爆，去min 的linked list里面找一个对的(i.e., 最靠前面的和h
: 比相差小于k)然后update tail位置 （要注意tail的位置其实是linked list上一个元
: 素+1），然后继续挪h；
|
z*****n
发帖数: 447 | 23 跳表是不是skiplist
成的链表把。。
【在 h********e 的大作中提到】
: 跳表是我很早以前学数据结构国内书翻译的。。我也不知道叫啥。。就是数组指针做成的链表把。。
: btw 刚才看了楼主贴的老印网站的程序。。丫的写了个平方的算法。。。
|
h********e
发帖数: 1972 | 24 仔细想啊-0- 。。。别重复找,每次min，max都是list的第一个元素，不需要扫一遍list。。找过的都扔掉了。。amortize下来肯定O(1).就两个指针，永远不回头的。不可能搞出n^2的复杂度。
应该叫skiplist。。不过这里的用法跟skiplist的本意应该不一样。反正很简单，就是个array里面每个元素都有可能有一个指针指向下一个要去的地方。这样就有O(1) access, which is better than linked list.
【在 m********g 的大作中提到】
: 这样也不是O(n)呀，每次diff超过k, 找下一个最大或最小还要遍历max_list or min_
: list,which is not O(1).
:
: h
|
s******n
发帖数: 3946 | 25 这个不对吧？，举个反例
k=10
前5个元素是
-10, -7, -9, -8，0
第6个元素是1
照你的做法，前5个元素处理完min linklist是-10, -9, -8。新元素1让max暴仓，你去
linklist找了-9。但选-7是更优解。
h
【在 h********e 的大作中提到】
: 这题O(n)不难吧。。就是写起来麻烦了点。
: 主要是h,t 两个指针，每次h往前挪到爆了k 为止。过程中要维护如下内容：
: h和t之间的 最大元素 max 的位置， max的位置到h 之间 最大元素max的位置， 第一
: 个用指针指向第二个，然后指向第三个，等等。
: min 也同样要记下这些。
: 每次刷新max或者min，都从当前位置重新来建立这么一个linked list。可以直接在数
: 组上维护。
: 每次爆了如果是max 爆，去min 的linked list里面找一个对的(i.e., 最靠前面的和h
: 比相差小于k)然后update tail位置 （要注意tail的位置其实是linked list上一个元
: 素+1），然后继续挪h；
|
h********e
发帖数: 1972 | 26 你理解错了或者你没有仔细阅读。 我说去找list里面下一个in range max的上一个元
素+1的位置。也就是-7的位置开始。 |
z**********2
发帖数: 307 | 27 强大
【在 w***y 的大作中提到】
: maximum length subarray such that maximum difference is less than k
: 在这里看到解法 http://effprog.blogspot.com/2010/12/maximum-length-subarray-such-that.html
: 需要判断很多情况, 答案看了好几遍才看懂. 不知道这种题目考的是什么? 如果面
: 试被问到,怎么找切入点呢?
|
