f*********i
发帖数: 197 | 1 Given an array A[i..j] find out maximum j-i such that A[i]
这题我记得很早的时候有讨论过,考古找不到答案,希望有牛人为我再解释下,多谢 |
h*********n
发帖数: 11319 | 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]: 这题我记得很早的时候有讨论过,考古找不到答案,希望有牛人为我再解释下,多谢
|
f****4
发帖数: 1359 | 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]: 这题我记得很早的时候有讨论过,考古找不到答案,希望有牛人为我再解释下,多谢
|
i**********e
发帖数: 1145 | 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.
|
d*******l
发帖数: 338 | 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;
} |
g**********y
发帖数: 14569 | 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) {
|
g**********y
发帖数: 14569 | 7 我觉得不象有O(n)的算法，考虑个极端情况：A是递减数组，意思是不存在那样的j-i。
你要不排序，好象很难排除所有的情况。
期待有人给个巧妙解。
【在 i**********e 的大作中提到】
: 这题没那么简单，给个反例：
: A = { 3, 2, 4, 1 }
: 我暂时想到排序的解法，但是是 O(n log n)，就算有重复的值的也能处理。我也想知
: 道有没有 O(n) 的解。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
i**********e
发帖数: 1145 | 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) {
|
i**********e
发帖数: 1145 | 9 我觉得他的解法是对的，也可以证明是对的。
【在 g**********y 的大作中提到】
: 这个好象有问题，你找了一条包含a0的降链，但是最大路径不一定包含这条链的点。反
: 例应该不难找。
|
i**********e
发帖数: 1145 | 10 递减不是 O(n^2).
A = { 5 4 3 2 1 }
在递减的情况，while loop 里每次最多比较两次。
所以是 2* n. |
|
|
g**********y
发帖数: 14569 | 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 的大作中提到】
: 我觉得他的解法是对的，也可以证明是对的。
|
d*******l
发帖数: 338 | 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的降链，但是最大路径不一定包含这条链的点。反
: 例应该不难找。
|
d*******l
发帖数: 338 | 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--
: ...
: 这样算下来对吗？
|
g**********y
发帖数: 14569 | 14 是我想错了。
【在 d*******l 的大作中提到】
: 这里break之后，就不会j--了，只有i--，只有不满足判断条件才会j--
|
i**********e
发帖数: 1145 | 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--
: ...
: 这样算下来对吗？
|
g**e
发帖数: 6127 | 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，如果这个也要考虑的话要
|
d*******l
发帖数: 338 | 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) 的距离，
: 也就是更加好的答案。利用这方面的想法来理解这题就简单多了。
|
i**********e
发帖数: 1145 | 18 darksteel,
"这题其实我觉得和很久之前讨论的那个给定a[i]，每个a[i]代表一个高度为a[i]的木
板，问最多能装多少水的题很像。"
那题的解法是不是用两个指针（也就是 i 和 j 两个 index），第一个从左到右的方向
，和第二个从右到左的方向缩进？从左到右 和右到左 必须是个递增的序列。每一步首
先看左边 / 右边的柱子哪个比较高，同时更新最大容量值。如果左边柱子高些的话，
就从右到左进行缩进（反之亦然），直到 A[new_j] > A[old_j]，然后再更新最大值。
之后也一样，重新比较左边右边的柱子，再重复移动指针，直到他们两个相遇。
不知道这个理解对不对呢？
【在 d*******l 的大作中提到】
: 握手～～就是这个意思
|
d*******l
发帖数: 338 | 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]，然后再更新最大值。
: 之后也一样，重新比较左边右边的柱子，再重复移动指针，直到他们两个相遇。
: 不知道这个理解对不对呢？
|
x***n
发帖数: 70 | 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，如果这个也要考虑的话要
|
|
|
p*****u
发帖数: 310 | 21 恳求木桶原题。
【在 d*******l 的大作中提到】
: 差不多，你居然还记得。。
: 当时好像没有最后的定论，但我记得我最后想到的方法和这题的差不多，我是只考虑一
: 边的，一个i一个j，开始在两端。从a[0]开始只考虑递增的序列，原因和这题差不多，
: 然后对于每个a[i]，j也从会往前退到第一个a[j] > a[i]的地方，并不断更新最大值，
: 然后对于下一个a[i]，j可以不回头的继续回退，直到i，j相遇。其实跟你说的每次矮
: 的那边缩进好像效果是一样的。有点区别是那道题在两边缩进的时候每一步都要去试着
: 更新最大值，因为那个要求的是容量，和距离以及a[i]的值都有关系，所以每个i，j都
: 有可能是最优解。那题是可以直接从两边扫，但这题没法直接从两边扫，所以只能先把
: 递减的序列求出来，然后再从同一边扫。
|
g******0
发帖数: 221 | |
g***s
发帖数: 3811 | 23 no.
Http://www.mitbbs.com/article_t0/JobHunting/31816659.html
27&31&37 lou gave the correct answers & codes. similar idea.
【在 g******0 的大作中提到】
: 原题好象是这个？
: http://www.mitbbs.com/article/JobHunting/31719089_3.html
|
g******0
发帖数: 221 | 24 啊， 不好意思搞错了。谢谢。
【在 g***s 的大作中提到】
: no.
: Http://www.mitbbs.com/article_t0/JobHunting/31816659.html
: 27&31&37 lou gave the correct answers & codes. similar idea.
|
