题目大意:有n个花盆,第i天,第flowers[i]个花盆的花会开。问是否存在一天,两朵花之间有k个空花盆。
Problem:
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].
Idea:
BST/Buckets
Solution 2: BST
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Runtime: 228 ms class Solution { public: int kEmptySlots(vector<int>& flowers, int k) { int n = flowers.size(); if (n == 0 || k >= n) return -1; set<int> xs; for (int i = 0; i < n; ++i) { int x = flowers[i]; auto r = xs.insert(x).first; auto l = r; if (++r != xs.end() && *r == x + k + 1) return i + 1; if (l != xs.begin() && *(--l) == x - k - 1) return i + 1; } return -1; } }; |
Solution 3: Buckets
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua // Runtime: 196 ms (better than 94%) class Solution { public: int kEmptySlots(vector<int>& flowers, int k) { int n = flowers.size(); if (n == 0 || k >= n) return -1; ++k; int bs = (n + k - 1) / k; vector<int> lows(bs, INT_MAX); vector<int> highs(bs, INT_MIN); for (int i = 0; i < n; ++i) { int x = flowers[i]; int p = x / k; if (x < lows[p]) { lows[p] = x; if (p > 0 && highs[p - 1] == x - k) return i + 1; } if (x > highs[p]) { highs[p] = x; if (p < bs - 1 && lows[p + 1] == x + k) return i + 1; } } return -1; } }; |
Solution 1: TLE with latest test cases
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// Author: Huahua // Runtime: 192 ms (better than 97.85%) class Solution { public: int kEmptySlots(vector<int>& flowers, int k) { int n = flowers.size(); if (n == 0 || k >= n) return -1; std::unique_ptr<char[]> f(new char[n+1]); memset(f.get(), 0, (n + 1)*sizeof(char)); for (int i = 0; i < n; ++i) if (IsValid(flowers[i], k, n, f.get())) return i + 1; return -1; } private: bool IsValid(int x, int k, int n, char* f) { f[x] = 1; if (x + k + 1 <= n && f[x + k + 1]) { bool valid = true; for (int i = 1; i <= k; ++i) if (f[x + i]) { valid = false; break; } if (valid) return true; } if (x - k - 1 > 0 && f[x - k - 1]) { for (int i = 1; i <= k; ++i) if (f[x - i]) return false; return true; } return false; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// Author: Huahua // Runtime: 17 ms class Solution { public int kEmptySlots(int[] flowers, int k) { int n = flowers.length; if (n == 0 || k >= n) return -1; int[] f = new int[n + 1]; for (int i = 0; i < n; ++i) if (IsValid(flowers[i], k, n, f)) return i + 1; return -1; } private boolean IsValid(int x, int k, int n, int[] f) { f[x] = 1; if (x + k + 1 <= n && f[x + k + 1] == 1) { boolean valid = true; for (int i = 1; i <= k; ++i) if (f[x + i] == 1) { valid = false; break; } if (valid) return true; } if (x - k - 1 > 0 && f[x - k - 1] == 1) { for (int i = 1; i <= k; ++i) if (f[x - i] == 1) return false; return true; } return false; } } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
""" Author: Huahua Runtime: 398 ms """ class Solution: def kEmptySlots(self, flowers, k): n = len(flowers) f = [0] * (n + 1) i = 0 def isValid(x, k, n, f): f[x] = 1 if x + k + 1 <= n and f[x + k + 1] == 1: valid = True for i in range(k): if f[x + i + 1] == 1: valid = False break if valid: return True if x - k - 1 > 0 and f[x - k - 1] == 1: for i in range(k): if f[x - i - 1] == 1: return False return True return False for x in flowers: i += 1 if isValid(x, k, n, f): return i return -1 |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment