Java中对contains()操作最快的数据结构是什么? 例如我有一组数字{1,7,12,12,20 ...} 给定另一个任意数字x,(平均)最快的方法是生成x是否包含在集合中的 bool(boolean) 值? !contains()的概率大约高5倍。 是否所有 map 结构都提供o(1)操作? HashSet是最快的方法吗? 解决方案如下: 看一下基于集合(哈希集,枚举集)和哈希(HashMap,linkedhash ...,idnetityhash ..)的实现。他们对contains()有O(1) Thi…

2020年11月30日 0条评论 61点热度 阅读全文

这不是一个实际的问题,我只是想在这里讨论和学习数据结构设计,我听说它是​​Google在现场采访中提出的。请告诉我如何改进我的设计,谢谢! 一开始,我想使用双端队列来存储蛇的 body 部位的x,y坐标对。 deque<pair<x, y>> snakeBodyParts; 因为蛇移动时很容易向前推-根据旧的头部位置和当前方向创建新的坐标对作为新的头部,然后弹出以去除尾巴。这样,移动,进餐,检查头撞墙都是O(1)的操作,并且容易与双端队列实现。但是要检查新的头部位置是否与蛇体重叠,将需要遍历…

2020年11月30日 0条评论 34点热度 阅读全文

假设您在Java中拥有一个链表结构。它由节点组成: class Node { Node next; // some user data } 每个节点都指向下一个节点,但最后一个节点除外,后者的下一个为空。假设列表有可能包含一个循环-即最终的Node而不是null可能引用了列表中位于其之前的节点之一。 最好的写作方式是什么 boolean hasLoop(Node first) 如果给定的Node是带有循环的列表的第一个,则返回 true,否则返回 false?您怎么写才能占用恒定的空间和合理的时间? 这是带有循环的…

2020年11月28日 0条评论 68点热度 阅读全文

我希望从HasMap中获取一个值,但是有时该值不存在,所以我这样做了: int var = 0; if (hashMapHouse.containsKey("home1") { var = hashMapHouse.get("houme1"); } if(var==0) //do something else //do something else 我的问题是:是否可以只调用一次hashMap以获取值并测试该值是否存在? 解决方案如下: 在Java 8中,可以使用getOrDefault方法: int var = …

2020年11月27日 0条评论 22点热度 阅读全文

静态和动态数据结构之间的主要区别,优点和缺点是什么? 最常见的数据结构属于哪些类别? 我怎么知道在哪种情况下使用它们? 解决方案如下: 首先要简化: 数据结构只有几种基本类型:数组,列表和树。其他所有内容都可以通过使用这两种结构的不同类型来构成(例如,哈希表可以实现为具有一个用于哈希值的数组和一个用于每个哈希值的列表以处理冲突)。 在这些结构中,阵列是静态的(即,随着对其执行操作,其内存占用量不会随时间变化),其他所有内容都是动态的(即,通常情况下内存占用量会发生变化)。 两种结构之间的差异可以从上面得出: 静态需…

2020年11月25日 0条评论 16点热度 阅读全文

我正在寻找一个好的数据结构来表示以下形式的字符串: Domain:Key1=Value1,Key2=Value2... 每个“域”可以包含以下模式字符-*,?(*-0个或更多字符,?-0或1个字符) 每个“键”可以包含以下模式字符-*,?(*-0个或更多字符,?-0或1个字符) 每个“值”可以包含以下模式字符-*和?(*-0个或更多字符,?-0或1个字符) 例子: JBoss:* *:* JBoss:type=ThreadPool,* JBoss:type=Thread*,* JB*:name=http1,type…

2020年11月24日 0条评论 20点热度 阅读全文

我打算用Java编写Mario的副本。我在考虑两个级别的表示形式/数据结构,但不确定该选择哪个: 一个2D整数数组。用四叉树将级别分成几部分。 它的优缺点是什么? 解决方案如下: 绝对是某种类型的二维数组。整数将是一个好主意,但是字符将是一个更好的主意。 考虑制作一个基本上是“地图”的文本文件。它可能是10行乘10列的文本。在这种情况下,非常简单的地图。也许您可以使用“ a”表示草,使用“ b”表示砖头。这样,您甚至可以在将地图付诸行动之前从视觉上了解您的地图。但是您基本上可以对应用程序进行编程,使其依赖于此文本文…

2020年11月24日 0条评论 23点热度 阅读全文

我们可以在LinkedHashSet中的固定点插入Elements吗?我知道我们不能在HashSet中的固定点插入元素,因为HashSet不维护插入顺序。但是,即使LinkedHashSet保持插入顺序,我也无法弄清楚为什么以下代码引发错误: import java.util.*; class Main{ public static void main(String args[]){ LinkedHashSet<String> set=new LinkedHashSet<String>();…

2020年11月24日 0条评论 21点热度 阅读全文

我的程序: private class Node{ private d1 val; private Node next; public Node(d1 val){ this.val=val; next=null; } } 公共(public)节点sorted_list(左侧节点,右侧节点){ try { Node result=null; if(left==null) { return right; } if(right==null) { return left; } if(left.val <= right…

2020年11月23日 0条评论 26点热度 阅读全文

我研究了OpenJDK source code的 CopyOnWriteArrayList ,似乎所有写操作均受同一锁保护,而读操作则根本不 protected 。据我了解,在JMM下,对变量的所有访问(读和写)都应受锁保护,否则可能会发生重新排序的效果。 例如,set(int, E)方法包含以下几行(处于锁定状态): /* 1 */ int len = elements.length; /* 2 */ Object[] newElements = Arrays.copyOf(elements, len); /* …

2020年11月18日 0条评论 37点热度 阅读全文