Data Structures 群控编程网

弗洛伊德循环检测

问题：给定一个链表，检测其中是否有任何循环。解决此问题的方法很多，但就复杂性而言，弗洛伊德循环检测算法比其他算法更有效。空间复杂度：O（1）时间复杂度：O（n）在这里，您使用2个指针，其中1个以1的速度移动，另一个以2的速度移动。如果有一个周期，则这2个指针将彼此相遇；如果不是一个周期，则快速指针将遇到null。这是科特林的一个例子。私人乐趣isCycle（node：Node）：布尔{ var陆龟：节点？ =节点 var hare：节点？ =节点 while（hare！= null && hare.next！= null）{ 乌龟=乌龟!!。nextNode 兔子=兔子!!。nextNode…

如何在C中使用结构和数组演示散列及其在初学者中的应用：简易方法-第4部分（链式）

这是有关散列和散列冲突的文章系列的第四篇也是最后一部分，前三部分是清楚理解本部分并处理较早概念的前提，可以在下面的链接中找到这些概念。哈希：Part1哈希的应用：演示Part2哈希冲突：Part3 在第3部分中，讨论了哈希冲突和开放寻址下解决冲突的各种方法。在本文中，通过演示示例详细讨论了通过链解决冲突。链接是哈希解析的一种非常简单的方法，在此方法中，冲突键存储为链接列表，哈希值用作哈希表的索引。简单来说，具有相同散列值的所有键都存储为链接列表，并且基于散列表中的散列值存储链接列表的根/头。因此，在发生冲突的情况下，会将新节点插入到链表中，基于哈希值从哈希表中获取头/根值。因此，基本上，哈希表可以看作是许多链接列表的根的数组，并且具有相同哈希值的所有键都将进入同一链接列表。继续我们先前的演示应用程序，在m = 11的乘法哈希处理中，滚动号136001和136009都产生相同的哈希值2。不同的冲突解决方法存储的136009记录不同，但索引与哈希值不同。现在，在链接这些记录并创建一个链表时，此链表的头将存储在基于哈希值即2的哈希表的索引2处。实作链接方法的实现与单链表非常相似。以下是两个示例，第一个示例演示如何使用链接存储记录，然后全部打印它们，第二个示例演示基于键的特定记录搜索。随着本系列的散列工作的结束。请写出任何建议或改进。

短代码：在Python中反转二叉树

“谷歌：我们90％的工程师都使用您编写的软件（Homebrew），但您无法在白板上倒置二叉树，因此无法使用。” —马克斯·豪威尔（Max Howell）问题定义倒置二叉树可以认为是获取输入树的镜像。 Leetcode上给出的示例显示了一个输入树： 4 / \ 2 7 /// 1 3 6 9 当倒置时，会给出： 4…

假人的数据结构：二叉搜索树

假设您正在对数据库进行编程，以保存一个国家公民的基本信息-大约有1亿个数据条目。如果要使用链表或数组来存储此数据，则搜索条目所需的学习时间为O（n ），插入新条目的时间为常数O（1），线性时间为O（n））删除条目。（有关大O表示法如何工作的更多信息，请阅读本系列中有关链表的上一篇文章！我还将介绍本文中将使用的大多数基本概念。）让我们考虑对排序数组执行搜索功能的成本（排序意味着数据已按时间顺序排列）。如果比较一百万个条目大约需要一秒钟，这意味着在最坏的情况下，搜索整个数据库大约需要100秒。对于可能每天执行多次的基本操作而言，这太长了。我们如何缩短这个时间？在本文中，我们将探讨二进制搜索树，它们的基本结构，它们的特征以及如何自己编写代码。我们还将尝试了解它们如何成为此问题的可能解决方案。结构体二叉搜索树是一种二叉树，其中根节点（位于树顶部的第一个节点）的左子树上的所有子节点具有较小的值，而a的右子树上的所有子节点具有较小的值。根节点具有更大的值。因此，在上面的示例中，我们看到根节点为25。…

掌握Ruby中的数据结构-双链表

单链表和双链表之间的主要区别在于，在后面的每个元素都包含一个指向其前面元素的指针。这使我们可以从尾到头遍历列表，并在固定时间内删除元素。如果您还没有阅读我以前关于单链列表的文章，建议您这样做，因为这一次我们将在上次构建的内容的基础上进行工作。在双向链表上，元素由包含三个属性的节点表示：元素保存的值。指向列表中下一个节点的指针。指向列表中上一个节点的指针。与单链列表一样，列表的第一个元素称为“ head”，最后一个元素称为“ tail”。双向链表的边界由第一个元素的上一个指针和最后一个元素的下一个指针界定。两个指针都必须设置为nil。 X <-[prev|data|next] [prev|data|next] [prev|data|next] ->…

菲尔的数据结构动物园

以编程方式解决问题通常涉及将数据项分组在一起，以便可以方便地对它们进行操作或将其复制为单个单元-将这些项收集在数据结构中。在过去的几十年中，已经设计了许多不同的数据结构，其中一些存储单个项目，例如电话号码，另一些存储更复杂的对象，例如名称/电话号码对。每个都有优点和缺点，或多或少适合特定的用例。在本文中，我将描述并尝试按三种不同的摘要级别对一些最流行的数据结构及其实际实现进行分类，这些层次从柏拉图式理想开始，以基准测试的实际代码结束：理论级别：无论具体实现如何，都将描述数据结构/收集类型，并列出其核心操作的渐近行为。实现级别：将显示特定编程语言的容器类如何与上一级别引入的数据结构相关联-例如，尽管名称相似，但Java的Vector与Scala或Clojure的Vector实现不同。另外，将为每个实现类提供核心操作的渐进复杂性。经验级别：将测量数据结构效率的两个方面：将在不同配置下确定容器类的内存占用量。将测量操作的运行时性能，这将证明渐进优势的扩展体现在具体场景中，以及渐近相等结构的相对性能是什么。在第三部分中提供实际的速度和空间测量结果之前，可以根据数据结构可能存储的项数以抽象的方式描述执行时间和空间。传统上，这是通过Big O表示法完成的，并且在表中使用以下缩写： C是恒定时间O（1） aC摊销固定时间 eC是有效的恒定时间对数是对数时间，O（log…

编程不仅仅是学习语法。

作为程序员，您应该了解在应用程序中使用的编程库。使用Java，C＃，scala，python等都无关紧要。假设您在应用程序中使用HashMap。如果您不希望了解哈希映射的工作原理，那么您将永远无法理解它在内部的工作原理？哈希如何工作？哈希是编程中一种很棒的方法，可以极大地提高应用程序的性能。然后，您不知道它们如何在新的哈希映射（基本上使用二叉树）中提高性能。也就是说，您永远不会想到在任何地方使用哈希。这可以用来改善现实世界中停车系统的拥挤状况。这是非常小的简单示例。我不是说只是阅读集合或内部类，而不是做更多的事情。编程不仅仅是学习语法。阅读各种算法（例如图形，树，搜索等），了解各种数据结构。当您学习这些东西时，您将能够将现实世界中的问题与您的学习联系起来，并能够提出最佳解决方案。现在如何学习这些使您成为一名出色的程序员？作为程序员，您不仅会想要为给定的问题编写解决方案。您将要编写最佳解决方案。它应该在各种情况下为您提供最佳性能。…

Java链表数据结构的5分钟初学者指南

链表通常用于实现其他数据结构，例如堆栈，队列和树，是线性数据结构。链表形成了可以被视为链链的位置，是一个节点序列。每个节点都存储自己的数据和指向下一个节点位置的指针（地址）。链接列表中的最后一个链接指向null，表示链的末尾。尽管链表的顺序和顺序类似于数组，但是链表不限于声明的元素数。同样与数组不同，在数组中每个数组元素都是连续存储的（每个元素都有一个连续的内存地址），而链表元素不是连续存储的。因此，与数组相反，可以在不重新分配内存的情况下插入和删除链接列表元素。 Big-O表示法是描述（和比较）算法（或在这种情况下，数据结构）执行某项任务需要多少操作的一种方式。访问对象的成本：数组== O（1）与链表== O（N）插入/删除的费用：数组== O（N）与链表==…

掌握Ruby中的数据结构-单链接列表

单链列表是一种数据结构，它使我们能够管理大小可变的元素集合。与C样式数组不同，单链接列表可以根据它们必须存储的对象数量来动态增长或收缩。此属性使它们非常适合那些元素数事先未知的情况。链表中的每个元素都由一个节点表示，该节点包含两个属性：元素保存的值。指向列表中下一个节点的指针。列表的第一个节点称为“ head”，最后一个节点称为“ tail”。要标记列表的末尾，必须将尾节点的下一个指针设置为nil。 [值| 下一个]-> [值| 下一个]-> [值| 下一个]-> X（无）要从单链列表中获取元素，您必须从头到尾遍历该元素。…

一致性哈希：分布式哈希问题的替代方法。

分布式哈希：在某些情况下，可能有必要将哈希表拆分为几个部分，由不同的服务器/计算机维护，这解决了单个计算机/服务器上的内存限制问题，还可以创建任意大的哈希表。这就是所谓的分布式哈希。每个密钥都映射到特定的服务器，例如，哈希= HashFunc（key）服务器/索引=哈希mod（N）其中N是服务器数。分布式哈希是一个简单可行的解决方案，直到服务器宕机/更改。在这种情况下，需要重新分配密钥以解决更改。但是我们知道，托管在不同服务器中的密钥是基于N（没有服务器）来计算的。因此，随着N的变化（即，如果服务器关闭或添加了新服务器），必须与新的N对应地重新映射所有密钥。这会导致性能严重下降，并可能使现有正在运行的服务器崩溃。引入一致性哈希作为上述问题的替代方案/解决方案。一致哈希：一致哈希是一种特殊的哈希，其中，当必须调整哈希表的大小时，平均仅需要重新映射k / n个键，其中k是键的数量，n是服务器的数量。…