Tag: algorithm

如何用JavaScript包装节点中的文本的一部分

我有一个具有挑战性的问题要解决。 我正在研究一个以正则expression式作为input的脚本。 这个脚本然后在文档中find这个正则expression式的所有匹配，并将每个匹配包装在它自己的<span>元素中。 最难的部分是文本是一个格式化的HTML文档，所以我的脚本需要浏览DOM，并一次性在多个文本节点上应用正则expression式，同时根据需要找出需要分割文本节点的位置。 例如，用一个正则expression式来捕获以大写字母开始并以句点结尾的完整句子，本文档： <p> <b>HTML</b> is a language used to make <b>websites.</b> It was developed by <i>CERN</i> employees in the early 90s. <p> 会变成这样： <p> <span><b>HTML</b> is a language used to make <b>websites.</b></span> <span>It was developed by <i>CERN</i> employees in the early 90s.</span> <p> 该脚本然后返回所有创build的跨度的列表。 我已经有了一些代码，可以find所有的文本节点，并将它们存储在一个列表中，以及它们在整个文档中的位置及其深度。 你并不需要理解代码来帮助我，它的recursion结构可能会有点混乱。 第一部分，我不知道该怎么做是找出哪些元素应该包含在范围内。 function SmartNode(node, depth, start) { […]

人工智能领域有哪些令人印象深刻的algorithm或软件？

我一直喜欢AI和演化algorithm的想法。 不幸的是，大家都知道，这个领域在最初几乎没有像预期那样快速发展。 我正在寻找的是一些有“哇”因素的例子： 以意想不到的方式改编的自主学习系统。 特别活跃的游戏代理商制定了意想不到的策略 符号表示系统，实际上产生了一些有意义和有见地的输出 有趣的多代理系统中的紧急行为。 我们不要深入定义AI的语义。 如果它看起来或听起来像AI，让我们听听 。 我会先从1997年的故事开始 。 Adrian Thompson博士尝试使用遗传algorithm在FPGA中创build语音识别电路。 几千年后，他成功地让设备区分“停止”和“去”语音命令。 他检查设备的结构，发现一些有效的逻辑门与电路的其余部分断开连接。 当他禁用这些所谓无用的门，电路停止工作… 编辑 我们是否可以尝试并将讨论延伸到产生令人印象深刻的技术/algorithm？ 我可以谷歌，如果我想了解数以千计的AI技术， 在早期阶段，但显示承诺 。

后缀树和尝试。 有什么不同？

我正在阅读关于前缀树和Suffix Trees Tries 。 虽然我已经find了Trie代码，但我找不到Suffix Tree的示例。 另外我感觉到构buildTrie的代码和Suffix Tree的代码是一样的，唯一不同的是，在前一种情况下，我们存储前缀，但在后面的后缀中。 这是真的？ 任何人都可以帮我在我的脑海中清除这个问题吗？ 一个示例代码将是很大的帮助！

网球比赛安排

数量有限的球员和数量有限的网球场。 每场比赛最多可以有多less场比赛。 没有人rest2轮。 每个人都和其他人玩。 产生尽可能less的轮次的时间表。 （因为每个人之间必须有轮休的规则，所以可以有一轮没有比赛。）5个球员和2个球场的输出可以是： | 1 2 3 4 5 -|——————- 2| 1 – 3| 5 3 – 4| 7 9 1 – 5| 3 7 9 5 – 在这个输出中，列和行是玩家号码，matrix内的数字是这两个玩家竞争的轮数。 问题是find一个algorithm，可以在一个可行的时间更大的情况下做到这一点。 我们被要求在Prolog中这样做，但任何语言的（伪）代码都是有用的。 我的第一个尝试是一个贪婪的algorithm，但是结果太多了。 然后我提出了一个迭代深化的深度优先search，这是我的一个朋友实现的，但是对于7个玩家来说，这个search仍然花费了太多的时间。 （这是从一个旧的考试题目，我没有任何解决scheme。）

如何计算具有某种属性的大A和B之间的整数？

在编程竞赛中，以下模式出现在很多任务中： 给定数字A和B是巨大的（可能是20个十进制数字或更多），确定具有特定属性P的A≤X≤B的整数X SPOJ有很多类似的练习任务 。 有趣的属性的例子包括： “X的数字和是60” “X只包含数字4和7” “X是回文”，这意味着X的十进制表示等于其反向（例如，X = 1234321） 我知道，如果我们定义f（Y）是这样的整数X≤Y的数目，那么我们的问题的答案是f（B） – f（A – 1） 。 减less的问题是如何有效地计算函数f 。 在某些情况下，我们可以利用某些math属性来提出一个公式，但是这些属性往往比较复杂，我们没有足够的时间来进行比赛。 有没有更多的一般方法，在很多情况下工作？ 它也可以用来枚举具有给定属性的数字或计算它们的聚合吗？ 其中的一个变化是find具有给定属性的第k个数字，当然这可以通过使用二分查找和计数function来解决。

find最大元素的位置

有没有一个标准的函数返回值的数组的最大元素的位置（而不是值）？ 例如： 假设我有一个这样的数组： sampleArray = [1, 5, 2, 9, 4, 6, 3] 我想要一个返回3的整数的函数，告诉我sampleArray[3]是数组中最大的值。

线性时间投票algorithm。 我不明白

当我正在阅读（ find数组中最常见的条目 ）时，提出了Boyer和Moore的线性时间投票algorithm 。 如果您按照该网站的链接，则可以逐步解释algorithm的工作原理。 对于给定的序列， AAACCBBCCCBCC它提出了正确的解决scheme。 当我们将指针向前移动一个元素e： 如果计数器为0，我们将当前候选人设置为e，并将计数器设置为1。 如果计数器不是0，则根据e是否是当前候选者来递增或递减计数器。 当我们完成时，如果有多数，当前候选人是多数。 如果我在AAACCBB作为input的一张纸上使用这个algorithm， 那么build议的候选人将变成B ，显然是错的。 正如我所看到的，有两种可能性 作者从来没有在AAACCBBCCCBCC以外的任何其他algorithm上尝试过他们的algorithm，完全是无能的，应该当场解雇（疑问） 。 我明显错过了一些东西 ，必须禁止从Stackoverflow，并再也不允许触摸任何涉及逻辑。 注意：下面是Niek Sanders algorithm的一个C ++实现 。 我相信他正确地实现了这个想法，因此它也有同样的问题（或不是吗？）。

实施二分查找的缺陷是什么？

二元search比看起来更难实现。 “虽然二分查找的基本思想比较简单，但细节可能会非常棘手……” – Donald Knuth。 哪些错误最有可能被引入新的二进制search实现？

最大化直方图下的矩形区域

我有一个整数高度和恒定宽度的直方图1.我想要最大化直方图下的矩形区域。 例如： _ | | | |_ | | | |_ | | 答案是6,3 * 2，使用col1和col2。 O（n ^ 2）蛮力对我来说很清楚，我想要一个O（n log n）algorithm。 我试图按照最大递增子序列O（n log n）algorithm来思考dynamic编程，但是我不会前进。 我应该使用分而治之algorithm吗？ PS：如果没有这样的解决scheme，要求有足够信誉的人去除分而治之的标签。 在mho的评论之后：我的意思是最大的矩形区域完全适合。 （感谢j_random_hacker澄清:)）。

如何find最大的生成树？

Kruskal最小生成树algorithm的反面是否适用？ 我的意思是，每一步select最大重量（边缘）？ 任何其他想法find最大的生成树？