Tag: 算法

检测圆形（非精确圆）路径算法？

我收到一个路径 – 来自touchevent的x，y坐标列表。 如何检测此路径形成圆形路径（不是完整或精确的圆）？ 是否有任何算法或方法来检测这个？

Mergesort交换和比较

我正在研究一个分析项目，我正在观察在Java中实现时不同算法的行为方式。 我得到了一些在线实现Mergesort算法的代码，现在我需要在10,000个随机生成的整数（1到100,000之间）的数组上运行此代码，并记录进行了多少次交换和比较。 我不确定代码中的哪一点增加了计算Swaps和Comparisons的变量。 期望值是多少？ 因为Mergesort的最佳，最差和平均情况都是nlog（n）这是否意味着我应该期望10,000 *（10,000的基数2）约为138,000，换算和比较的总和？ 这是代码，我猜测交换仅在原始数组被更改时发生，比较我不太确定： void MergeSort(int low, int high) // a[low : high] is a global array to be sorted. // Small(P) is true if there is only one element to // sort. In this case the list is already sorted. { if (low < high) { // If there are more […]

使用O（1）中的前缀树查找单个最近邻居？

我正在读一篇论文，他们提到他们能够使用前缀树在O（1）中找到单个最近邻居。 我将描述一般问题，然后是经典解决方案，最后是论文中提出的解决方案： 问题 ：给定一个位向量列表L（所有向量具有相同的长度）和查询位向量q，我们希望找到q的最近邻居。 距离度量是汉明距离（多少位不同）。 天真的方法是通过列表并计算列表中每个向量和q之间的汉明距离，这将取O（N）。 然而，鉴于我们将拥有数以百万计的非常昂贵的位向量，因此我们希望减少这一点。 经典解决方案 ：这个问题的经典解决方案是使用近似来找到最近邻居，从而实现O（logN）。 这样做的方法是首先按字典顺序对L进行排序，以使相似的位向量彼此接近。 然后给定q，我们在排序列表上应用二进制搜索以获得q在排序列表中的位置，并获取列表上方和下方的向量（因为它们类似于排序）并计算他们之间的距离，选择最短的汉明距离。 然而，仅仅进行一次排序我们仍然会遗漏许多类似的向量，因此为了覆盖尽可能多的相似向量，我们使用P个列表和P个jumbling函数。 每个jumbling函数对应于每个列表。 然后我们将每个位向量插入到P中的每个列表中，然后用相应的jumbling函数对其进行混音。 因此，我们最终得到P列表，每个列表都有位向量，但位数不同。 我们再次按字典顺序对P中的每个列表进行排序。 现在给出q，我们对P中的每个列表应用相同的二进制搜索，但是在这里我们在根据我们访问的列表将jumbling函数应用于q之前。 在这一步中，我们得到P个最相似的向量到q，所以我们最终得到一个与q最相似的向量。 这样我们就可以覆盖尽可能多的相似向量。 通过忽略排序所需的时间，定位最近邻居所需的时间是O（log n），这是在每个列表上进行二进制搜索的时间。 建议的解决方案 ：文中提出的这个解决方案（但没有任何解释）说我们可以使用前缀树在O（1）时间内获得最近邻居。 在论文中，他们说他们使用P个前缀树和P个jumbling函数，其中每个jumbling函数对应于每个树。 然后，在用相应的混音函数对每个向量的位进行混音后，它们将位向量插入到每个树中。 给定q，我们将跳跃函数应用于对应于每个树的q，并且我们从每个树中检索q最相似的向量。 现在我们最终得到从树中检索到的P位向量。 在论文中，他们说只是从前缀树获得最相似的q向量是O（1）。 我根本不理解这一点，因为我知道搜索前缀树是O（M），其中M是位向量的长度。 有人理解为什么是O（1）？ 这是我所指的论文（第3.3.2节）：实时网络上基于内容的人群检索 http://students.cse.tamu.edu/kykamath/papers/cikm2012/fp105-kamath.pdf 我还希望你能回答我与此相关的另一个问题： 如何在NN搜索的前缀树中查找最相似的位向量？

项目欧拉45

