问题标签 [algorithm]

我正在尝试确定完成下述任务的最佳时间效率算法。

我有一组记录。对于这组记录，我有连接数据，指示该组中的记录对如何相互连接。这基本上表示一个无向图，记录是顶点，连接数据是边。

集合中的所有记录都具有连接信息（即不存在孤立记录；集合中的每条记录都连接到集合中的一个或多个其他记录）。

我想从集合中选择任意两条记录，并能够显示所选记录之间的所有简单路径。“简单路径”是指路径中没有重复记录的路径（即仅限有限路径）。

注意：两个选择的记录总是不同的（即开始和结束顶点永远不会相同；没有循环）。

例如：

如果我选择 B 作为我的开始记录，E 作为我的结束记录，我希望找到所有通过记录连接的简单路径，这些路径将记录 B 连接到记录 E。

这是一个例子，实际上我可能有包含数十万条记录的集合。

在候选人筛选过程中，您发现哪些简单的算法或数据结构相关的“白板”问题是有效的？

我有一些简单的方法可以用来验证解决问题的能力，可以简单地表达，但有一些机会应用一些启发式方法。

我用于初级开发人员的基础知识之一是：

编写一个 C# 方法，该方法接受一个包含一组单词（一个句子）的字符串，并将这些单词向右旋转 X 个位置。当句子最后位置的单词被旋转时，它应该出现在结果字符串的前面。

当候选人回答这个问题时，我希望看到他们可以使用 .NET 数据结构和方法（string.Join、string.Split、List 等）来解决问题。我还寻找他们来识别优化的特殊情况。就像单词需要旋转的次数并不是真正的 X，而是 X % 的单词数。

您在面试候选人时使用了哪些白板问题，以及您在答案中寻找哪些内容（不需要发布实际答案）。

一段时间以来，我一直想知道，连接字符串数组的一个漂亮、干净的解决方案可能是什么样的。示例：我有 ["Alpha", "Beta", "Gamma"] 并且想将字符串合并为一个，用逗号分隔 - “Alpha, Beta, Gamma”。

现在我知道大多数编程语言为此提供了某种连接方法。我只是想知道如何实现这些。当我上入门课程时，我经常尝试单干，但始终没有找到令人满意的算法。一切看起来都相当混乱，问题是你不能只循环遍历数组，连接字符串，因为你会添加一个太多的逗号（在最后一个字符串之前或之后）。我不想检查循环中的条件。我真的不想在循环之前/之后添加第一个或最后一个字符串（我想这可能是最好的方法？）。

有人可以告诉我一个优雅的解决方案吗？或者告诉我为什么没有更优雅的东西？

我有一个可能有多达 8 位小数的数字数组，我需要找到可以将它们相乘的最小公数，以便它们都是整数。我需要这个，所以所有原始数字都可以乘以相同的比例，并由一个只处理整数的密封系统处理，然后我可以检索结果并将它们除以公共乘数以获得我的相对结果.

目前我们对数字进行一些检查并乘以 100 或 1,000,000，但 *sealed 系统完成的处理在处理大数字时可能会变得非常昂贵，因此仅仅为了它而将所有内容乘以一百万并不是真的一个很好的选择。作为一个近似值，每次乘以 10 倍时，密封算法的成本就会增加 10 倍。

什么是最有效的算法，它也会给出最好的结果，以完成我需要的东西，是否有我需要的数学名称和/或公式？

*密封系统并不是真正密封的。我拥有/维护它的源代码，但它有 100,000 多行专有魔法，并且已经过彻底的错误和性能测试，出于多种原因，更改它以处理浮点数不是一种选择。它是一个系统，它创建一个由 X 乘 Y 单元组成的网格，然后将 X 乘 Y 的矩形放入网格中，“专有魔法”发生并吐出结果——显然这是一个极其简化的现实版本，但它是一个足够好的近似值。

到目前为止，有一些很好的答案，我想知道我应该如何选择“正确”的答案。一开始我认为唯一公平的方法是创建每个解决方案并对其进行性能测试，但后来我意识到纯速度并不是唯一相关的因素——更准确的解决方案也非常相关。无论如何我都编写了性能测试，但目前我正在使用“直觉”公式根据速度和准确性选择正确的答案。

我的性能测试处理 1000 组不同的 100 个随机生成的数字。每个算法都使用相同的随机数集进行测试。算法是用 .Net 3.5 编写的（尽管到目前为止与 2.0 兼容）我非常努力地使测试尽可能公平。

