题目描述:
There is a garden with N
slots. In each slot, there is a flower. The N
flowers will bloom one by one in N
days. In each day, there will be exactly
one flower blooming and it will be in the status of blooming since then.
Given an array flowers
consists of number from 1
to N
. Each number in the array represents the place where the flower will open in that day.
For example, flowers[i] = x
means that the unique flower that blooms at day i
will be at position x
, where i
and x
will be in the range from 1
to N
.
Also given an integer k
, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k
and these flowers are not blooming.
If there isn't such day, output -1.
Example 1:
Input: flowers: [1,3,2] k: 1 Output: 2 Explanation: In the second day, the first and the third flower have become blooming.
Example 2:
Input: flowers: [1,2,3] k: 1 Output: -1
Note:
- The given array will be in the range [1, 20000].
题目大意:
花园中有N个槽,每次在槽中种一朵花。给定种花的顺序flowers,flowers[i] = x表示第i天,在第x个槽种下一朵花。
另外给定数字k,求flowers中是否存在某一天,满足相隔k距离的两个端点恰好各有一朵花,而这两朵花之间的k个槽都没有花。
解题思路:
树状数组(Fenwick Tree)
树状数组ft[k]存储前k个槽一共有多少朵花,则区间[m, n]的花朵总数 = ft[n] - ft[m - 1]
利用该数据结构,遍历flowers即可求解。
Python代码:
class Solution(object):
def kEmptySlots(self, flowers, k):
"""
:type flowers: List[int]
:type k: int
:rtype: int
"""
maxn = max(flowers)
nums = [0] * (maxn + 1)
ft = FenwickTree(maxn)
for i, v in enumerate(flowers):
ft.add(v, 1)
nums[v] = 1
if v >= k and ft.sum(v) - ft.sum(v - k - 2) == 2 and nums[v - k - 1]:
return i + 1
if v + k + 1<= maxn and ft.sum(v + k + 1) - ft.sum(v - 1) == 2 and nums[v + k + 1]:
return i + 1
return -1
class FenwickTree(object):
def __init__(self, n):
self.n = n
self.sums = [0] * (n + 1)
def add(self, x, val):
while x <= self.n:
self.sums[x] += val
x += self.lowbit(x)
def lowbit(self, x):
return x & -x
def sum(self, x):
res = 0
while x > 0:
res += self.sums[x]
x -= self.lowbit(x)
return res
本文链接:http://bookshadow.com/weblog/2017/09/24/leetcode-k-empty-slots/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。