avatar
问一道题目(3)# JobHunting - 待字闺中
f*i
1
Given an array A[i..j] find out maximum j-i such that A[i]这题我记得很早的时候有讨论过,考古找不到答案,希望有牛人为我再解释下,多谢
avatar
h*n
2
are A[i..j] distinct values?

time.

【在 f*********i 的大作中提到】
: Given an array A[i..j] find out maximum j-i such that A[i]: 这题我记得很早的时候有讨论过,考古找不到答案,希望有牛人为我再解释下,多谢
avatar
f*4
3
是我理解不对?
maximum j-i,i从0开始往中间扫描,j从数组结束开始往中间扫描
只要A[i]
time.

【在 f*********i 的大作中提到】
: Given an array A[i..j] find out maximum j-i such that A[i]: 这题我记得很早的时候有讨论过,考古找不到答案,希望有牛人为我再解释下,多谢
avatar
i*e
4
这题没那么简单,给个反例:
A = { 3, 2, 4, 1 }
我暂时想到排序的解法,但是是 O(n log n),就算有重复的值的也能处理。我也想知
道有没有 O(n) 的解。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 f****4 的大作中提到】
: 是我理解不对?
: maximum j-i,i从0开始往中间扫描,j从数组结束开始往中间扫描
: 只要A[i]:
: time.

avatar
d*l
5
我想了个方法,不知道对不对:
int MaxDistance(int a[], int n)
{
int i, j;
int ans = 0;
vector vi;
vi.push_back(0);
int pre = a[0];
for(i = 1; i < n; i++)
if(a[i] < pre) {
pre = a[i];
vi.push_back(i);
}
j = n-1;
for(i = vi.size()-1; i >= 0; i--) {
int t = vi[i];
while(j > t) {
if(a[j] > a[t]) {
ans = max(ans, j-t);
break;
}
j--;
}
}
return ans;
}
avatar
g*y
6
这个好象有问题,你找了一条包含a0的降链,但是最大路径不一定包含这条链的点。反
例应该不难找。

