问题标签 [puzzle]

到目前为止我最好的镜头：

运送车辆需要进行一系列运送（d ₁ ,d ₂ ,...d _n），并且可以按任何顺序进行 - 换句话说，集合 D = {d ₁的所有可能排列， d ₂ ,...d _n } 是有效的解决方案——但具体的解决方案需要在路线的一端离开基站之前确定（假设需要在车辆 LIFO 中装载包裹，例如）。

此外，各种排列的成本也不相同。_{它可以计算为 d i -1}和 d _i之间行进距离的平方和，其中 d ₀被视为基站，但需要注意的是，任何涉及方向改变的段的成本是其 3 倍（想象一下这是在铁路或气动管上发生的，并且备份会干扰其他交通）。

给定一组传递D表示为它们与基站的距离（所以abs(d_i -d_j)是两个传递之间的距离）和一个permutations(D)将连续产生每个排列的迭代器，找到一个成本小于或等于任何排列的排列其他排列。

现在，从这个描述中直接实现可能会导致这样的代码：

这是 O(n*n!^2)，例如非常糟糕——尤其是与有洞察力的人通过简单地对 D 进行排序会发现的 O(n log(n)) 相比。

我的问题：你能想出一个合理的问题描述，它自然会导致粗心的人进入更糟糕（或不同程度糟糕）的排序算法实现吗？

在 Douglas Hofstader 的 Godel, Escher, Bach 的第 8 章中，读者面临着将这两个陈述翻译成 TNT 的挑战：

“b 是 2 的幂”

和

“b 是 10 的幂”

以下答案是否正确？：

（假设 '∃' 表示'存在一个数字'）：

∃x:(xx = b)

即“存在一个数字'x'使得x乘以x等于b”

如果这是正确的，那么下一个同样微不足道：

∃x:(xxxxxxxxxx = b)

我很困惑，因为作者指出它们很棘手，第二个需要几个小时才能解决；我一定在这里错过了一些明显的东西，但我看不到它！

如何在 C 中找到数字（从 1 到 10）的阶乘，而不使用：

• for、while 和 do while 等循环语句；
• 条件运算符，例如 if 和 case；和
• 算术运算符，如 + 、 − 、 * 、 % 、 / 、 ++ 、 −−?

仅供参考：我在 C aptitude 中发现了这个问题。

Joel 在他的Guerrilla Guide to Interviewing中提到计算一个字节中设置的位数是一个编程问题，并谈到了一种利用查找表中出现的模式的方法。在我找到模式后不久，我写了一篇关于它的文章。

总结一下：

第一行和第一列完全相同，网格中的每个位置都可以通过将该位置的行和列中的第一个值相加来计算。因此，对于一个 8 位数字，您只需要一个包含 16 个条目的查找表，并且可以只使用前 16 个数字。然后，如果您想计算数字 243 中的设置位，例如，您只需执行以下操作：

之后我注意到的下一个模式是，每次将 NxN 网格的大小加倍时，每个象限都可以通过分别向每个象限添加 0、1、1 和 2 来计算，如下所示：

再重复这个过程两次，你会从上面得到 16x16 的网格，所以我想一定有某种四叉树算法可以让你从网格开始：

并给定一个数字 N，动态生成查找表并计算出位数。所以我的问题/挑战是，你能想出一个算法来做到这一点吗？

我有一个 X x Y 大小的面板。我想在这个面板上放置最多 N 个随机大小的矩形，但我不希望它们中的任何一个重叠。我需要知道这些矩形的 X、Y 位置。

算法，有人吗？

编辑：所有 N 个矩形一开始都是已知的，可以按任何顺序选择。这会改变程序吗？

最近我一直在我的 iPhone 上玩一个名为 Scramble 的游戏。你们中的一些人可能将这款游戏称为 Boggle。本质上，当游戏开始时，您会得到一个字母矩阵，如下所示：

游戏的目标是找到尽可能多的单词，这些单词可以通过将字母链接在一起形成。您可以从任何字母开始，并且围绕它的所有字母都是公平的游戏，然后一旦您继续下一个字母，围绕该字母的所有字母都是公平的游戏，除了以前使用的任何字母。因此，例如，在上面的网格中，我可以想出单词LOB、TUX、SEA、FAME等。单词必须至少为 3 个字符，并且不超过 NxN 个字符，在这个游戏中为 16，但在某些实现中可能会有所不同. 虽然这个游戏很有趣而且让人上瘾，但我显然不太擅长它，我想通过制作一个可以给我最好的单词的程序来作弊（单词越长，你得到的分数越多）。

