B*****t 发帖数: 335 | 1 Thanks!
Given an array A which holds a permutation of 1,2,...,n. A sub-block A[i..j]
of an array A is called a valid block if all the numbers appearing in A[i..
j] are consecutive numbers (may not be in order).
Given an array A= [ 7 3 4 1 2 6 5 8] the valid blocks are [3 4], [1,2], [6,5
], [3 4 1 2], [3 4 1 2 6 5], [7 3 4 1 2 6 5], [7 3 4 1 2 6 5 8]. Give an O(
n log n) algorithm to count the number of valid blocks. | g*******y 发帖数: 1930 | 2 这题不错。krone有不错的解法,能做到平均性能nlogn | B*****t 发帖数: 335 | 3 有没有link?
【在 g*******y 的大作中提到】 : 这题不错。krone有不错的解法,能做到平均性能nlogn
| U********o 发帖数: 132 | 4 ss
这题不错。krone有不错的解法,能做到平均性能nlogn
【在 g*******y 的大作中提到】 : 这题不错。krone有不错的解法,能做到平均性能nlogn
| j********9 发帖数: 603 | 5 DP问题吧应该算是:
我是这样想的:
每个数都看成一个valid block,每个valid block都有最大值和最小值,每个block都
用最大值和最小值来表示,如果一个block里就有一个数,那最大最小都是他自己。
接下来就比价相邻的两两block,如果两个block的最大值和最小值,或者最小值和最大
值相差1或者是0,那么这两个block就可以jion一个新的block,计数器++。这样下去,
block的长度逐渐增加,如果没有新的可以join的blocks,最后再加1(整个这个array
作为最大的block)
不知道这样想对不对,请大虾们指教。 | k***e 发帖数: 556 | 6 哈哈 你直接贴出来好了
不过我估计没几个人有耐心看完。
we first extend the problem to numbers where integers are allowed, however,
they may note be continuous, for example, 1 5 4 3, and 2 is missing. We also
need to use minimum (maximum) range query frequently, i.e, query min n[i:j]
for any interval. Basically after spending linear time in preprocessing, we
can finish it in time O(1).
Suppose n[i:j] is the interval we want to cope with. Then min, max stands
for
the minimum and maximum of n[i:j]. We can thus divide n[i:j]
【在 g*******y 的大作中提到】 : 这题不错。krone有不错的解法,能做到平均性能nlogn
| m*****f 发帖数: 1243 | 7 这道题作为面试题有些太难了...
我就没耐心看完...
,
also
]
we
【在 k***e 的大作中提到】 : 哈哈 你直接贴出来好了 : 不过我估计没几个人有耐心看完。 : we first extend the problem to numbers where integers are allowed, however, : they may note be continuous, for example, 1 5 4 3, and 2 is missing. We also : need to use minimum (maximum) range query frequently, i.e, query min n[i:j] : for any interval. Basically after spending linear time in preprocessing, we : can finish it in time O(1). : Suppose n[i:j] is the interval we want to cope with. Then min, max stands : for : the minimum and maximum of n[i:j]. We can thus divide n[i:j]
| g*******y 发帖数: 1930 | 8 赞一个哈,我就是想让原作者亲自来贴
,
also
]
we
【在 k***e 的大作中提到】 : 哈哈 你直接贴出来好了 : 不过我估计没几个人有耐心看完。 : we first extend the problem to numbers where integers are allowed, however, : they may note be continuous, for example, 1 5 4 3, and 2 is missing. We also : need to use minimum (maximum) range query frequently, i.e, query min n[i:j] : for any interval. Basically after spending linear time in preprocessing, we : can finish it in time O(1). : Suppose n[i:j] is the interval we want to cope with. Then min, max stands : for : the minimum and maximum of n[i:j]. We can thus divide n[i:j]
| B*****t 发帖数: 335 | 9 Thanks for your method. However,I cannot catch your point and doubt its
correctness. Especially how this equation comes from
T(n[i:j]) = T(a) + T(b) + T(c) + c(j - i + 1)
and the explanation after that. Could you make it clear? or show some code
or pseudo-code? Thanks.
,
also
]
we
【在 k***e 的大作中提到】 : 哈哈 你直接贴出来好了 : 不过我估计没几个人有耐心看完。 : we first extend the problem to numbers where integers are allowed, however, : they may note be continuous, for example, 1 5 4 3, and 2 is missing. We also : need to use minimum (maximum) range query frequently, i.e, query min n[i:j] : for any interval. Basically after spending linear time in preprocessing, we : can finish it in time O(1). : Suppose n[i:j] is the interval we want to cope with. Then min, max stands : for : the minimum and maximum of n[i:j]. We can thus divide n[i:j]
| x***y 发帖数: 633 | 10 The first 3 items are for case 4, and the last one is for case 2,3, which
he proved later is linear....
【在 B*****t 的大作中提到】 : Thanks for your method. However,I cannot catch your point and doubt its : correctness. Especially how this equation comes from : T(n[i:j]) = T(a) + T(b) + T(c) + c(j - i + 1) : and the explanation after that. Could you make it clear? or show some code : or pseudo-code? Thanks. : : , : also : ] : we
| g*****u 发帖数: 298 | 11 哈,你换了头像我都没认出来。。。
顺便问一下你们面google都是software engineer还是test engineer呢?
【在 m*****f 的大作中提到】 : 这道题作为面试题有些太难了... : 我就没耐心看完... : : , : also : ] : we
|
|