j***n
发帖数: 301 | 1 Given an integer array A[], what preprocessing you need to do so that when g
iven i and j such that i <= j, you can tell in O(1) time the number of eleme
nts in the array having values between and including i and j.
A graph is given. You need to design a data structure with minimum space com
plexity such that it does the follows
--> Finds whether nodes u and v have a path in between them in O(1) time.
--> Finds whether there is a path of length l between u and v in O(k) time.
What does the follo | p******n
发帖数: 32 | 2 第一题直接把数组排序，另外用一个hash table记录每个value，e.g.,i,j在排序后数
组中的索
引。 | r*d
发帖数: 896 | 3 程序是统计的n的二进制表示中1的个数。
g
eleme
com
time.
【在 j***n 的大作中提到】
: Given an integer array A[], what preprocessing you need to do so that when g
: iven i and j such that i <= j, you can tell in O(1) time the number of eleme
: nts in the array having values between and including i and j.
: A graph is given. You need to design a data structure with minimum space com
: plexity such that it does the follows
: --> Finds whether nodes u and v have a path in between them in O(1) time.
: --> Finds whether there is a path of length l between u and v in O(k) time.
: What does the follo
| n*******s
发帖数: 482 | 4 (1) Using counting sort, the helper array C[]. C[x] is the number of
elements in original array that smaller than or equal to x. So the number in
range (i,j] should be C[j] - C[i]. If the range is [i,j] , just do a small
modification. | s*******s
发帖数: 46 | 5
g
eleme
先sort A[], 然后得到一个数组B[k],表示A[]
然后答案就是B[t2]-B[t1] (A[t1]=i, A[t2]=j)
com
time.
what is k?另外，第二个是否需要最短距离还是任意距离？
使用一个dp算法可以得到图中任意两点最短距离。
然后你可以使用linkedlist来表示这个sparse矩阵。
【在 j***n 的大作中提到】
: Given an integer array A[], what preprocessing you need to do so that when g
: iven i and j such that i <= j, you can tell in O(1) time the number of eleme
: nts in the array having values between and including i and j.
: A graph is given. You need to design a data structure with minimum space com
: plexity such that it does the follows
: --> Finds whether nodes u and v have a path in between them in O(1) time.
: --> Finds whether there is a path of length l between u and v in O(k) time.
: What does the follo
| s*********t
发帖数: 1663 | 6 t1,t2是怎么出来的？如果二分查找已经不能O(1)了
i和j也未必是A里的数
【在 s*******s 的大作中提到】
:
: g
: eleme
: 先sort A[], 然后得到一个数组B[k],表示A[]: 然后答案就是B[t2]-B[t1] (A[t1]=i, A[t2]=j)
: com
: time.
: what is k?另外，第二个是否需要最短距离还是任意距离？
: 使用一个dp算法可以得到图中任意两点最短距离。
: 然后你可以使用linkedlist来表示这个sparse矩阵。
|
|
