问题标签 [clrs]

假设我们希望跟踪一组区间中的最大重叠点——数据库中与它重叠的区间数最多的点。

一种。表明总会有一个最大重叠点，它是其中一个线段的端点。

湾。设计一个有效支持操作 INTERVAL-INSERT、INTERVAL-DELETE 和 FIND-POM 的数据结构，该操作返回最大重叠点。（提示：保留所有端点的红黑树。将 +1 值与每个左端点相关联，并将 -1 值与每个右端点相关联。用一些额外信息来扩充树的每个节点以维护最大重叠点。）

这个问题在《算法介绍》一书中。但我不知道如何解决第二个问题。如果一个更伟大的头脑有一个优雅的解决方案，请与我分享你的想法！谢谢。

我已经阅读并搜索了 Floyd Warshall 算法，我想我理解它。但是在我在“算法简介（Thomas H. Cormen 的书）”一书中读到的示例中，我堆叠在一个点上。我很困惑。这是书中相同的图片。我的问题在最后一步，即 π(5)。这是示例：http: //integrator-crimea.com/images/fig653_01_0.jpg

有人可以解决我上面的困惑吗？书上写错了吗？

以下动态集操作的渐近最坏情况运行时间是多少？

Successor(L,x) 用于未排序的单链和双链表

Predecessor(L,x) 用于未排序的双向链表

L：列表，x：指向条目的指针

（实际上这是本书问题10-1的一部分：“算法简介，第三版”，我搜索了答案，答案是O（n）但我找不到任何解释）

这是完整的问题：

假设我们有一个有向图 G = (V,E)，我们想找到一个图 G' = (V,E')，它具有以下属性：

1. G' 具有与 G 相同的连通分量
2. G' 与 G 具有相同的分量图
3. E' 被最小化。也就是说，E' 尽可能小。

这是我得到的：

首先，运行强连通分量算法。现在我们有了强连接的组件。现在转到每个强连接组件，并在该 SCC 内做一个简单的循环；也就是说，唯一重复的节点是开始/结束节点的循环。这将最小化每个 SCC内的边缘。

现在，我们需要最小化SCC之间的边缘。唉，我想不出这样做的方法。

我的两个问题是：（1）关于最小化SCC之间边缘的部分之前的算法听起来正确吗？(2) 如何最小化 SCC 之间的边缘。

对于 (2)，我知道这相当于最小化 DAG 中的边数。（将 SCC 视为顶点）。但这似乎对我没有帮助。

在 CLRS 第 2 版，第 4 次印刷，第 288-9 页之后，我正在为区间树实现红黑树删除。

错误总结：

RB-删除-修复

如果 x 和 w 是标记节点，这是 RB-Delete 的可能结果，则分别评估 color(left(w))。RB-Delete-Fixup 中的 color(right(w)) 在 while 循环的第一次迭代中遇到空指针异常。

这个问题的所有代码都在 Clojure 中：

https://github.com/mobiusinversion/interval-trees

这是抛出异常时的红黑树状态图：

http://gorillamatrix.com/files/rb-delete-fixup.jpg

失败的单元测试是

在文件中

以下是 lein test 的输出：

问题似乎是在分配之后

CLRS, pg. 289 rb-delete-fixup 伪代码第7行，w指向sentinel节点，因此伪代码第9行没有左右检查颜色。

Clojure 实现中抛出异常的行在这里

勘误表中似乎没有提交错误：

http://www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-2e.php

我很抱歉这个问题非常具体和密集，但非常感谢您的帮助，我已经为此苦苦思索了好几天。

看来这个人问了同样的问题，但没有得到答案 红黑树删除算法

更新：我在第三版第三版中实现了delete和delete fixups例程，但未能解决问题。

这是 CLR (Introduction to Algorithms) 的问题，问题如下：

假设每个快速排序级别的拆分比例为 1 - α 与 α，其中 0 < α ≤ 1/2 是一个常数。证明递归树中叶子的最小深度约为 -lg n/ lg α，最大深度约为 -lg n/ lg(1 - α)。（不用担心整数舍入。）http://integrator-crimea.com/ddu0043.html

我不知道如何达到这个解决方案。根据链接，他们表明对于 1:9 的比率，最大深度是 log n/log(10/9) 和最小 log n/log(10)。那么如何证明上述公式。由于我是算法和数据结构课程的新手，请帮助我了解我哪里出错了。

Theorem 22.10 in CLRS - Introduction to Algorithms说

在无向图 G 的深度优先搜索中，G 的每条边要么是树边，要么是后边。

现在在这里对树边缘部分的解释很明显，但我没有得到后边缘部分。例如：- 取一个无向图，使得

1----2----3

现在，如果首先探索边 1-2 使得 d 1 < d[2]，那么边 1-2 将是树边。现在因为这是一个无向图，所以我们可以说边 2-1 是图中的后边 (d[2] > d 1 ) 吗？

我没有掌握这个后缘的窍门。

给定：整数数组 K,M

问题：找到我们可以从给定数组的所有 K 个元素子集中获得的最大和，使得和小于值 M？

这个问题有可用的非动态编程解决方案吗？或者如果只有 dp[i][j][k] 只能解决这类问题！你能解释一下算法吗？

这是来自 CLRS 的数论章节。

我们被要求证明a/b带有结果q和提示的二进制“纸和铅笔”长除法r对O((1+lgq)lgb)位进行操作。

我看到它的方式是我们b对q. 因此，假设减法b执行lgb操作（对于 中的每个位一个b），那么我们总共有O(lgblgq)操作，这不是所要求的。

如果您考虑到您执行的第一个减法运算可能会导致 0 位（例如，将 100b 除以 11b），那么，好的，您可以加 1lgq来补偿这个减法。但是......减法本身也可以这样说 - 它可以进行lgb运算，也可以lg(b)+1根据数字进行运算（在 100b 和 11b 示例中，第二次减法将是 100b-11b 需要 3 次运算才能完成） .

所以如果我们考虑这些情况，那么操作的数量应该是O((1+lgb)(1+lgq)).

所以问题是，你怎么能证明这个部门有O((1+lgq)lgb)行动呢？

CLRS - 第 22 章

定理 22.10

在无向图 G 的深度优先搜索中，G 的每条边要么是树边，要么是后边。

证明 假设 (u,v) 是 G 的任意边，并且不失一般性地假设 ud < vd 那么搜索必须在完成 u 之前发现并完成 v（而 u 是灰色的），因为 v 在 u 的邻接表上. 如果搜索第一次探索边缘 (u,v)，它是在从 u 到 v 的方向上，那么在那个时间之前 v 是未被发现的（白色），否则搜索将已经在从v 给你。因此，(uv) 变成了树的边缘。如果搜索首先沿从 v 到 u 的方向探索 (u,v)，则 (u,v) 是后边缘，因为在第一次探索边缘时 u 仍然是灰色的。

我当然明白证明；但不太相信前沿的想法。

在上图中，从第一个顶点到第三个顶点（第一行）有一条前向边。第一个顶点是源。

据我了解，DFS(S) 将包括一个前向顶点 1 -> 3。（我显然错了，但我需要有人来纠正我！）