l*******l
发帖数: 248 | 1 1.Suppose you have the following code:
void function() {
int * =new(a);
int *= new(b);
a=b;
delete(a);
delete(b);
return(a);
}
What are all the problems with this code? (There might be more than one)
2.Let a[n] be a sorted array of integers. Let b be an integer.
Write an (efficient) algorithm which checks whether there are indices i,j
such that a[i]+a[j]=b .
3.Write an algorithm which outputs the set of all subsets of the list {1,2,.
...,n}. How many subsets will there be?
4.Write an algorithm implementing search on a lexicographically ordered
array of strings. | t*******i
发帖数: 32 | 2 1 a) = has the shallow copy , delete a might delete pointer inside b,
b) return non-existing object
c) return object to void f
2. set up two indexes, one moves forward, one moves backward | l*******l
发帖数: 248 | 3 这个是O（n^2）?
【在 t*******i 的大作中提到】
: 1 a) = has the shallow copy , delete a might delete pointer inside b,
: b) return non-existing object
: c) return object to void f
: 2. set up two indexes, one moves forward, one moves backward
| n******m
发帖数: 169 | 4 他的意思是这样的：
Let c[i]=b-a[i];
Suppose a[i] is in increasing order,
c[i] then, is in decreasing order.
all you need now is to find a same element that appears in a[] and c[]. for
example if a[j]=c[k], then, this means a[j]+a[k]=b.
To find this same element, you need linear time. (think about how you merge
2 sorted arrays in mergesort). the way is to initial a pointer 'ap' to a[0]
and a pointer 'cp' to c[n], then move the pointers.
【在 l*******l 的大作中提到】
: 这个是O（n^2）?
| l*******l
发帖数: 248 | 5 谢谢啦！！这样的话是O（n）?
for
merge
]
【在 n******m 的大作中提到】
: 他的意思是这样的：
: Let c[i]=b-a[i];
: Suppose a[i] is in increasing order,
: c[i] then, is in decreasing order.
: all you need now is to find a same element that appears in a[] and c[]. for
: example if a[j]=c[k], then, this means a[j]+a[k]=b.
: To find this same element, you need linear time. (think about how you merge
: 2 sorted arrays in mergesort). the way is to initial a pointer 'ap' to a[0]
: and a pointer 'cp' to c[n], then move the pointers.
| m*********g
发帖数: 646 | 6 I think it is 0(N^2)
【在 l*******l 的大作中提到】
: 谢谢啦！！这样的话是O（n）?
:
: for
: merge
: ]
| l*******l
发帖数: 248 | 7 agreed, does anyone have a more efficient way?
【在 m*********g 的大作中提到】
: I think it is 0(N^2)
| t*******i
发帖数: 32 | 8 come on, there is one way of O(N)
suppose array is increasing ,
one index from start, another is from end, end pointer search backward, once
end pointer cannot find b-a[begin], then keep going , until a[end]
begin] ,
then begin move forward, and end continue search, since array is increasing,
the element must be ahead the current position of end ,
and then keep going like that ... once end <= begin , then you can say, i
cannot find the equality ....
this algorithm is of O(N), since every element is visited only once .... |
| r*******y
发帖数: 1081 | 9 #2, how to move forward the first index and backward the second index ?
for example if a[1] + a[n] > sum and i = 1, j = n, then only decrease j
or both increase i and decrease j ?
I have an idea, say a={a[1], a[2], ..., a[n]} which is increasing
construct b = {sum - a[n], sum - a[n - 1], ..., sum- a[1]}
which is also increasing.
then in O(n) to check whether any a[i] = b[j] and if so a[i] + a[j] = sum
【在 t*******i 的大作中提到】
: 1 a) = has the shallow copy , delete a might delete pointer inside b,
: b) return non-existing object
: c) return object to void f
: 2. set up two indexes, one moves forward, one moves backward
| z****g
发帖数: 1978 | 10 可以直接suppose array is increasing?你这可直接就把nlog(n)给扔了... | | | z****g
发帖数: 1978 | 11 and memory leak of a...
【在 t*******i 的大作中提到】
: 1 a) = has the shallow copy , delete a might delete pointer inside b,
: b) return non-existing object
: c) return object to void f
: 2. set up two indexes, one moves forward, one moves backward
| z****g
发帖数: 1978 | 12 2. 如果array是没有sort的，最好的应该是nlog(n)了。
3. n位2进制计数器累加
4. std::set.find() | z****s
发帖数: 532 | 13 这个是标准答案
once
increasing,
【在 t*******i 的大作中提到】
: come on, there is one way of O(N)
: suppose array is increasing ,
: one index from start, another is from end, end pointer search backward, once
: end pointer cannot find b-a[begin], then keep going , until a[end]: begin] ,
: then begin move forward, and end continue search, since array is increasing,
: the element must be ahead the current position of end ,
: and then keep going like that ... once end <= begin , then you can say, i
: cannot find the equality ....
: this algorithm is of O(N), since every element is visited only once ....
| l*******l
发帖数: 248 | 14 如果是sorted 的array，很容易check是increasing还是decreasing的吧，看看前两个
element谁打就好了吧
可以讲讲如果没有sort过，这道题怎么做吗？为什么是nlog(n)？
【在 z****g 的大作中提到】
: 可以直接suppose array is increasing?你这可直接就把nlog(n)给扔了...
| z****g
发帖数: 1978 | 15 ...先sort一次呗，你不觉得nlog(n)眼熟么？
【在 l*******l 的大作中提到】
: 如果是sorted 的array，很容易check是increasing还是decreasing的吧，看看前两个
: element谁打就好了吧
: 可以讲讲如果没有sort过，这道题怎么做吗？为什么是nlog(n)？
| l*******l
发帖数: 248 | 16 我觉得眼熟。。。
就是不确定 n+nlogn = nlogn
【在 z****g 的大作中提到】
: ...先sort一次呗，你不觉得nlog(n)眼熟么？
| z****g
发帖数: 1978 | 17 复杂度里不存在+加号吧...两个O加还是O，如果是O和o，直接取O了
【在 l*******l 的大作中提到】
: 我觉得眼熟。。。
: 就是不确定 n+nlogn = nlogn
| a********e
发帖数: 508 | 18 第一题是C++ code吗？怎么完全不认识？
第三题麻烦的地方是number of subsets会explode。生成2^n的vector
或对2^n循环肯定不行。估计要定义一个size为n的bool array
第四题直接binary search就行了
【在 l*******l 的大作中提到】
: 1.Suppose you have the following code:
: void function() {
: int * =new(a);
: int *= new(b);
: a=b;
: delete(a);
: delete(b);
: return(a);
: }
: What are all the problems with this code? (There might be more than one)
|
|
