Tag: 数据结构

后缀数组algorithm

在阅读了一段时间之后，我已经想出了一个后缀数组和LCP数组代表了什么。 后缀数组 ：表示数组中每个后缀的_lexicographic等级。 LCP数组 ：包含两个连续后缀之间的最大长度前缀匹配， 按照字典顺序sorting 。 我已经努力了解了几天， 后缀数组和LCPalgorithm的工作原理。 这是从Codeforces获取的代码： /* Suffix array O(n lg^2 n) LCP table O(n) */ #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define REP(i, n) for (int i = 0; i < (int)(n); ++i) namespace SuffixArray { const int MAXN = 1 << 21; char * S; int […]

什么是C中的内存有效的双链表？

在阅读关于C数据结构的书时，我遇到了“Memory-Efficient Doubly Linked List”这个术语。 它只有一行说，一个内存有效的双向链表比正常的双向链表使用更less的内存，但是做同样的工作。 没有更多的解释，也没有例子。 只是有人认为，这是从一本杂志，“支架”中的“辛哈”。 在Google上search之后，我最接近的就是这个 。 但是，我什么都不懂。 有人可以解释我什么是在C内存有效双向链接列表？ 它和正常的双链表有什么不同？ 编辑：好吧，我犯了一个严重的错误。 看到我上面贴出的链接，是文章的第二页。 我没有看到有第一页，并认为给出的链接是第一页。 文章的第一页实际上给出了解释，但我不认为它是完美的。 它只讨论了内存有效链接列表或异或链接列表的基本概念。

用于检测点“簇”的algorithm

我有一个分布在这个区域的“点”的2D区域。 我现在正在尝试检测点的“簇”，即具有一定高密度点的区域。 任何想法（或带有想法的文章的链接）如何优雅地检测这些区域？

二进制堆的有效实现

我在寻找如何有效地实现二进制堆的信息 。 我觉得应该有一个好的文章有关实施堆，但我还没有find一个。 事实上我一直没有find任何有关如何将数据堆存储在基础之上的有效实现方面的资源。 我正在寻找制作快速二进制堆的技术，超出了我在下面描述的范围。 我已经写了一个比Microsoft Visual C ++和GCC的std :: priority_queue更快的C ++实现，或者使用std :: make_heap，std :: push_heap和std :: pop_heap。 以下是我在实现中已经涉及到的技术。 我自己只提出了最后两个，但我怀疑这些是新的想法： （编辑：增加内存优化部分） 从1开始索引 查看二维堆的维基百科实现注释 。 如果堆的根位于索引0处，则索引n处的父节点，左节点和右节点的公式分别为（n-1）/ 2,2n + 1和2n + 2。 如果使用基于1的数组，那么公式将变得更简单n / 2，2n和2n + 1.因此，在使用基于1的数组时，父项和左项是更高效的。 如果p指向一个基于0的数组，并且q = p-1，那么我们可以像q [1]那样访问p [0]，所以在使用基于1的数组时没有开销。 在更换叶子之前，将popup/移除元素移到堆的底部 在一个堆上popup通常是通过replace最左边的底部叶子的顶部元素，然后将其向下移动直到堆属性被恢复来描述。 这要求每个级别进行2次比较，而且我们可能会在堆栈顶部移动一个叶子，因此可能会走得很远。 所以我们应该期望有less于2个log n的比较。 相反，我们可以在堆顶部留下一个洞。 然后，我们通过迭代地将更大的孩子向上移动，将这个洞向下移动。 这只需要我们通过每个级别1比较。 这样孔就会变成一片叶子。 在这一点上，我们可以将最右边的底部叶子移动到洞的位置，并移动该值直到堆属性恢复。 既然我们移动的价值是一片叶子，我们不期望它移动到树上很远。 所以我们应该期待比log n比较多一点，这比以前更好。 支持replace顶部 假设你想删除最大的元素，并插入一个新的元素。 […]

拼字游戏瓷砖检查

拼字检查瓷砖，你做四个5×5的字母总共100个瓷砖。 我想做一个所有40个水平和垂直的单词是有效的。 可用拼贴的集合包含： 12×E 9 x A，I 8 x O 6×N，R，T 4 x D，L，S，U 3 x G 2×B，C，F，H，M，P，V，W，Y，空白瓦（通配符） 1×K，J，Q，X，Z 有效单词字典在这里可以find （700KB）。 大约有12000个有效的5个字母的单词。 下面是一个例子，其中所有20个水平字都是有效的： ZOWIE|PINOT YOGIN|OC t AD <= blank being used as 't' XEBEC|NALED WAITE|MERLE VINER|LUTEA ———+——— USNEA|KNOSP TAVER|JOLED SOFTA|IAMBI RIDGY|HAIT h <= blank being used as 'h' QURSH|GROUF 我想创build一个所有的垂直的也是有效的。 你能帮我解决吗？ 这不是功课。 这是一个朋友问我帮忙的问题。