_{（来源：boggled.org）}

不幸的是，我不太擅长算法或其效率等等。我的第一次尝试使用了这样的字典（~2.3MB），并进行了线性搜索，试图将组合与字典条目进行匹配。这需要很长时间才能找到可能的单词，而且由于每轮只有 2 分钟，这根本不够。

我有兴趣看看是否有任何 Stackoverflowers 可以提出更有效的解决方案。我主要在寻找使用 Big 3 Ps 的解决方案：Python、PHP 和 Perl，尽管使用 Java 或 C++ 的任何东西也很酷，因为速度是必不可少的。

当前解决方案：

• 亚当·罗森菲尔德，Python，~20 多岁
• John Fouhy，Python，~3s
• Kent Fredric, Perl, ~1s
• Darius Bacon, Python, ~1s
• rvarcher, VB.NET, ~1s
• Paolo Bergantino, PHP (live link) , ~5s (~2s local)

我最近在一次工作面试中被要求解决一个我认为分享会很有趣的编程难题。这是关于将 Excel 列字母转换为实际数字，如果你还记得的话，Excel 用从 A 到 Z 的字母命名它的列，然后序列为 AA、AB、AC... AZ、BA、BB 等。

您必须编写一个接受字符串作为参数的函数（如“AABCCE”）并返回实际的列号。

解决方案可以是任何语言。

好的，以示例为目标：执行此操作的命令行应用程序：

倒计时.exe 7

打印 7 6 5 4 3 2 1

不允许任何形式的减法（包括使用减号）或字符串反转。

waaaaay 显然太容易了 :-) 答案概述（至少是原则）

1. 通过添加和递归
2. 通过使用模
3. 通过推动和弹出，（也许是最明显的？）
4. 通过使用溢出
5. 通过反复试验（也许是最不明显的？）

当我阅读本文时（在数组中查找最常见的条目），建议使用Boyer 和 Moore 的线性时间投票算法。

如果您点击该网站的链接，则会逐步解释该算法的工作原理。对于给定的序列，AAACCBBCCCBCC它提供了正确的解决方案。

当我们将指针向前移动到元素 e 上时：

• 如果计数器为 0，我们将当前候选设置为 e，并将计数器设置为 1。
• 如果计数器不为 0，我们根据 e 是否是当前候选者来增加或减少计数器。

完成后，如果有多数，则当前候选人是多数元素。

如果我在一张纸上使用这个算法AAACCBB作为输入，建议的候选人将变成 B，这显然是错误的。

在我看来，有两种可能

1. 作者从未在任何其他方面尝试过他们的算法AAACCBBCCCBCC，完全无能，应该当场解雇（怀疑）。
2. 我显然遗漏了一些东西，必须从 Stackoverflow 被禁止，并且永远不能再接触任何涉及逻辑的东西。

注意：这是来自 Niek Sanders的算法的 C++ 实现。我相信他正确地实现了这个想法，因此它有同样的问题（或者不是吗？）。

我想让这个挑战引起 stackoverflow 社区的注意。原来的问题和答案都在这里。BTW，如果你以前没有关注过，你应该尝试阅读 Eric 的博客，这是纯粹的智慧。

概括：

编写一个函数，它接受一个非空 IEnumerable 并返回一个具有以下特征的字符串：

1. 如果序列为空，则结果字符串为“{}”。
2. 如果序列是单个项目“ABC”，则结果字符串为“{ABC}”。
3. 如果序列是两个项目序列“ABC”、“DEF”，则结果字符串为“{ABC 和 DEF}”。
4. 如果序列有两个以上的项目，比如“ABC”、“DEF”、“G”、“H”，那么结果字符串是“{ABC, DEF, G and H}”。（注意：没有牛津逗号！）

正如您所看到的，甚至我们自己的 Jon Skeet（是的，众所周知，他可以同时在两个地方）发布了一个解决方案，但他的（恕我直言）并不是最优雅的，尽管您可能无法击败它表现。

你怎么看？那里有很多不错的选择。我真的很喜欢涉及选择和聚合方法的解决方案之一（来自 Fernando Nicolet）。Linq 非常强大，花一些时间来应对这样的挑战会让你学到很多东西。我稍微扭曲了它，让它更高效更清晰（通过使用 Count 并避免 Reverse）：