Tag: 算法

以下function的时间复杂度是多少？: int func(int n){ if(n==1) return 0; else return sqrt(n); } 其中sqrt（n）是C math.h库函数。 O（1） O（lg n） O（lg lg n）上）我认为运行时间完全取决于sqrt（n）。但是，我不知道这个function是如何实际实现的。 PS找到我所知道的数字的平方根的一般方法是使用牛顿方法。如果我没有错，那么使用牛顿方法的时间复杂度就变成了O（lg n）。答案应该是O（lg n）吗？ PPS在我最近出现的测试中得到了这个问题。

避免整数乘法溢出，然后除法: 我有两个积分变量a和b以及一个常数s resp。 d 。我需要计算(a*b)>>s resp的值。 a*b/d 。问题是乘法可能会溢出，即使a*b/d适合给定的整数类型，最终结果也不正确。怎么能有效地解决？直接的解决方案是将变量a或b扩展为更大的整数类型，但可能没有更大的整数类型。有没有更好的方法来解决这个问题？

Bytelandian Gold Coin，动态编程，解释？: 这有点不成熟，但我不得不问，这里提到的Bytelandian金币问题 – http://www.codechef.com/problems/COINS/ ，据说是典型的DP问题，尽管我已经阅读了DP和递归的基础知识，但我发现很难理解它解， # include # include long unsigned int costArray[30][19]; unsigned int amount; unsigned int currentValue(short int factor2,short int factor3) { int j; unsigned int current = amount >> factor2; for(j=0;j<factor3;j++) current /= 3; return current; } long unsigned int findOptimalAmount(short int factor2,short int factor3) { unsigned int n = currentValue(factor2,factor3); if(n […]

二叉树的最低共同祖先（非二叉搜索树）: 我尝试使用Tarjan的算法和网站上的一种算法来解决这个问题： http ： //discuss.techinterview.org/default.asp？interview.11.532716.6 ，但没有一个是清楚的。也许我的递归概念没有正确构建。请举一个小型演示来解释上面两个例子。我对Union Find数据结构有所了解。这看起来很有意思。所以必须解决问题无论如何。准备面试。如果存在任何其他逻辑/算法，请分享。

BST节点的所有父母？: 在使用递归函数（预订）打印二进制搜索树（BST）时。我需要打印当前节点的所有父节点（路径根目录）。可以使用辅助数据结构（例如，我的代码中的路径），但我不想保留node-> path来存储路径。 4 / \ / \ 2 6 / \ / \ 1 3 5 7 假设我使用预订序遍历在行中打印节点： NODE PATH 4 4 2 4,2 1 4,2,1 3 4,2,3 6 4,6 5 4,6,5 7 4,6,7 我做了如下：工作正常！路径以此代码中的0（零）值结束。 BST中没有节点值为0。 void printpath(int* mypath){ while(*mypath) printf(“%d “, *mypath++); } void preorder(struct tree *p, int* path){ […]

如何测试点是否位于由点云定义的表面的3d形状内？: 我有一个点的集合描述了应该是大致球形的形状的表面，我需要一种方法来确定是否有任何其他给定点位于这个形状内。我之前已经将形状近似为一个精确的球体，但事实certificate这太不准确了，我需要一种更精确的方法。简单和速度有利于完全准确，良好的近似就足够了。我遇到过将点云转换为3d网格的技术，但我发现的大多数事情都非常复杂，我正在寻找尽可能简单的东西。有任何想法吗？

单声道到立体声转换: 我在这里有以下问题：我得到一个表示音频数据的字节块（uint16_t *），生成它们的设备正在捕获单声道声音，所以很明显我在1声道上有单声道音频数据。我需要将这些数据传递给另一个设备，这需要交错的立体声数据（因此，2个通道）。我想要做的基本上是复制数据中的1个通道，以便立体声数据的两个通道都包含相同的字节。你能指点我这样做的有效算法吗？谢谢，f。

如何在二进制堆实现的优先级队列中保留相同优先级元素的顺序？: 我创建了一个二进制堆，它代表一个优先级队列。它只是经典的众所周知的算法。此堆计划不同事件的时间顺序（排序键是时间）。它支持2种操作：插入和删除。堆的每个节点的密钥大于或等于其每个子节点。但是，使用相同的键添加事件不会保留它们的添加顺序，因为每次调用Remove或Insert之后，堆启动和堆降过程都会破坏顺序。我的问题是：在经典算法中应该改变什么来保持具有相同优先级的节点的顺序？

多数表决算法 – 错误？: 如果存在这样的元素，则多数表决算法决定序列中的哪个元素占多数。这是我在试图理解它时发现的最常被引用的链接。 http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html 此外，我们在这里有一个讨论问题的链接：如何找到重复至少N / 2次的数组元素？问题是标记为正确的答案是错误的。请注意，该问题实际上允许输入具有单个元素的正好 N / 2个副本（不一定多于 N / 2，如通常在多数元素检测算法中假设的那样）。我复制了代码并尝试使用[1,2,3,2]和[1,2,3,2,6,2]等输入（产生3和6的结果）。这实际上也适用于上面引用的算法（返回“无多数元素！”）。问题是：只要多数元素和其他任何元素之间发生交替，就会选择数组中不是多数元素的最后一个元素。请更正我错误的想法，并告诉我如何在实施中避免它。

Langford序列实现Haskell或C.: 在组合数学中， Langford配对，也称为Langford序列，是2n数字2n 1, 1, 2, 2, …, n, n序列的排列，其中两个数字相隔一个单位，两个两个相距两个单位，更一般地，每个数字k的两个副本相隔k个单位。例如： n = 3 Langford配对由序列2,3,1,2,1,3. 在haskell或C解决这个问题的好方法是什么你能建议一个算法来解决它（不想使用蛮力）？ – – – – – – – – – – – – – 编辑 – – – – – – – – – – – 我们如何定义数学规则以将@ Rafe的代码放入haskell中