Tag: algorithm

Java – 删除ArrayList中的重复项

我正在使用ArrayList来存储Strings 。 该程序提示用户一个菜单，并允许用户select一个操作来执行。 这样的操作是将string添加到列表中，打印条目等。我想要做的是创build一个名为removeDuplicates()的方法。 这个方法将searchArrayList并删除任何重复的值。 我想在列表中留下一个重复值的实例。 我也希望这个方法返回删除重复的总数。 我一直在尝试使用嵌套循环来实现这一点，但我一直在遇到麻烦，因为当条目被删除时， ArrayList的索引被改变，事情不能正常工作。 我从概念上知道我需要做什么，但是在代码中实现这个想法时遇到了麻烦。 这是一些伪代码： 从第一个入口开始; 检查列表中的每个后续条目，看它是否与第一个条目匹配; 删除列表中与第一个条目匹配的每个后续条目; 毕竟所有参赛作品已经过检查，转到第二项; 检查列表中的每个条目，看它是否与第二个条目匹配; 删除列表中与第二个条目匹配的每个条目; 重复列表中的条目 这是我迄今为止的代码： public int removeDuplicates() { int duplicates = 0; for ( int i = 0; i < strings.size(); i++ ) { for ( int j = 0; j < strings.size(); j++ ) { if ( i == […]

从未知长度的序列中随机选取N个项目

我试图编写一个algorithm，从一个随机序列中selectN个不同的项目，而不必事先知道序列的大小，以及在不止一次遍历序列的过程中，花费的昂贵。 例如，序列的元素可能是一个巨大的文件的行。 当N = 1时，我find了一个解决scheme（也就是说，当试图从一个巨大的序列中随机挑选一个元素时）： import random items = range(1, 10) # Imagine this is a huge sequence of unknown length count = 1 selected = None for item in items: if random.random() * count < 1: selected = item count += 1 但是我怎样才能达到N的其他值（比如N = 3）呢？

在n个项目的数组中findk个最小数字的algorithm

我试图编写一个algorithm，它可以在O（n）时间内打印n个大小数组中的k个最小数字，但是我不能将时间复杂度降低到n。 我该怎么做？

计算将一个排列转换为另一个排列所需的相邻交换

我们给出了两个小写拉丁字母的序列。 它们的长度相同，并且具有相同数量的给定types的字母（第一个与第二个字母具有相同数量的t等等）。 我们需要find将第一个序列转化为第二个序列所需的最小互换次数（ 通过“互换”我们的意思是改变两个相邻字母的次序 ）。 我们可以安全地假设每两个序列可以相互转换。 我们可以用蛮力来做到这一点，但是序列太长了。 input： 序列的长度（至less2，最多999999），然后是两个序列。 输出： 表示序列变为相同所需的交换次数的整数。 例： {5，aaaaa，aaaaa}应输出{0}， {4，abcd，acdb}应该输出{2}。 我想起来的第一件事就是泡泡。 我们可以简单地说明每个交换的顺序。 问题是：a）O（n ^ 2）最糟糕的情况b）我不相信这会给我每个案件的最小数量…即使是最优化的泡沫似乎也没有办法。 我们可以执行鸡尾酒sorting来解决龟的问题 – 但它会给我最好的performance吗？ 或者也许有一些更简单/更快？ 这个问题也可以表述为： 当唯一允许的操作是换位时，我们如何确定两个string之间的编辑距离？

什么是最好的方式来查找数组中的项目的所有组合？

什么是最好的方式来find在C＃中的数组中的项目的所有组合？

具有固定子集大小的Sum子集

求和子集问题指出： 给定一组整数，是否有一个总和为零的非空子集？ 这个问题通常是NP完全的。 我很好奇，如果这个轻微的变种的复杂性是已知的： 给定一组整数，是否有一个总和为零的大小为k的子集？ 例如，如果k = 1 ，则可以执行二进制search以在O(log n)find答案。 如果k = 2 ，那么你可以把它归结为O(n log n) （例如参见从一个数组中找出一对元素，其和等于一个给定的数字 ）。 如果k = 3 ，那么你可以做O(n^2) （例如参见在一个数组中find三个元素的总和最接近给定的数字 ）。 作为k一个函数，是否有一个可以放在这个问题上的已知边界？ 作为动机，我正在考虑这个问题。 你如何将一个数组分成两部分，这两部分的平均数是相等的？ 并试图确定它是否实际上是NP完整的。 答案在于是否有如上所述的公式。 除了一个通用的解决scheme，我会非常有兴趣知道k=4的最优界限。

用于在string中search子string的快速algorithm

我想要一个高效的algorithm（或库），我可以在Java中使用来searchstring中的子string。 我想要做的是： 给定一个inputstring – INSTR ： “BCDEFGH” 和一组候选string – CAND ： “AB”，“CDE”，“FG”，“H”，“IJ” find与INSTR内的子string匹配的任何CANDstring 在这个例子中，我会匹配“CDE”，“FG”和“H”（但不是“AB”和“IJ”） 可能有数千个候选string（在CAND中），但更重要的是，我将这样search数百万次，所以我需要它是快速的。 我想使用char数组。 另外，我并没有将其构build成解决scheme，比如分发search – 只是本地最有效的function/algorithm。 此外，CAND和INSTR中的所有string都将相对较小（<50个字符） – 即目标stringINSTR相对候选string不长。 更新我应该提到，CANDstring的集合在INSTR的所有值中都是不变的。 更新我只需要知道有一场比赛 – 我不需要知道比赛是什么。 最终更新由于实施简单，我select尝试AhoCorsick和Rabin-Karp。 因为我有可变长度模式，所以我使用了一个修改过的Rabin-Karp来散列每个模式的前n个字符，其中n是最小模式的长度，那么N就是我的滚动子stringsearch窗口的长度。 对于Aho Corsick，我使用了这个 在我的testing中，我search了两个文档新闻文章中的1000个模式，平均1000次迭代等…规范化的时间完成： AhoCorsick ：1 拉宾卡普 ：1.8 天真的search （检查每个模式和使用string.contains）：50 *一些资源描述在以下答案中提到的algos： http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2×2.pdf http://www-igm.univ-mlv.fr/~lecroq/string/index.html *

在Python中，从列表中删除重复项的最快algorithm是什么，以便所有元素都是唯一的*，同时保持顺序*？

例如： >>> x = [1, 1, 2, 'a', 'a', 3] >>> unique(x) [1, 2, 'a', 3] 假设列表元素是可散列的。 澄清：结果应该保留在列表中的第一个副本。 例如，[1,2,3,2,3,1]变成[1,2,3]。

如何确定多边形是复杂的/凸的/非凸的？

从XFillPolygon的手册页 ·如果形状是复杂的，path可以自相交。 请注意，path中的重合点不被视为自交。 ·如果形状为凸，则对于多边形内的每对点，连接它们的线段不会与path相交。 如果客户知道，指定凸面可以提高性能。 如果将凸指定为非凸的path，则graphics结果是不确定的。 ·如果形状为非凸，path不自相交，但形状不是完全凸的。 如果客户端知道，指定Nonconvex而不是Complex可能会提高性能。 如果您为自相交path指定Nonconvex，则graphics结果未定义。 我遇到了填充XFillPolygon性能问题，因为手册页build议我要采取的第一步是指定Polygon的正确形状（我目前正在使用Complex来保证安全）。 是否有一个有效的algorithm来确定多边形（由一系列坐标定义）是凸的，非凸的还是复杂的？

什么是find重叠矩形区域的高效algorithm

我的情况 input：一组矩形 每个矩形包含4个双打，如下所示：（x0，y0，x1，y1） 它们不是以任何angular度“旋转”，它们都是相对于屏幕“上/下”和“左/右”的“普通”矩形 他们被随机放置 – 他们可能在边缘触摸，重叠，或没有任何接触 我将有几百个矩形 这是在C＃中实现的 我需要find 由它们重叠形成的区域 – canvas中多于一个矩形“覆盖”的所有区域（例如，具有两个矩形，这将是交叉点） 我不需要重叠的几何形状 – 只是区域（例如：4平方英寸） 重叠不应该被多次计算 – 例如，想像3个尺寸和位置相同的交叉 – 它们彼此重叠 – 这个区域应该被计算一次（而不是三次） 例 下面的图片包含三个矩形：A，B，C A和B重叠（如虚线所示） B和C重叠（如虚线所示） 我正在寻找的是显示破折号的地方 – AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA————–BBB AAAAAAAAAAAAAAAA————–BBB AAAAAAAAAAAAAAAA————–BBB AAAAAAAAAAAAAAAA————–BBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBB———–CCCCCCCC BBBBBB———–CCCCCCCC BBBBBB———–CCCCCCCC CCCCCCCCCCCCCCCCCCC CCCCCCCCCCCCCCCCCCC CCCCCCCCCCCCCCCCCCC CCCCCCCCCCCCCCCCCCC