683. K Empty Slots解题报告

Description:

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:

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

Link:

https://leetcode.com/problems/k-empty-slots/description/

解题方法：

这道题是求在某一天（某次开花后）是否有一个以左右两朵花为边界，中间部分不开花，并且中间部分长度为k的区域。

暴力破解就是按照数组顺序每次迭代开一朵花，记录开花位置，每次迭代都扫一遍数组看看有没有符合以上的一段区域。这样的时间复杂度是O(N^2);

假设把整个数组当成一个大区域（0到size - 1），以-1和size为边界；把每次开花都当成用刀切割当前区域，如果在某次切割后（某日开花后）能出现符合上面条件的区域，那么就找到了这样一个天数。
如果这样理解，这道题就可以转化为二叉树的题来考虑，如果这道题只是求到这么一个天数，用DFS就可以做出来。如果需要找到最早的天数，用BFS也可以做出来。

Tips:

这道题在LeetCode上是要找到最短天数，所以用BFS。

Time Complexity：

完整代码：

// DFS:
int kEmptySlots(vector<int>& flowers, int k) {
    int size = flowers.size();
    if(size < 2 || size - 2 < k)
        return -1;
    int result = -1;
    helper(flowers, k, -1, -1, size, result);
    return result;
}
void helper(vector<int>& flowers, int k, int day, int lB, int rB, int& result) {
    if(rB - lB < k + 1 || result != -1 || day >= (int) flowers.size()) {
        return;
    }
    if(rB - lB == k + 1 && lB != -1 && rB != (int) flowers.size()) {
        result = day + 1;
        return;
    }
    int curr = flowers[day + 1] - 1;
    if(curr <= lB || curr >= rB)
        helper(flowers, k, day + 1, lB, rB, result);
    else {
        helper(flowers, k, day + 1, lB, curr, result);
        helper(flowers, k, day + 1, curr, rB, result);
    }
}

// BFS(AC方法):
int kEmptySlots(vector<int>& flowers, int k) {
    int size = flowers.size();
    if(size < 2 || size - 2 < k || k < 0)
        return -1;
    int day = 0;
    queue<pair<int, int>> Q;
    Q.push(pair<int, int> (-1, size));
    while(!Q.empty()) {
        int len = Q.size();
        while(len-- > 0) {
            int l = Q.front().first, r = Q.front().second;
            Q.pop();
            if(r - l < k + 1)
                continue;
            if(r - l == k + 1 && l != -1 && r != size)
                return day;
            int curr = flowers[day] - 1;
            if(curr <= l || curr >= r)
                Q.push(pair<int, int> (l, r));
            else {
                Q.push(pair<int, int> (l, curr));
                Q.push(pair<int, int> (curr, r));
            }

        }
        ++day;
    }
    return -1;
}