你如何代表魔方：

如果你正在开发软件来解决魔方问题，你将如何表示魔方？

什么时候使用Preorder，Postorder和Inorder二叉search树遍历策略

我最近意识到，虽然在我的生活中使用了BST的丰富，但我从来没有想过使用除Inorder遍历之外的任何东西（虽然我意识到并知道如何使程序适应前/后顺序遍历）。 在意识到这一点之后，我拿出了一些旧的数据结构教科书，并在前序遍历和后序遍历的有用性之后寻找推理 – 虽然他们没有多说。 实际上什么时候使用前序/后序？ 什么时候比有序更有意义？

Java支持结构吗？

Java是否具有C ++ struct的模拟： struct Member { string FirstName; string LastName; int BirthYear; }; 我需要使用我自己的数据types。

为Objective-C集合实现-hash / -isEqual：/ -isEqualTo …：

注意：下面的SO问题是相关的，但是他们和链接的资源似乎都不能完全回答我的问题，特别是在实现对象集合的平等testing方面。 覆盖-isEqual和-hash的最佳实践 在可变的cocoa对象上实现-hash的技巧 背景 NSObject提供了默认的实现-hash （它返回实例的地址，比如(NSUInteger)self ）和-isEqual:除非接收者的地址和参数相同，否则返回NO 。 这些方法被devise为根据需要被覆盖，但是文档清楚地表明你应该提供或者不提供。 此外，如果-isEqual:对于两个对象返回YES ，则这些对象的-hash结果必须相同。 如果不是这样，那么当对象应该是相同的，比如两个string实例（其中的NSOrderedSame -compare: returns NSOrderedSame ）被添加到Cocoa集合中，或者直接进行比较时，问题会随之而来。 上下文 我开发了CHDataStructures.framework ，一个Objective-C数据结构的开源库。 我已经实现了一些集合，并且正在改进和增强它们的function。 我想要添加的function之一是能够比较集合的平等与另一个。 这些比较应该考虑两个集合中存在的对象（包括sorting，如果适用），而不是只比较内存地址。 这种方法在cocoa中有相当的先例，并且通常使用一种单独的方法，包括以下方法： -[NSArray isEqualToArray:] -[NSDate isEqualToDate:] -[NSDictionary isEqualToDictionary:] -[NSNumber isEqualToNumber:] -[NSSet isEqualToSet:] -[NSString isEqualToString:] -[NSValue isEqualToValue:] 我想使自定义集合对于相等性testing的健壮性，所以他们可以安全地（可预测地）将其添加到其他集合中，并允许其他集合（如NSSet）确定两个集合是否相等/等同/重复。 问题 一个-isEqualTo…:方法可以很好地工作，但是定义这些方法的类通常也会覆盖-isEqual:如果参数是相同的类（或者可能是子类），则调用[self isEqualTo…:]接收者，否则[super isEqual:] 。 这意味着该类还必须定义-hash ，以便为具有相同内容的不同实例返回相同的值。 另外，苹果的-hash文件规定如下:(强调我的） “如果将可变对象添加到使用散列值确定对象在集合中的位置的集合中，则在对象位于集合中时，由对象的散列方法返回的值不得更改，因此无论是散列方法不能依赖任何对象的内部状态信息， 或者当对象位于集合中时，必须确保对象的内部状态信息不发生变化。因此，例如，可以将可变字典放在哈希表中，但必须而不是在它那里改变它（注意可能很难知道一个给定的对象是否在一个集合中）。“ 编辑： 我当然明白为什么这是必要的，并完全同意推理 – 我在这里提到它提供了额外的背景，并且为了简洁起见跳过为什么是这样的话题。 我所有的集合都是可变的，哈希将不得不考虑至less一些内容，所以这里唯一的select是将其存储在另一个集合中的集合进行变异时，将其视为编程错误。 （我的集合都采用NSCopying ，所以像NSDictionary集合可以成功地作为一个副本作为一个键等） […]

如果磁盘上的数据集为1 TB，每个数据logging约为1 KB，那么如何使用512 MB RAM和无限磁盘空间来查找重复数据？

磁盘上有1 TB数据，每个数据logging大约1 KB。 如何使用512 MB RAM和无限磁盘空间查找重复项？