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
|
|