• Greg – 乘以大数然后除以 GCD – 63 毫秒
• Andy – 字符串解析 – 199 毫秒
• Eric – Decimal.GetBits – 160 毫秒
• Eric – 二进制搜索 – 32 毫秒
• Ima - 抱歉，我无法弄清楚如何在 .Net 中轻松实现您的解决方案（我不想花太长时间在上面）
• 比尔——我认为你的答案与格雷格的很接近，所以没有实施。我敢肯定它会更快，但可能不太准确。

所以 Greg 的乘以大数然后除以 GCD”解决方案是第二快的算法，它给出了最准确的结果，所以现在我称之为正确的。

我真的希望 Decimal.GetBits 解决方案是最快的，但它非常慢，我不确定这是由于将 Double 转换为 Decimal 还是由于 Bit 掩码和移位。使用 BitConverter.GetBytes 和此处包含的一些知识应该有一个类似的可用解决方案：http: //blogs.msdn.com/bclteam/archive/2007/05/29/bcl-refresher-floating-point- types-the-good-the-bad-and-the-ugly-inbar-gazit-matthew-greig.aspx但每次我读到那篇文章时，我的眼睛一直在发呆，最终我没时间尝试实现一个解决方案。

如果有人能想到更好的方法，我总是对其他解决方案持开放态度。

如何获取一组包含任意值的多边形并创建相应的位图，其中每个像素都包含该位置的多边形值？

为了将问题置于上下文中，我的多边形包含有关多边形内每平方公里平均人数的信息。我需要创建一个栅格/位图，其中包含代表 200 米箱中人口的像素。

我过去做过类似的事情，我使用多边形通过绘制位图并填充值来创建蒙版，然后将位图转换为我可以操作的数组。我敢肯定有更好的方法来做到这一点！

我根据要求进一步澄清了这个问题。

1. 有多个多边形，每个多边形是一组向量
2. 每个多边形都有一个唯一值
3. 多边形不重叠

谢谢

缺口

同步算法有什么好的参考吗？

我对在多个用户之间同步以下类型的数据的算法感兴趣：

• 日历
• 文件
• 列表和大纲

我不只是在寻找目录内容的同步la rsync；我对合并单个文件中的数据感兴趣。

输入：词组 1，词组 2

输出：语义相似度值（介于 0 和 1 之间），或者这两个短语谈论同一事物的概率

我有许多由 GPS 记录的轨迹，更正式地可以描述为许多线串。

现在，一些记录的轨迹可能是同一条路线的记录，但由于 GPS 系统的不准确，记录是在不同的场合进行的，而且它们可能是以不同的速度记录的，所以它们不会完美匹配，但当人类在地图上查看时仍然看起来足够近，以确定它实际上是已记录的同一条路线。

我想找到一种算法来计算两个线串之间的相似度。我想出了一些自制的方法来做到这一点，但想知道这是否是一个已经有很好的算法来解决的问题。

考虑到相似的平均值代表地图上的相同路径，您将如何计算相似度？

编辑：对于那些不确定我在说什么的人，请查看此链接以了解行字符串的定义：http: //msdn.microsoft.com/en-us/library/bb895372.aspx - I' m不询问字符串。

在 Java 应用程序中工作时，我最近需要组装一个以逗号分隔的值列表以传递给另一个 Web 服务，而无需事先知道有多少元素。我能想到的最好的事情是这样的：

我意识到这不是特别有效，因为到处都在创建字符串，但我的目的是为了清晰而不是优化。

在 Ruby 中，我可以做这样的事情，感觉更优雅：

但是由于 Java 缺少连接命令，所以我想不出任何等效的东西。

那么，在 Java 中执行此操作的最佳方法是什么？

什么是一种非递归算法，用于确定是否可以从一组数字中加法构建传入的数量。
就我而言，我正在确定是否可以通过将一组钞票（例如 5 美元、10 美元和 20 美元钞票）的某种组合相加来满足某个货币金额（例如 40 美元）。这是一个简单的例子，但算法需要适用于任何货币集（一些货币使用时髦的账单金额，而一些账单可能在给定时间不可用）。
所以 50 美元可以用一组（20 美元和 30 美元）来满足，但不能用一组（20 美元和 40 美元）来满足。非递归要求是由于目标代码库用于SQL Server 2000递归支持有限的地方。
此外，这是为了支持多币种环境，其中可用的账单集可能会发生变化（例如外币兑换柜员）。