java treeset 红黑树_红黑树的Java实现TreeSet及相关LeetCode题目_微策略中国的博客-程序员宅基地

技术标签: java treeset 红黑树  

红黑树是一种自平衡的二叉排序树,实现原理参见 教你透彻了解红黑树

Java 中的 TreeSet 使用红黑树实现。提供了一些比较实用的方法:

add(E e)

contains(Object o)

first()

Returns the first (lowest) element currently in this set. 返回最小值

last()

Returns the last (highest) element currently in this set. 返回最大值

higher(E e)

Returns the least element in this set strictly greater than the given element, or null if there is no such element. 返回大于e的元素

ceiling(E e)

Returns the least element in this set greater than or equal to the given element, or null if there is no such element. 返回大于或者等于e的元素

tailSet(E fromElement)

Returns a view of the portion of this set whose elements are greater than or equal to fromElement. 返回大于或者等于e的所有元素

lower(E e)

Returns the greatest element in this set strictly less than the given element, or null if there is no such element. 返回小于e的元素

floor(E e)

Returns the greatest element in this set less than or equal to the given element, or null if there is no such element. 返回小于或者等于e的元素

headSet(E toElement)

Returns a view of the portion of this set whose elements are strictly less than toElement. 返回小于e的所有元素

LeetCode题目:683 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

class Solution {

public int kEmptySlots(int[] flowers, int k) {

// 使用红黑树,查询效率 O(logN)

TreeSet set = new TreeSet<>();

for(int i = 0; i < flowers.length; i++) {

// 找到离该花最近的两个花

Integer lower = set.lower(flowers[i]);

Integer higher = set.higher(flowers[i]);

set.add(flowers[i]);

if(lower != null && (flowers[i] - lower - 1) == k) return i + 1;

if(higher != null && (higher - flowers[i] - 1) == k) return i + 1;

}

return -1;

}

}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_34975022/article/details/114210860

智能推荐

5G时代服务器如何变化_leo12036okokok的博客-程序员宅基地

随着5G离我们越来越近,生活即将变得无所不能,但是服务器我们生活的任何设备或软件都要运行在服务器端,不可能我们安装个软件就能使用了,厂商和服务商所有的服务端程序所运行的服务器在5G时代下将变得不同寻常。5G的百兆传输速率、1ms延时以及每平方公里1000000的连接数,使得终端需要更快速的数据处理能力,5G时代的服务器凭借着低延时、低成本优势,可以说,5G给服务器市场带来了新生机。...

vue3+ts 开发系统 -- 评论列表_Forina_Han的博客-程序员宅基地

写评论组件,希望实现失焦时评论回复框折叠如图所示问题:如何使得Comment组件失焦时,回复面板折叠?监听textarea的blur,在点击提交按钮时,会直接执行面板折叠操作,从而导致未执行提交评论方法。监听外部div的blur事件。div 无focus,blur 事件,查找了下资料,提到,设置tabIndex 属性为0,css中outline为none,tabIndex为tab键聚焦顺序,默认值为-1,即无聚焦事件。详情参考MDN tabIndex。但回复面板内部有输入框,当内部输入框聚焦时将.

MySQL数据库之SQL入门_Mekeater的博客-程序员宅基地_sql数据库入门

MySQL数据库之SQL入门前言本文以MySQL数据库为例,系统讲解SQL的基本操作。一、数据库的基本概念数据库的英文单词: DataBase 简称 : DB数据库是用于存储和管理数据的仓库。数据库的特点:1. 持久化存储数据的。其实数据库就是一个文件系统2. 方便存储和管理数据3. 使用了统一的方式操作数据库 – SQL常见的数据库软件二、MySQL数据库软件1. MySQL安装软件下载链接:https://pan.baidu.com/s/1RS3uBXJiznAIdJC5

Unity 获得视频的某一帧,生成缩略图_weixin_33856370的博客-程序员宅基地

Unity 并无直接获取视频某一帧图像的API,所以想要生成缩略图就要自己写方法了,图片和视频都可以用这种方式生成缩略图,另,转载请标明出处,谢谢。 1 using System.Collections; 2 using System.Collections.Generic; 3 using UnityEngine; 4 using UnityEngine.Video;...

oracle概念和术语_cunxiyuan108的博客-程序员宅基地

<br />Oracle数据库系统是一个复杂的软件系统。如果不了解其内部的结构原理及关系,就不可能设计和编写出高质量的应用软件系统,也不可能管理好一个复杂的应用系统。为了给以后章节的打好基础,本章简要给出 ORACLE 8 /ORACLE8i数据库系统结构的描述。 <br /><br />§2.1  术语 <br /><br />l 数据库块(BLOCK) <br /><br />ORACLE 数据库中的最小存储和处理单位,包含块本身的头信息数据或PL/SQL代码。 <br />ORACLE 块的大小是可以

Windows下编译 ImageMagick 的php API_afarliu的博客-程序员宅基地

转自:http://blog.csdn.net/golden_chan/article/details/5712266首先,需要的软件包有:PHP5.2.5 源码包[http://www.php.net/downloads.php]bindlib_w32 [http://www.php.net/extra/bindlib_w32.zip]win32build [http://w

随便推点

Android RecyclerView 报错:java.lang.IllegalStateException: The specified child already has a..._瞌睡先生想睡觉的博客-程序员宅基地

报错信息: java.lang.IllegalStateException: The specified child already has a parent. You must call removeView() on the child's parent first.解决办法:由原来 @Override public MyViewHolder onCreateViewHolder(V

java telnet tab指令_Java实现Telnet 客户端代码教程(一)_weixin_39724793的博客-程序员宅基地

时间:2018-12-01概述:Telnet 客户端Java实现Telnet 客户端,我们可以使用一些Telnet 客户端软件来连接开通Telnet 服务的主机,本例通过编程实现了一个Telnet 客户端工具。运行程序,就可在客户端登录指定主机,运行程序后产生的界面如下图所示。Java实现Telnet 客户端运行界面实现思路:Telnet 类继承了Applet 类,在init()中实现的是此App...

分布式锁的三种实现方式_谈胖胖的博客-程序员宅基地_分布式锁怎么实现

在很多场景中,我们为了保证数据的最终一致性,需要很多的技术方案来支持,比如分布式事务、分布式锁等。有的时候,我们需要保证一个方法在同一时间内只能被同一个线程执行。在单机环境中,Java中其实提供了很多并发处理相关的API,但是这些API在分布式场景中就无能为力了。也就是说单纯的Java Api并不能提供分布式锁的能力。所以针对分布式锁的实现目前有多种方案:分布式锁一般有三种实现方式:1.数据库...

电脑如何炫酷下拉关机_小屁孩大帅-杨一凡的博客-程序员宅基地_下拉关机

第一步:在桌面鼠标右键新建一个“文本文件” 第二步:在文件中输入“SlideToShutDown”,然后点击文件进行保存。 第三步:修改文件后缀改“TXT”为“bat”。 第四步:双击文件进行运行即可炫酷下拉关机。 END 注意事项 第二步中“SlideToShutDown”必须区分大小写。 ...

HBase RowKey与索引设计_weixin_30763397的博客-程序员宅基地

1.HBase的存储形式hbase的内部使用KeyValue的形式存储,其key时rowKey:family:column:logTime,value是其存储的内容。其在region内大多以升序的形式排列,唯一的时logTime是以降序的形式进行排列。所以,rowKey里越靠近左边的信息越容易被检索到。其设计时,要考虑把重要的信息放左边,不重要的信息放到右边。这样可以提高查询数据的速...

推荐文章

热门文章

相关标签