我还不是一个熟练的程序员，但我认为这是一个有趣的问题，我想我会试一试。 三角形，五边形和六边形数字由以下公式生成： 三角形T_（n）= n（n + 1）/ 2 1,3,6,10,15 …… 五角形P_（n）= n（3n-1）/ 2 1,5,12,22,35 …… 六角形H_（n）= n（2n-1）1,6,15,28,45，…… 可以validationT_（285）= P_（165）= H_（143）= 40755。 找到下一个三角形和六边形的三角形数字。 是任务描述。 我知道六角形数字是三角形数字的子集，这意味着你只需要找到一个Hn = Pn的数字。 但我似乎无法让我的代码工作。 我只知道java语言，这就是为什么我在网络上找不到解决方案的原因。 无论如何希望有人可以帮忙。 这是我的代码 public class NextNumber { public NextNumber() { next(); } public void next() { int n = 144; int i = 165; int p = i * […]

用于大输入的Java优化算术和赋值运算符

我有一段代码必须在时钟速度方面运行得非常快。 该算法已经在O（N）中。 它需要2秒，需要1秒。 对于大多数A.length输入~100,000，除非特定行代码被调用极限次数，否则需要.3s。 （对于深奥的编程挑战） 它使用1,2，… N – > 1,3,4,10,15 ..的算术系列的计算，可以用n *（n + 1）/ 2 I循环通过这个等式数百个成千上万次。 我无法访问输入，也无法显示它。 我能够返回的唯一信息是运行所花费的时间。 特别是等式是： s+=(n+c)-((n*(n+1))/2); s和c的值可以是0到10亿 n可以是0到100,000 在时钟速度方面写这个语句最有效的方法是什么？ 我听说除法需要更多的时间然后乘法，但除此之外我无法确定在一行或多个赋值行中写这个是否更有效。 除以乘法再乘以然后除以？ 还会创建自定义整数类型显着帮助吗？ 根据请求编辑，带有小输入案例的完整代码（对不起，如果它很难看，我只是继续剥离它）： public static void main(String[] args) { int A[]={3,4,8,5,1,4,6,8,7,2,2,4};//output 44 int K=6; //long start = System.currentTimeMillis();; //for(int i=0;i<100000;i++){ System.out.println(mezmeriz4r(A,K)); //} //long end = System.currentTimeMillis();; // System.out.println((end – start) + […]

使用Stacks Java将中缀转换为Postfix

我正在尝试编写一个程序来将中缀表达式转换为后缀表达式。 我使用的算法如下： 1. Create a stack 2. For each character t in the expression – If t is an operand, append it to the output – Else if t is ‘)’,then pop from the stack till ‘(‘ is encountered and append it to the output. do not append ‘(‘ to the output. – If t […]

相交的矩形

这是一个分析几何问题。我不确定我可以在这里发布。但是我必须想出一个Java函数才能完成这个function。我在页面/ swing容器中有多个矩形。我知道它的界限矩形。现在我需要找到哪些矩形相互交叉。这里交叉矩形的一件好事总是有相同的y分量，所有矩形都是相同的高度。我必须根据它们的x坐标和宽度配对矩形 例如 Rect1 has bounds:20,10,50,20 Rect2 has bounds:60,10,30,20 Rect3 has bounds:40,10,40,20 Rect4 has bounds 20,30,40,20 Rect5 has bounds 20,50,30,20 现在我的方法应该返回 Rect1 and Rect2 Rect2 and Rect3 Rect3 and Rect1 是否有任何算法或之前有人试过？提出你的建议 编辑：更具体地说，我的矩形实际上是一个JLabel。 我将标签放在表格的行内。

Java哈希码在一种情况下发生冲突而在另一种情况下不会发生碰撞，为什么？ （以下代码）

我尝试编写一个小程序来演示java中的哈希冲突，只重写了equals而不是hashcode（）方法。 这是为了certificate两个不等对象可以具有相同哈希码的理论。 这是针对行为问题的面试问题。 我创建了200,000个对象，将它们存储在一个数组中，然后将它们进行比较以查看哪些是重复的。 （为此我在对象创建阶段之后使用嵌套for循环迭代对象数组。）对于大约200,000个对象，我得到9次碰撞。 第一个是索引196和121949处的对象。然后我继续打印这些哈希码以显示两个值是相同的。 但是我得到了一些非常令人惊讶的行为。 如果我遍历嵌套的for循环并打印哈希码的第一次碰撞，我得到相同的哈希码值 1867750575 1867750575 对于索引196和121949处的两个对象。 但是如果我注释掉嵌套for循环以检测所有冲突并直接打印索引196和121949的元素的哈希码，我得到 1829164700 366712642 注意，我没有评论这些元素的创建，只是我检查碰撞的部分。 为什么会发生这种情况，即使我不迭代它们，哈希码是不是应该一致？ 附录1：据我所知，有没有一个消息来源，按照生日原则，如果我创建200,000个对象，我必须得到一个碰撞，如何迭代每个hascode或不改变任何东西？ 附录2：我尝试添加另一个200000大小的数组，只是为了查看碰撞索引是否发生了变化，但是没有，所以显然在未提交循环的情况下对二进制文件进行更改不会进行任何更改。 因此，更改二进制更改哈希码的假设并不成立。 这是我的代码 import java.util.HashMap; public class EmployeeFactory { private static int counter = 0; public int id; public String empName; EmployeeFactory() { id = counter; empName = “employee_” + id; counter++; } @Override public boolean equals(Object o) […]

在Java中获取k个最小（或最大）数组元素的最快方法是什么？

我有一个元素数组（在这个例子中，这些只是整数），使用一些自定义比较器进行比较。 在这个例子中，我通过定义i SMALLER j模拟这个比较器，当且仅当scores[i] <= scores[j] 。 我有两种方法： 使用当前k候选人的堆 使用当前k候选的数组 我通过以下方式更新上面的两个结构： heap：方法PriorityQueue.poll和PriorityQueue.offer ， array：存储候选数组中前k个候选中最差的索引top 。 如果新看到的示例比索引top的元素更好，则后者由前者替换，并且top通过迭代遍历数组的所有k个元素来更新。 但是，当我测试了哪种方法更快时，我发现这是第二种。 问题是： 我对PriorityQueue使用是否不理想？ 计算k个最小元素的最快方法是什么？ 我感兴趣的是，当例子的数量可以很大，但是邻居的数量相对较小（在10到20之间）。 这是代码： public static void main(String[] args) { long kopica, navadno, sortiranje; int numTries = 10000; int numExamples = 1000; int numNeighbours = 10; navadno = testSimple(numExamples, numNeighbours, numTries); kopica = testHeap(numExamples, numNeighbours, numTries); sortiranje […]

如何在Java 8中找到N个数字中最大的M个数字？

IntStream可能是最简单的方法，但我只能选择最小的M数，如下所示： public class Test { private static final int[] arr = {5, 3, 4, 2, 9, 1, 7, 8, 6}; public static void main(String[] args) throws Exception { System.out.println(Arrays.asList(IntStream.of(arr).sorted().limit(5).boxed().toArray())); } } 顺便说一句，考虑到算法的复杂性并假设N >> M，“排序+限制”方法只有O（N log（N））的复杂度。 我认为最好的复杂性可能达到O（N log（M）），但我不知道Java 8是否有这种流方法或收集器。