【在 d*******l 的大作中提到】
: 我想了个方法,不知道对不对:
: int MaxDistance(int a[], int n)
: {
: int i, j;
: int ans = 0;
: vector vi;
: vi.push_back(0);
: int pre = a[0];
: for(i = 1; i < n; i++)
: if(a[i] < pre) {

avatar
g*y
7
我觉得不象有O(n)的算法,考虑个极端情况:A是递减数组,意思是不存在那样的j-i。
你要不排序,好象很难排除所有的情况。
期待有人给个巧妙解。

【在 i**********e 的大作中提到】
: 这题没那么简单,给个反例:
: A = { 3, 2, 4, 1 }
: 我暂时想到排序的解法,但是是 O(n log n),就算有重复的值的也能处理。我也想知
: 道有没有 O(n) 的解。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

avatar
i*e
8
好样的!这个思路是对的,也的确是 O(n)。
这个思路很巧妙地避免了没有必要的比较。

【在 d*******l 的大作中提到】
: 我想了个方法,不知道对不对:
: int MaxDistance(int a[], int n)
: {
: int i, j;
: int ans = 0;
: vector vi;
: vi.push_back(0);
: int pre = a[0];
: for(i = 1; i < n; i++)
: if(a[i] < pre) {

avatar
i*e
9
我觉得他的解法是对的,也可以证明是对的。

【在 g**********y 的大作中提到】
: 这个好象有问题,你找了一条包含a0的降链,但是最大路径不一定包含这条链的点。反
: 例应该不难找。

avatar
i*e
10
递减不是 O(n^2).
A = { 5 4 3 2 1 }
在递减的情况,while loop 里每次最多比较两次。
所以是 2* n.
avatar
g*y
11
是我理解有问题?
5 4 3 2 1 10 9 8 7 6
v[] = {5, 4, 3, 2, 1}
j = 9, i=4, a[j] > v[4], so break, ans = 5, j--
j = 8, i=3, a[j] > v[3], so break, ans = 5, j--
...
这样算下来对吗?

【在 i**********e 的大作中提到】
: 我觉得他的解法是对的,也可以证明是对的。
avatar
d*l
12
这题其实我觉得和很久之前讨论的那个给定a[i],每个a[i]代表一个高度为a[i]的木板
,问最多能装多少水的题很像。思路就是先从a[0]开始找一个降序的序列作为start
point的candidates,很容易证明不在这个序列中的点不可能得到最优解:加入某个a[k
]不在这个序列中,那就存在a[i] <= a[k], i < k。假如存在j,使a[k] < a[j],那必
然有a[i] < a[j],而j-k < j-i,所以a[k]就不可能是最优解的起点。
于是我们只要尝试这个序列中的所有点c[i],假设每个c[i]对应的最优解的end point
是d[i],很容易看出d[i]是一个非降的序列,所以可以从数组c的末尾开始向前循环,j
初始值是n-1,对于每一个c[i],j向前移动到合适的位置,根据d[i]的单调性,j是可
以不回退的,这样总共的复杂度就是O(n)。
惟一的concern是,如果是递减的序列,最大的j-i似乎是-1,如果这个也要考虑的话要
单独处理下,如果序列所有元素的相等,结果又没有定义。不过这些都是细节的问题了

【在 g**********y 的大作中提到】
: 这个好象有问题,你找了一条包含a0的降链,但是最大路径不一定包含这条链的点。反
: 例应该不难找。

avatar
d*l
13
这里break之后,就不会j--了,只有i--,只有不满足判断条件才会j--

【在 g**********y 的大作中提到】
: 是我理解有问题?
: 5 4 3 2 1 10 9 8 7 6
: v[] = {5, 4, 3, 2, 1}
: j = 9, i=4, a[j] > v[4], so break, ans = 5, j--
: j = 8, i=3, a[j] > v[3], so break, ans = 5, j--
: ...
: 这样算下来对吗?

avatar
g*y
14
是我想错了。

【在 d*******l 的大作中提到】
: 这里break之后,就不会j--了,只有i--,只有不满足判断条件才会j--
avatar
i*e
15
有一点小错误纠正一下。
当 j = 8, i = 3, a[j] > v[3], update ans = 6 and break,因为这是更大的距离。
这题非常巧妙,我想我在面试时第一次碰着这样的题目如果没有提示肯定想不到。
我说说一个以我角度 来理解我对darksteel同学给的答案
这个方法很巧妙,因为那个起始点肯定从左到右必定是个递减序列。
为什么呢?
当有另一个 j > i,但是 A[j] > A[i],你会选择 j 为起始点吗?不会,因为选 j 为
起始点得到最远的距离为 k,那么我同样可以选 i 为起始点得到 k + (j-i) 的距离,
也就是更加好的答案。利用这方面的想法来理解这题就简单多了。

【在 g**********y 的大作中提到】
: 是我理解有问题?
: 5 4 3 2 1 10 9 8 7 6
: v[] = {5, 4, 3, 2, 1}
: j = 9, i=4, a[j] > v[4], so break, ans = 5, j--
: j = 8, i=3, a[j] > v[3], so break, ans = 5, j--
: ...
: 这样算下来对吗?

avatar
g*e
16
学习

[k
point
,j
。反

【在 d*******l 的大作中提到】
: 这题其实我觉得和很久之前讨论的那个给定a[i],每个a[i]代表一个高度为a[i]的木板
: ,问最多能装多少水的题很像。思路就是先从a[0]开始找一个降序的序列作为start
: point的candidates,很容易证明不在这个序列中的点不可能得到最优解:加入某个a[k
: ]不在这个序列中,那就存在a[i] <= a[k], i < k。假如存在j,使a[k] < a[j],那必
: 然有a[i] < a[j],而j-k < j-i,所以a[k]就不可能是最优解的起点。
: 于是我们只要尝试这个序列中的所有点c[i],假设每个c[i]对应的最优解的end point
: 是d[i],很容易看出d[i]是一个非降的序列,所以可以从数组c的末尾开始向前循环,j
: 初始值是n-1,对于每一个c[i],j向前移动到合适的位置,根据d[i]的单调性,j是可
: 以不回退的,这样总共的复杂度就是O(n)。
: 惟一的concern是,如果是递减的序列,最大的j-i似乎是-1,如果这个也要考虑的话要

avatar
d*l
17
握手~~就是这个意思

【在 i**********e 的大作中提到】
: 有一点小错误纠正一下。
: 当 j = 8, i = 3, a[j] > v[3], update ans = 6 and break,因为这是更大的距离。
: 这题非常巧妙,我想我在面试时第一次碰着这样的题目如果没有提示肯定想不到。
: 我说说一个以我角度 来理解我对darksteel同学给的答案
: 这个方法很巧妙,因为那个起始点肯定从左到右必定是个递减序列。
: 为什么呢?
: 当有另一个 j > i,但是 A[j] > A[i],你会选择 j 为起始点吗?不会,因为选 j 为
: 起始点得到最远的距离为 k,那么我同样可以选 i 为起始点得到 k + (j-i) 的距离,
: 也就是更加好的答案。利用这方面的想法来理解这题就简单多了。

avatar
i*e
18
darksteel,
"这题其实我觉得和很久之前讨论的那个给定a[i],每个a[i]代表一个高度为a[i]的木
板,问最多能装多少水的题很像。"
那题的解法是不是用两个指针(也就是 i 和 j 两个 index),第一个从左到右的方向
,和第二个从右到左的方向缩进?从左到右 和右到左 必须是个递增的序列。每一步首
先看左边 / 右边的柱子哪个比较高,同时更新最大容量值。如果左边柱子高些的话,
就从右到左进行缩进(反之亦然),直到 A[new_j] > A[old_j],然后再更新最大值。
之后也一样,重新比较左边右边的柱子,再重复移动指针,直到他们两个相遇。
不知道这个理解对不对呢?

【在 d*******l 的大作中提到】
: 握手~~就是这个意思
avatar
d*l
19
差不多,你居然还记得。。
当时好像没有最后的定论,但我记得我最后想到的方法和这题的差不多,我是只考虑一
边的,一个i一个j,开始在两端。从a[0]开始只考虑递增的序列,原因和这题差不多,
然后对于每个a[i],j也从会往前退到第一个a[j] > a[i]的地方,并不断更新最大值,
然后对于下一个a[i],j可以不回头的继续回退,直到i,j相遇。其实跟你说的每次矮
的那边缩进好像效果是一样的。有点区别是那道题在两边缩进的时候每一步都要去试着
更新最大值,因为那个要求的是容量,和距离以及a[i]的值都有关系,所以每个i,j都
有可能是最优解。那题是可以直接从两边扫,但这题没法直接从两边扫,所以只能先把
递减的序列求出来,然后再从同一边扫。

【在 i**********e 的大作中提到】
: darksteel,
: "这题其实我觉得和很久之前讨论的那个给定a[i],每个a[i]代表一个高度为a[i]的木
: 板,问最多能装多少水的题很像。"
: 那题的解法是不是用两个指针(也就是 i 和 j 两个 index),第一个从左到右的方向
: ,和第二个从右到左的方向缩进?从左到右 和右到左 必须是个递增的序列。每一步首
: 先看左边 / 右边的柱子哪个比较高,同时更新最大容量值。如果左边柱子高些的话,
: 就从右到左进行缩进(反之亦然),直到 A[new_j] > A[old_j],然后再更新最大值。
: 之后也一样,重新比较左边右边的柱子,再重复移动指针,直到他们两个相遇。
: 不知道这个理解对不对呢?

avatar
x*n
20
Brilliant!

[k
point
,j

【在 d*******l 的大作中提到】
: 这题其实我觉得和很久之前讨论的那个给定a[i],每个a[i]代表一个高度为a[i]的木板
: ,问最多能装多少水的题很像。思路就是先从a[0]开始找一个降序的序列作为start
: point的candidates,很容易证明不在这个序列中的点不可能得到最优解:加入某个a[k
: ]不在这个序列中,那就存在a[i] <= a[k], i < k。假如存在j,使a[k] < a[j],那必
: 然有a[i] < a[j],而j-k < j-i,所以a[k]就不可能是最优解的起点。
: 于是我们只要尝试这个序列中的所有点c[i],假设每个c[i]对应的最优解的end point
: 是d[i],很容易看出d[i]是一个非降的序列,所以可以从数组c的末尾开始向前循环,j
: 初始值是n-1,对于每一个c[i],j向前移动到合适的位置,根据d[i]的单调性,j是可
: 以不回退的,这样总共的复杂度就是O(n)。
: 惟一的concern是,如果是递减的序列,最大的j-i似乎是-1,如果这个也要考虑的话要

avatar
p*u
21
恳求木桶原题。

【在 d*******l 的大作中提到】
: 差不多,你居然还记得。。
: 当时好像没有最后的定论,但我记得我最后想到的方法和这题的差不多,我是只考虑一
: 边的,一个i一个j,开始在两端。从a[0]开始只考虑递增的序列,原因和这题差不多,
: 然后对于每个a[i],j也从会往前退到第一个a[j] > a[i]的地方,并不断更新最大值,
: 然后对于下一个a[i],j可以不回头的继续回退,直到i,j相遇。其实跟你说的每次矮
: 的那边缩进好像效果是一样的。有点区别是那道题在两边缩进的时候每一步都要去试着
: 更新最大值,因为那个要求的是容量,和距离以及a[i]的值都有关系,所以每个i,j都
: 有可能是最优解。那题是可以直接从两边扫,但这题没法直接从两边扫,所以只能先把
: 递减的序列求出来,然后再从同一边扫。

avatar
g*0
24
啊, 不好意思搞错了。谢谢。

【在 g***s 的大作中提到】
: no.
: Http://www.mitbbs.com/article_t0/JobHunting/31816659.html
: 27&31&37 lou gave the correct answers & codes. similar idea.

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。