Tag: algorithm

使用2个“浮动”模拟“双”

我正在编写一个只支持32位单精度浮点运算的embedded式硬件程序。 然而，我正在执行的algorithm需要64位双精度加法和比较。 我正在尝试使用两个float的元组来模拟double数据types。 所以一个double d将被模拟为一个包含元组的struct ： (float d.hi, float d.low) 。 使用字典顺序来进行比较应该很简单。 然而，加法是有点棘手，因为我不知道我应该使用哪个基地。 应该是FLT_MAX ？ 我怎么能检测一个进位？ 如何才能做到这一点？ 编辑（清晰）：我需要额外的有效数字，而不是额外的范围。

parsing一个TB的文本，并有效地计算每个单词的出现次数

最近我遇到了一个面试问题，以任何语言创buildalgorithm，应该做以下几点 阅读1 TB的内容 对该内容中的每个重复单词进行计数 列出十个最常出现的单词 你能让我知道最好的方法来创build一个algorithm吗？ 编辑： 好的，假设内容是英文的。 我们如何才能find那个内容中最常出现的前10个单词？ 我的另一个疑问是，如果故意给予唯一的数据，那么我们的缓冲区将会随着堆栈大小溢出而过期。 我们也需要处理。

JavaScript：计算一个数字的第n个根

我正在尝试使用JavaScript获取数字的第n个根，但是我没有看到使用内置Math对象的方法。 我可以俯视吗？ 如果不… 有一个math库，我可以使用有这个function？ 如果不… 什么是自己做这个最好的algorithm？

ASCII艺术图像转换algorithm如何工作？

有一些很好的免费的“ASCII艺术”转换网站像这样的： ASCII-art.org 这种图像转换algorithm如何工作？ ， 。 W， WW @ W，WW，W，：W * .W。 ＃WW @WW WW＃ W WW.WWW WW：W W. WW * WWW＃WW @ W *：WW.WWWWWWW @ WWW @ W＃ + *＃WW＃WWWWWWWWWWWWW＃WW＃@WWWWWWWWWWWWWWWWWWWWWW W WW WWWWWWWWWWWWWWWWWW W WW WWWWWWWWWWWWWWWWWW @ W＃ ，WW.WWWWWWWWWWWWWWWWWWWWW WW @ WWWWWWWWWWWWWWWWWWWWW ：WWWWWWWWWWWWWWWWWWWWWWWW： @ WWWWWWWW @ WWWWWWW @@ WWWWWW。 W * WWWWWW :::: @ WWW […]

查找string中子序列的出现次数

例如，让string为pi的前10位， 3141592653 ，子序列为123 。 请注意，该序列发生两次： 3141592653 1 2 3 1 2 3 这是一个面试问题，我无法回答，我想不出一个有效的algorithm，它是在扰乱我。 我觉得应该可以做一个简单的正则expression式，但像1.*2.*3不返回每个子序列。 我在Python中的天真执行（在每个1之后每个2计数3）已经运行了一个小时，没有完成。

了解“中位数”algorithm

我想了解下面例子中的“中位数”algorithm： 我们有45个不同的数字，分成9组，每组5个元素。 48 43 38 33 28 23 18 13 8 49 44 39 34 29 24 19 14 9 50 45 40 35 30 25 20 15 10 51 46 41 36 31 26 21 16 53 52 47 42 37 32 27 22 17 54 第一步是sorting每个组（在这种情况下，他们已经sorting） 第二步recursion地找出中位数的“真实”中位数（ 50 45 40 35 30 25 […]

Max-Heapify最糟糕的情况 – 你如何得到2n / 3？

在CLRS，第三版，第155页中给出了在MAX-HEAPIFY中， 每个子树的最大尺寸至多为2n / 3 ，最差的情况发生在树的底部正好满一半的时候。 我明白为什么最差的时候，树的底部正好是半满的。 在这个问题中也回答了MAX-HEAPIFY中的最坏情况：“最坏的情况发生在树的底部正好是半满的时候” 我的问题是如何获得2n / 3？ 为什么如果最低水平是一半，那么子树的大小是2n / 3？ 如何计算？ 谢谢

在间隔列表中search间隔重叠？

说[a，b]表示从a到b的实线上的区间，a <b，包含（即[a，b] =全部x的集合，使得a <= x <= b）。 另外，如果[a，b]和[c，d]共享任何x使得x在[a，b]和[c，d]中，则它们是“重叠的”。 给定一个区间列表（[x1，y1]，[x2，y2]，…），find与[x，y]重叠的所有区间的最有效方法是什么？ 显然，我可以尝试每一个，并在O（n）。 但是我想知道是否可以用一些聪明的方式对间隔列表进行sorting，我可以通过二进制search在O（log N）中find/一个/重叠的项目，然后从列表中的位置“查找”来查找所有重叠的间隔。 但是，如何分类间隔以使这种策略起作用呢？ 请注意，列表项本身中的元素之间可能会有重叠，这使得这很难。 我已经尝试了通过左端，右端，中间间隔sorting，但没有一个导致彻底search。 帮帮我？

点在多边形algorithm

我看到下面的algorithm工作来检查点是否在这个链接给定的多边形： int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy) { int i, j, c = 0; for (i = 0, j = nvert-1; i < nvert; j = i++) { if ( ((verty[i]>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ) c = !c; } return c; […]

具有未知数量的簇的无监督聚类

我有一个三维vector大集。 我需要根据欧几里德距离对它们进行聚类，使得任何特定聚类中的所有向量之间的欧氏距离小于阈值“T”。 我不知道有多less个集群存在。 最后，可能存在不属于任何聚类的单个vector，因为其欧几里得距离不小于空间中任何vector的“T”。 现在应该使用哪些现有的algorithm/方法？ 谢谢Abhishek S