Tag: algorithm

撤消/重做实施

给我一些思考如何实现撤消/重做function – 就像我们在文本编辑器中所做的那样。 我应该使用哪些algorithm以及我可以读取哪些algorithm。 谢谢。

平行四边形内的随机点

我有一个由4个点在2D中定义的4边凸多边形，我希望能够在里面生成随机点。 如果真的能够简化问题，我可以将多边形限制为平行四边形，但更一般的答案是首选。 生成随机点，直到一个在多边形内部将不起作用，因为它真的是不可预测的时间。

面试问题：三个数组和O（N * N）

假设我们有三个长度为N的数组，其中包含任意长度的数字。 然后我们给出一个M （相同types），我们的任务是从每个数组中select三个数字A ， B和C （换句话说， A 应该从第一个数组中挑选出来， B从第二个数组中挑选出来， C从第三个）所以总和A + B + C = M。 问题：我们可以select所有三个数字，最终的时间复杂度为O（N 2 ）吗？ 插图： 数组是： 1) 6 5 8 3 9 2 2) 1 9 0 4 6 4 3) 7 8 1 5 4 3 而我们得到的是19 。 那么我们的select是从第一个8 ，第二个4 ，第三个7 。

什么额外的轮换是需要从自上而下删除2-3-4左红黑树？

我一直在实现一个LLRB包，应该能够以Sedgewick （ 代码改进的代码） 描述的自下而上2-3或自上而下2-3-4两种模式中的任何一种模式进行操作，尽pipe只处理2- 3棵树在这里 ，感谢RS指针）。 Sedgewick为2-3模式提供了一个非常清晰的树操作描述，尽pipe他花费了大量的时间来讨论2-3-4模式。 他还展示了如何简单地改变插入过程中的颜色翻转顺序，可以改变树的行为（或者在2-3-4的路上分割，或者在2-3的path上分割）： private Node insert(Node h, Key key, Value value) { if (h == null) return new Node(key, value); // Include this for 2-3-4 trees if (isRed(h.left) && isRed(h.right)) colorFlip(h); int cmp = key.compareTo(h.key); if (cmp == 0) h.val = value; else if (cmp < 0) h.left = insert(h.left, […]

生成一个塔防御迷宫（最长的迷宫与有限的墙壁） – 近乎最佳的启发式？

在一个塔防游戏中，你有一个NxM网格，有一个开始，一个完成和一些墙。 敌人从起点到终点都走最短的路，而不经过任何的墙（它们通常不会被限制在网格中，但是为了简单起见，我们假设它们是无论如何都不能穿过对angular的“洞”） 问题（至less对于这个问题）是放置K个额外的墙壁，以最大化敌人必须采取的path。 例如，对于K = 14 我的直觉告诉我，如果（正如我所希望的那样）这个问题是NP难的，我们把这个问题推广到包括在到达终点之前必须访问的路点，也可能没有路点。 但是， 有没有什么像样的启发式algorithm可以接近最优解？ [编辑]我在这里发布了一个相关的问题。

find（稀疏）图的直径的好algorithm？

我有一个大的，连接，稀疏graphics的邻接表格forms。 我想find两个尽可能相距较远的顶点，即图的直径和实现它的两个顶点。 我对这个问题感兴趣，无论是针对不同的应用程序，还是无向和有针对性的案例。 在有针对性的情况下，我当然关心指向距离（从一个顶点到另一个顶点的最短的有向path）。 有没有比计算所有对最短path更好的方法？ 编辑 ：通过“尽可能远”，我当然是指“最长的最短path” – 即从一个到另一个的最短距离的所有顶点对的最大值。

如何处理数字猜测游戏（一个扭曲）algorithm？

我正在学习编程（python和algorithm），并试图在一个我觉得有趣的项目上工作。 我已经创build了几个基本的Python脚本，但我不知道如何解决我正在尝试构build的游戏的解决scheme。 以下是游戏的运作方式： 用户将被赋予具有价值的项目。 例如 Apple = 1 Pears = 2 Oranges = 3 他们将有机会select他们喜欢的任何组合（即100个苹果，20个梨子和1个桔子）。 计算机唯一的输出是总价值（在这个例子中，目前是143美元）。 电脑会试图猜测他们有什么。 这显然不能够正确的第一回合。 Value quantity(day1) value(day1) Apple 1 100 100 Pears 2 20 40 Orange 3 1 3 Total 121 143 接下来用户可以修改他们的数量，但不超过总数量的5％（或者我们可能select的其他百分比，例如5％）。 水果的价格可以随意改变，所以总价值也可以改变（为了简单起见，我不改变水果价格）。 使用上面的例子，在游戏的第二天，用户在第三天返回一个$ 152和$ 164的值。下面是一个例子。 quantity(day2) %change(day2) value(day2) quantity(day3) %change(day3) value(day3) 104 104 106 106 21 42 23 46 […]

如何在线性时间内使用堆find数字的中位数？

维基百科说： selectalgorithm：find最小值，最大值，最小值和最大值， 中值 ，甚至第k个最大元素都可以使用堆在线性时间内完成。 它所说的是，它可以做到，而不是如何。 你可以给我一些开始如何使用堆可以做到这一点？

Z形扫描N×Narrays

我有一个简单的数组。 数组长度总是有一个整数的平方根。 所以16,25,36等 $array = array('1', '2', '3', '4' … '25'); 我所做的，就是用HTML来排列数组，使它看起来像是一个双面的块。 我想要做的是对元素进行sorting，以便当我将JSON编码数组传递给jQuery时，它将迭代数组，淡入当前块，从而得到一种波animation。 所以我想sorting这样的数组types 所以我的sorting数组看起来像 $sorted = array('1', '6', '2', '3', '7', '11', '16, '12' .. '25'); 有办法吗？谢谢

这个怎么用？ 河内解答奇怪的塔

当我发现河内塔这个不寻常的迭代解决scheme时，我迷失在互联网上： for (int x = 1; x < (1 << nDisks); x++) { FromPole = (x & x-1) % 3; ToPole = ((x | x-1) + 1) % 3; moveDisk(FromPole, ToPole); } 这篇文章也有类似的Delphi代码中的一个答案。 然而，对于我的生活，我似乎无法find一个好的解释，为什么这个工程。 任何人都可以帮我理解吗？