LWC 51:683. K Empty Slots

LWC 51:683. K Empty Slots

传送门:683. K Empty Slots

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

题意:

题目要求满足开花的两个slot之间的间隙恰好为k个的天数。

很暴力,遍历每个位置i,因为在位置i的左侧一定都是开花的,而在位置i的右侧则都是还没开过的花。所以在左侧的位置中,找到两个相邻位置之差为k个即可,为了快速比较相邻slot之间的间隙,i在不断累加的同时,始终保持i左侧位置的有序性,在插入的同时,去比较它的左侧位置,和右侧位置,看是否符合间隙之差为k+1。

当然上述操作需要维护位置的有序性,于是采用了插入排序算法,并且输出插入对应的位置。这样就能方便的找寻当前位置的左侧位置和右侧位置。

代码如下:

    public int kEmptySlots(int[] flowers, int k) {
        int n = flowers.length;
        if (n == 1 && k == 0) return 1;
        sort = new int[n + 16];
        for (int i = 0; i < n; ++i) {
            int index = add(flowers[i]);
            int min = index - 1 < 0 ? -11111111 : sort[index - 1];
            int max = index + 1 >= tot ? -11111111 : sort[index + 1];
            if (valid(flowers[i], k, min, max)) return i + 1;
        }
        return -1;
    }

    boolean valid(int x, int k, int min, int max) {
        if (max - x == k + 1) return true;
        if (x - min == k + 1) return true;
        return false;
    }

    int[] sort;
    int tot = 0;
    public int add(int x) {
        int j = 0;
        while (j < tot && sort[j] < x) {
            ++j;
        }
        for (int i = tot - 1; i >= j; --i) {
            sort[i + 1] = sort[i];
        }
        sort[j] = x;
        tot++;
        return j;
    }

当然,你也可以使用JAVA自带的数据结构,TreeSet来实现,代码精简很多。

代码如下:

    public int kEmptySlots(int[] flowers, int k) {
        int n = flowers.length;
        if (n == 1 && k == 0) return 1;
        TreeSet<Integer> sort = new TreeSet<>();
        for (int i = 0; i < n; ++i) {
            sort.add(flowers[i]);
            Integer min = sort.lower(flowers[i]);
            Integer max = sort.higher(flowers[i]);
            int mi = min == null ? -1111111 : min;
            int ma = max == null ? -1111111 : max;
            if (valid(flowers[i], k, mi, ma)) return i + 1;
        }
        return -1;
    }

    boolean valid(int x, int k, int min, int max) {
        if (max - x == k + 1) return true;
        if (x - min == k + 1) return true;
        return false;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[LeetCode]Degree of an Array 数组的度 [LeetCode]Degree of an Array 数组的度

链接:https://leetcode.com/problems/degree-of-an-array/description/ 难度:Easy 题目:69...

852
来自专栏LeetCode

LeetCode <Stack>84&85. Maximal Rectangle&Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the ...

1185
来自专栏King_3的技术专栏

leetcode-605-Can Place Flowers

883
来自专栏技术碎碎念

dom4j 使用总结

dom4j是一个Java的XML API,类似于jdom,用来读写XML文件 dom4j的使用方法简单总结来说如下: ①可以创建一个新的xml文件 ②利用SAX...

3458
来自专栏数据结构与算法

1102 A-B数对

题目描述 出题是一件痛苦的事情! 题目看多了也有审美疲劳,于是我舍弃了大家所熟悉的A+B Problem,改用A-B了哈哈! 好吧,题目是这样的:给出一串数以及...

34213
来自专栏机器学习实践二三事

Leetcode之-题38

题目 Count and Say The count-and-say sequence is the sequence of integers beg...

1899
来自专栏Bingo的深度学习杂货店

Q101 Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric aroun...

3158
来自专栏desperate633

LintCode 分割回文串题目分析代码

首先为了分割出回文串,我们首先要写出判断回文串的方法,这里使用动态规划来判断回文串,而且可以存储子串的回文串的情况。 isPalindrome[i][j]:表...

392
来自专栏落影的专栏

程序员进阶之算法练习(三十五)LeetCode专场

LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的边...

44316
来自专栏顶级程序员

判断链表是否有环

判断一个单向链表是否有环。(指向表头结点的指针为head) 方法一: (1)用两个指针p1和p2分别指向表头结点,即p1=p2=head (2)p1和p2分别...

4467

扫码关注云+社区