问题标签 [programming-pearls]

第 2 栏（“啊哈！算法”）中的“编程珍珠”讨论了二分搜索如何帮助排序、树遍历等各种过程。但它提到二进制搜索可以用于“程序调试”。有人可以解释一下这是怎么做到的吗？

M个位置的圆移阵列最快的算法是什么？
例如，[3 4 5 2 3 1 4]移位 M = 2 个位置应该是[1 4 3 4 5 2 3]。

非常感谢。

Jon Bentley 在他的书 Programming Pearls 的第 1 列中介绍了一种使用位向量对非零正整数序列进行排序的技术。

我从这里获取了程序 bitsort.c并将其粘贴在下面：

我了解 clr、set 和 test 的功能并在下面解释它们：（如果我在这里错了，请纠正我）。

• clr 清除第 i 位
• set 设置第 i 位
• 测试返回第 i 位的值

现在，我不明白这些功能是如何做的。我无法弄清楚这三个函数中发生的所有位操作。

只是我还是Programming Pearls中的这段代码是错误的（quicksort 需要 2 个 const void，不是吗？）如果是这样，我的解决方案是否正确？抱歉，学习了...

这是一个解决方案吗？

我想知道是否有人知道最长重复不重叠子字符串的（最佳？）算法。

例如，在字符串

阿巴泽德巴德兹

最长的重复将是“坏”。顺便说一句，如果没有这样的结果，算法应该提醒这样的事情已经发生。我的猜测是这涉及后缀树。

我确定这一定已经存在于某个地方。谢谢您的帮助！

这是 中描述的问题Programming pearls。我无法理解作者描述的二进制搜索方法。谁能帮忙详细说明一下？谢谢。

编辑：我一般可以理解二进制搜索。我只是不明白如何在这种特殊情况下应用二进制搜索。如何确定丢失的数字是否在某个范围内，以便我们可以选择另一个。英语不是我的母语，这也是我不能很好理解作者的原因之一。所以，请使用简单的英语:)

编辑：谢谢大家的精彩回答和评论！我从解决这个问题中学到的最重要的一课是二进制搜索不仅适用于排序数组！

编程珍珠第8栏发现的问题如下：

给定实向量 x[n]，计算在任何连续子向量中找到的最大和。

提供的最终解决方案具有 O(n) 复杂度，如下所示：

我想知道如何修改上述算法以提供最小总和。

我似乎无法理解这将如何工作。

问题：
给定一个包含最多 40 亿个随机顺序的 32 位整数的顺序文件，找到一个不在文件中的 32 位整数（并且必须至少缺少一个）

回答：
根据表示每个整数的 32 位来查看这种二分搜索会很有帮助。在算法的第一遍中，我们读取（最多）40 亿个输入整数，并将具有前导零位的整数写入一个顺序文件，将前导一位的整数写入另一个文件。

其中一个文件最多包含 20 亿个整数，因此我们接下来使用该文件作为当前输入并重复探测过程，但这次是在第二位。

因此，通过一遍又一遍地拆分文件（二进制搜索），这实际上会如何导致我找到丢失的 32 位整数？

在2.6节和问题2中，原来的问题是这样的：

“给定一个包含 4,300,000,000 个 32 位整数的顺序文件，你如何找到至少出现两次的文件？”

我对这个练习的问题是：上述问题的技巧是什么，这个问题属于哪种一般算法类别？

我们都听说过解决最大子序列和的宾利美丽的编程珍珠问题：

如果我们添加一个小于 M 的附加条件最大子序列怎么办？