当前位置:网站首页>Déduisez la question d'aujourd'hui - 729. Mon emploi du temps I
Déduisez la question d'aujourd'hui - 729. Mon emploi du temps I
2022-07-06 02:26:00 【Un jeune combattant】
729. Mon emploi du temps I
Deux points
- Triez d'abord toutes les séquences déjà programmées,Puis traversez l'intervalle à tour de rôle,Regarde dans une section.
left1
,Est - ce plus grand queend
12Et3,5,10Comparer,Il n'y a pas d'intervalle plus grand,Il est temps d'envisager d'insérer.
- Non trouvé:C'est avec le dernier
right1
Comparaison,Regardez la dernière sectionright1Est inférieur à la plage d'insertionstart,Si possible, retournez àture,Sinon, retournez àfalse
12Et le dernier élément15Comparer,Découverte15Est supérieur à12De,Retourfalse.
Et17D'abord.3,7,10Comparer,Les résultats sont plus grands qu'eux,Alors, envisagez de placer,Et puis20Et15Comparaison,Découverte20Plus grand que15,Retourtrue.
- J'ai trouvé le premier
I) Jugement ,Je l'ai trouvé.
end
Plus petit que le plus petitleft1
,Pour pouvoir insérer,Je revienstrue
- Insertion au milieu
Intervalle intermédiaire,Trouverlast La section précédente de pre[left2,right2]
,Siright2Plus grand questart, Il y a intersection ,Retourfalse,Sinon, retournez àtrue.
Juge d'abord,Découverte10==10, Arrête de juger 7,Regarde.7<8Avec intersection,Retourfalse.
Par exemple,[9,10] C'est un bon exemple ,Découverte 10 =- 10, Arrête de juger ,Regarde.9> 8,Retourtrue.
- Code:
List<int[]> data;
public MyCalendar() {
data = new ArrayList<>();
}
public boolean book(int start, int end) {
if (data.size() == 0) {
data.add(new int[]{
start, end});
return true;
}
data.sort(Comparator.comparingInt(o -> o[0]));
int left = 0, right = data.size() - 1;
//Trouver le premierstart >= endIntervalle de
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (data.get(mid)[0] >= end) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
//Je n'ai pas trouvé Comparé au dernier intervalle
if (ans == -1) {
int[] ints = data.get(data.size() - 1);
if (ints[1] > start) {
return false;
}
} else if (ans != 0) {
// Pas la première section , Si c'est le premier intervalle, il peut être inséré directement
int[] pre = data.get(ans - 1);
if (pre[1] > start) {
return false;
}
}
data.add(new int[]{
start, end});
return true;
}
Directement à travers
class MyCalendar {
// Définir unbooked
List<int[]> booked;
public MyCalendar() {
booked = new ArrayList<int[]>();
}
public boolean book(int start, int end) {
for(int[] arr : booked){
int l = arr[0] ,r = arr[1];
//Dans le deuxième cas
if(l < end && start < r){
return false;
}
}
booked.add(new int[]{
start,end});
return true;
}
}
/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */
[s1,e1)Et[s2,e2)
, Pas d'intersection satisfaisantes1>e2
Ous2>e1
, Inversement, cela signifie que les deux se croisent en arrière .
Pensée 3
Changez d'avis , Le concept de chevauchement peut être étendu au concept général d'égalité , C'est - à - dire qu'une fois superposés, les deux éléments sont égaux , Alors c'est simple ,set Spécialement conçu pour le déstockage . AlorsHashSetEtTreeSetAvec lequel?? Tout d'abord,HashSet La dé - duplication est basée sur la valeur de hachage de l'objet , Parce que ce que nous stockons est int[]Type, Nous écrivons le Code en fonction de startEtendPour le créer, Donc leurs valeurs de hachage sont fondamentalement différentes , Ce qui veut dire que même si deux int[] Les valeurs sont exactement les mêmes , Mais les valeurs de hachage sont différentes ,HashSet Et les mettre dans . Parce que nous considérons le chevauchement comme une égalité au sens large , Il est donc nécessaire de définir un comparateur pour les distinguer de l'égalité généralisée ,EtTreeSet Prise en charge des comparateurs personnalisés , Et trier en fonction des valeurs retournées par le Comparateur , Très bien adapté à nos besoins .
class MyCalendar {
//Définir unTreeSet
TreeSet<int[]> calendars;
public MyCalendar() {
calendars = new TreeSet<>((a, b) -> {
if(a[1] <= b[0])
return -1;
else if(a[0] >= b[1])
return 1;
else
return 0;
});
}
public boolean book(int start, int end) {
int[] e = new int[]{
start, end};
return calendars.add(e);
}
}
/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */
Développement
TreeSetIntroduction:
Ordre.,Non reproductible,Arbre Rouge et noir,Basé surTreemapRéalisation, Caractéristiques telles que le tri personnalisé .
TreeSet Est une collection ordonnée,Son rôle est d'assurer l'ordreSetEnsemble.Il est hérité deAbstractSetClasse abstraite,C'est fait.NavigableSet, Cloneable, java.io.SerializableInterface.
TreeSet Hérité deAbstractSet,Donc C'est unSetEnsemble,AvecSetPropriétés et méthodes de.
TreeSet C'est fait.NavigableSetInterface,Cela signifie qu'il supporte une gamme de méthodes de navigation.Comme trouver la meilleure correspondance avec la cible spécifiée.
TreeSet C'est fait.CloneableInterface,Ça veut dire qu'il peut être cloné.
TreeSet C'est fait.java.io.SerializableInterface,Cela signifie qu'il supporte la sérialisation.
TreeSetEst basé surTreeMapRéalisé.TreeSetÉléments pris en charge dans2Trier par:Ordre naturel Ou Selon la créationTreeSet Fourni à Comparator Trier.Cela dépend de la méthode de construction utilisée.
TreeSet Pour les opérations de base (add、remove Et contains) Fournir une garantie log(n) Dépenses de temps.
En plus,TreeSetEst asynchrone. C'est...iterator L'Itérateur retourné par la méthode estfail-fastDe
边栏推荐
- 事故指标统计
- How to check the lock information in gbase 8C database?
- ftp上传文件时出现 550 Permission denied,不是用户权限问题
- Initial understanding of pointer variables
- Minecraft 1.18.1, 1.18.2 module development 22 Sniper rifle
- Global and Chinese markets hitting traffic doors 2022-2028: Research Report on technology, participants, trends, market size and share
- Computer graduation design PHP campus restaurant online ordering system
- 2022 eye health exhibition, vision rehabilitation exhibition, optometry equipment exhibition, eye care products exhibition, eye mask Exhibition
- 技术管理进阶——什么是管理者之体力、脑力、心力
- How to use C to copy files on UNIX- How can I copy a file on Unix using C?
猜你喜欢
2022 edition illustrated network pdf
Computer graduation design PHP college student human resources job recruitment network
The intelligent material transmission system of the 6th National Games of the Blue Bridge Cup
SQL statement
Know MySQL database
A doctor's 22 years in Huawei
RDD conversion operator of spark
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Minecraft 1.18.1, 1.18.2 module development 22 Sniper rifle
Building the prototype of library functions -- refer to the manual of wildfire
随机推荐
从顶会论文看2022年推荐系统序列建模的趋势
【MySQL 15】Could not increase number of max_ open_ files to more than 10000 (request: 65535)
Method of changing object properties
Number conclusion LC skimming review - 1
Executing two identical SQL statements in the same sqlsession will result in different total numbers
Crawler (9) - scrape framework (1) | scrape asynchronous web crawler framework
[depth first search notes] Abstract DFS
[untitled] a query SQL execution process in the database
Keyword static
[coppeliasim] 6-DOF path planning
机器学习训练与参数优化的一般过程 (讨论)
论文笔记: 图神经网络 GAT
零基础自学STM32-野火——GPIO复习篇——使用绝对地址操作GPIO
2022年版图解网络PDF
HttpRunnerManager安装(三)-Linux下配置myql数据库&初始化数据
Easy to use js script
[width first search] Ji Suan Ke: Suan tou Jun goes home (BFS with conditions)
Y a - t - il des cas où sqlcdc surveille plusieurs tables et les associe à une autre? Tout fonctionne dans MySQL
How to use C to copy files on UNIX- How can I copy a file on Unix using C?
SSM 程序集