Leetcode:K Empty Slots

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

老方法,树形数组
以下代码只是思路,不是答案,答案还要处理输入:

#include <stdio.h>

int lowbit(int x);
int kEmptySlots(int* flowers, int flowersSize, int k); 
void insert(int i,int x,int *c);
int getsum(int i,int *c);

int main(void)
{
    int flowers[4]={1,2,3,4};
    printf("%d",kEmptySlots(flowers,4,1)); 
    return 0;
}

int kEmptySlots(int* flowers, int flowersSize, int k)
{
    int trarray[10]={0};
    int base[4]={0};
    for(int i=0;i<flowersSize;i++)
    {
        insert(flowers[i],1,trarray);
        base[i]=getsum(flowers[i],trarray);
    }
    for(int j=0;j+k+1<flowersSize;j++)
    {
        if(base[j+k+1]-base[j]==k)
        {
            //printf("%d",j+k+1);
            return j+k+1;
        }
    }
    return -1;
}

int lowbit(int x) //定义一个Lowbit函数,返回参数转为二进制后,最后一个1的位置所代表的数值.
{
    return x&(-x);
}

void insert(int i,int x,int *c)
{
    while(i<=10)  //维护c数组
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}
int getsum(int i,int *c) //比i小的数
{
    int sum=0;
    while(i>0)
    {
        sum+=c[i];
        i-=lowbit(i);
    } 
    return sum;
}

发表评论