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 条评论
登录 后参与评论

相关文章

来自专栏赵俊的Java专栏

恢复旋转排序数组

1092
来自专栏nnngu

数据结构09 哈夫曼树

这一篇要总结的是树中的哈夫曼树(Huffman Tree),我想从以下几点对其进行总结: 1、什么是哈夫曼树 2、如何构建哈夫曼树 3、哈夫曼编码 4、代码实现...

2637
来自专栏算法修养

PAT 甲级 1027 Colors in Mars

1027. Colors in Mars (20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B ...

2746
来自专栏计算机视觉与深度学习基础

Leetcode 200 Number of Islands 并查集

Given a 2d grid map of '1's (land) and '0's (water), count the number of islan...

1787
来自专栏大闲人柴毛毛

动态规划法(五)——多段图问题

问题描述 给定一个多段图,求出多段图中的最短路径和最短路径长度。 什么是多段图? 多段图是一个有向、无环、带权 图。 有且仅有一个起始结点(原点source...

3394
来自专栏书山有路勤为径

二叉树层次遍历

二叉树层次遍历,又称为宽度优先搜索,按树的层次依次访问树的结点。层次遍历使用队列对遍历节点进行 存储,先进入队列的结点, 优先遍历拓展其左孩子与 右孩子。

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

codevs 1814 最长链

1814 最长链 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题目描述 Description 现给出...

2675
来自专栏desperate633

LeetCode 121. Best Time to Buy and Sell Stock题目Solution

假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。 样例 给出一...

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

3139 栈练习3

3139 栈练习3  时间限制: 2 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Descriptio...

2679
来自专栏决胜机器学习

有趣的算法(八) ——红黑树插入算法

有趣的算法(八)——红黑树插入算法 (原创内容,转载请注明来源,谢谢) 一、概述 红黑树是一种二叉平衡查找树。二叉查找树是二叉树,且树的根节点会比左节点大、比...

3525

扫码关注云+社区