Tag: 数据结构

数据结构(基础知识)

数据结构是解决算法问题的有用工具。 您可能熟悉的两个数据结构是数组和字典。 数组具有内置的函数,可让您解决问题。 您可以对数组进行计数,对数组进行排序,将项目追加到数组中,在数组中的项目之间循环等等。类似地,您可以将键值对插入字典中,从字典中提取键值对,等等。 ,队列和树是另外三个对您的代码工具箱有用的数据结构。 堆栈 堆栈有助于按特定顺序组织数据。 堆栈可归为三大功能: 推动将新元素添加到堆栈顶部 弹出以从堆栈顶部删除元素 窥视堆栈顶部而不弹出 与您放在桌上的一堆纸类似,添加到纸堆中的最后一个元素是可以从纸堆中删除的第一个元素。 另外,就像您只能看到桌子上纸叠顶部的纸上内容一样,您也只能看到编码纸叠中的顶部元素。 如果使用字符串,上面的示例很好,但是如果要使用其他类型,该怎么办? 没有恐惧! 泛型在这里! 使用泛型堆栈 s列 类似于堆栈,队列有助于按特定顺序组织数据。 与邮局在队列中等待的第一个人是第一个离开队列并得到服务的人一样,代码队列中的第一个元素也是第一个离开队列的元素。 队列可归为三大功能: 排队将新元素添加到队列 出队以从队列中删除元素 偷看队列中的第一个元素而不将其从队列中删除 像堆栈一样,您也可以将泛型与队列一起使用。 树木 树有助于提高搜索效率,提供排序的数据列表以及使对象之间具有层次关系。 树木由三个元素组成: 节点是树结构中的数据块 根是树的入口点(零级节点) 叶子 (终端节点)是没有子节点的节点 由于树是由节点组成的,因此我首先创建一个Node类。 此类由值,Node类型的子级数组(有时还包括Node类型的父级)组成。 您可能想知道为什么我指定Node类符合等于协议。 为了在使用泛型时实现搜索功能,我不得不让Xcode知道Node类实际上可以执行比较。 如果您要以树的方式考虑上述测试,它看起来像这样: 您可能已经听说过专门的“二叉树”。二叉树是其中每个节点只有0,1或2个子节点的树。 二叉搜索树是一棵树,它从树中插入和删除信息,以便始终对树进行排序。 要了解更多信息,请查看以下链接: 二叉树 二进制搜索树 参考文献: https://github.com/raywenderlich/swift-algorithm-club

iOS中的队列多线程

要创建吸引用户每天使用它的iOS应用,精美的设计必不可少,因此应用中的快速体验也至关重要。 几个月前,我下载了一个教您如何烹饪的应用程序。 我在使用它的10分钟内删除了它。 为什么? 图片无法加载,我被卡在加载标牌上很长时间(例如1-2分钟?)。 这很令人沮丧,因为我想看看教程中的菜式。 好吧,这没有发生。 那么到底需要发生什么呢? 排队是有益的,也是麻烦的 iPhone内有一个CPU(中央处理单元)。 CPU一次只能执行一项任务。 待处理的任务排成一行 。 将排队视为排队等候餐厅座位的人。 当服务员有空位时,将排在第一位。 先进先出(FIFO)。 那么,我们的手机又如何如此迅速地响应我们的触摸和动作? 答案是:多线程。 多线程允许处理器创建并发线程以便在处理器之间进行切换。 结果,可以同时执行多个任务。 每个线程都有自己的队列。 就像剧院票房的台词一样。 一条线供客户购买机票,另一条线供客户打印预订的机票。 人们在每一行同时进出。 相同的概念适用于iOS生态系统。 如果我们在应用程序内部具有多线程,则不会发生像烹饪应用程序这样的悲剧。 我们不必从服务器获取配方,而不必等待它完成然后显示图像。 让我们看看我们如何做到这一点! 在iOS中引入Grand Central Dispatch(GCD) Grand Central Dispatch将任务分配给不同的线程(不同的队列)。 例如,主线程负责从服务器获取配方数据,而后台线程将更新UI并显示图像。 因此,该应用程序保持响应状态。 很好,对吗? GCD API围绕 DispatchQueue 。 此类使我们能够创建/修改队列,以及同步或异步分配代码 和更多。 同步方式 为了。 当您执行同步操作时,以后出现的所有内容都必须等待上一个操作完成才能开始。 另一方面,当您异步执行某项操作时,以下代码可以立即运行。 在其他队列上启动任务后,它将立即将控件返回到当前队列,而无需等待其结束。 异步方法不会阻止当前队列上的任务执行。 如您所见,当队列给我们带来麻烦时,我们可以通过它的变体来巧妙地处理它。 请继续关注第二部分–代码中的GCD实现!

使用Swift在BST中进行级别订单遍历

开始之前,让我们先回顾一下… 在Swift中使用数据结构 因此,基本上我们已经学习了数据结构并在C / C ++中实现。 在这个故事中,您将看到学习一些基本数据的方法。 Swift中的二叉搜索树 从以前的帖子开始:https: //medium.com/@abhishekthaplithapliyal/playing-with-data-structure-in-swift-ccd8efca9611 medium.com 从最近的两个故事中,我们可以获得一些信息。 关于堆栈和树木。 让我们将它们放到一个新的水平,并结束本系列的其他内容。 此处节点1的级别为1,节点2和3的级别为2,节点4,5,6和7的级别为3。 现在,在进行级别顺序遍历的情况下,从根节点开始,从左到右逐一遍历每个级别。 如下所示 所以最终的内联输出就像 20、9、49、5、12、23、52、15、50 就像我们从左到右逐行编写。 那么,遍历为何排队的背后的策略是什么? 在这种情况下,队列是遍历的最简单方法。 与在队列中一样,操作以FIFO方式进行,即首先进行优先操作,并且在进行层顺序遍历时,我们需要首先访问根节点及其子节点,依此类推。 队列 让我们简要介绍一下队列。 队列具有类似数组的结构,其中元素是从后面添加的,因此操作称为Enqueue ,元素是从前面删除的,称为Dequeue 。 这就像售票柜台中的一条线,在该行的最后一行添加了新人,而票证则被卖给该行的第一人。 太好了! BST就在我这边。 希望你喜欢。 直到那时 快乐—编码😄😄!!!

Swift中的二叉搜索树

从以前的帖子: 在Swift中使用数据结构 因此,基本上我们已经学习了数据结构并在C / C ++中实现。 在这个故事中,您将看到学习一些基本数据的方法。 因此,我也前进到也要在二进制搜索树上进行写操作。 二进制搜索树是满足以下属性的树: 1.左子树中所有节点的值均小于根节点中的值。 2.右子树中所有节点的值都大于根节点中的值。 3.根节点的左和右子树也是BST。 要从这些遍历手动构建树,请遵循以下https://crackinterviewtoday.wordpress.com/2010/03/15/rebuild-a-binary-tree-from-inorder-and-preorder-traversals/ 正在搜寻 搜索机制类似于上面提到的具有相同2条规则的插入机制。 仅当节点数据与输入元素匹配时,它才会成功返回, 否则将返回无效消息,如下所示。 func search(element:T){…} :可供用户搜索元素。 private func search(_ rootNode:TreeNode ?, _ element:T){…} :这是将搜索元素的递归函数。 因此,如果element> rootNode.data ,它将递归调用根的右子树节点, 否则调用左子树节点。 由于树中存在E节点,因此返回成功结果NODE FOUND:E 。 由于没有节点包含等于N的数据,因此返回INVALID NODE:N 。 因此,这是泛型树的概述。 希望您对泛型有更多的了解。 在下一个故事中,我们将讨论最后一种遍历类型:Level Order Traversing😄……敬请期待😜!!! 使用Swift在BST中进行级别订单遍历 让我们先回顾一下, 然后再开始… medium.com 快乐编码😃!

在Swift中使用数据结构

我们都学习了数据结构,并以C / C ++实现。 在这个故事中,我将迅速说明一些使用泛型的基本数据结构。 让我们从堆栈开始。 注意:这个故事只是一个想法,重点在于基础知识。 欢迎提出建议和改进。 什么是堆栈? 我们都知道这是对的! 仅供参考,这是一个简单的例子– 我将定义一个可以推送/弹出任何类型对象的Stack类。 为了方便起见,我假设这些对象将确认为CustomStringConvertible协议(以便我可以打印其描述) Stack :CustomStringConvertible 这是使用泛型对象T的简单类声明 在单个链接列表中,第一个节点将是开始/根节点,下一个节点将是nil 。 创建一个班级名称 类LinkList :CustomStringConvertible,其中T:可比较,T:CustomStringConvertible 问:为什么在这里要求可比 ? 答:在搜索特定节点的情况下,我需要比较元素。 因此,为了进行比较,链接列表中的元素应符合可比较协议。 如上所示,声明称为startNode的私有节点。 注意:在这里假设理想情况,您可以管理空/零情况 append:此函数将在列表末尾添加元素。 如果链接列表为空,那么将要添加的第一个元素将是起始节点。 insert:此函数将在链接列表的开头添加元素。 如果链接列表为空,那么将要添加的第一个元素将是起始节点。 插入(位置):这会将节点添加到给定位置。 removeFirst:此函数将从头开始删除节点。 removeLast:此函数将在最后删除节点。 remove(position):这将从给定位置移除节点。 搜索:它将根据数据搜索节点并返回其位置。 行使: 1.试用字母链接列表😝。 2.尝试制作双向/圆形链接列表😅 希望您能对如何快速使用泛型和实现基本数据结构有所了解。 我还添加了练习,希望您能进行探索。 如果听起来不错,请在Swift check中选择Binary Search Tree Swift中的二叉搜索树 从以前的帖子开始: medium.com 快乐编码😃!

iOS版Sweet&Swifty动画

“在计算机科学中, 数据结构是在计算机中组织数据以便有效利用的一种特殊方式。”-维基百科 这些数据结构和设计模式使您可以通过简单且普遍有用的解决方案来摆脱臭名昭著的反模式 。 输入SwiftyAnimate(插件🔌)。 制作动画的更好方法…… 您是否尝试过将多个动画串在一起? 是的,你当然有。 您将每个后续动画包装在上一个动画的完成处理程序中,并迅速结束编写其他功能的工作,以打破厄运金字塔(或死亡虫洞?)。 无论您最终得到什么,都不是您真正想要的。 也许像这样……? 输入要救援的队列! 它们为您提供O(1)入队和出队的时间复杂度,而您在Swift中使用标准Array类型无法获得(阵列对append和popLast操作具有O(1)的平均时间复杂度,其中popFirst是O(n)操作)。 (现实生活中的例子)

Swift中的树数据结构

如果您不熟悉数据结构和算法,那么树数据结构就是一个很好的起点。 实际上,如果您曾经使用过JSON,那么您已经很熟悉这个概念。 树是一种数据结构,可用于对对象之间的层次关系进行建模。 该树由节点组成,每个节点具有以下组成: 一个值。 可选的父节点。 子节点列表。 术语 虽然树中的所有对象都被视为节点,但它们根据周围的上下文具有不同的命名约定。 根节点 :这是树的最高层的节点,并且是唯一没有任何父节点的节点。 叶子节点 :这是一个不包含任何子节点的节点。 Swift中的节点数据结构 这里要注意的一些事情是: 1. Node类对它拥有的值是通用的。 但这不是必需的,但是,它允许您以与数组相同的方式构建包含不同数据类型的各种树,从而有助于代码重用。 2.我们已将持有父节点的属性标记为弱。 由于父节点拥有对其所有子代的引用,而子代拥有对其父代的引用,因此我们将父代参考标记为弱,以防止创建强参考循环。 3.我们已将父级和子级属性标记为只读。 这是因为直接修改这些值可能容易出错。 最好通过Node类上的方法公开一个安全的API。 您可以看到,通过在Node上使用addChild方法,我们将永远不会忘记在新添加的节点上设置父级。 树木和递归就像面包和黄油。 您可以尝试: 1.创建一个在包含给定值的树中查找第一个节点的方法。 2.打印出节点及其所有子节点的文本表示形式。 在Swift算法俱乐部中更深入地了解这棵树的例子。

解决LeetCode中的问题对我有什么帮助?

几周前,我启动了我的第一个iOS应用程序,它具有关于Swift的非常基础的知识,这些知识是我通过一些教程和主要是Apple文档中学到的。 但是后来,我对任何编程语言都不了解,几乎所有在Swift中学到的东西对我来说都是新的。 掌握了基本数据类型,条件语句和循环的新手知识之后 ,我开始使用Swift进行编码。 在开发应用程序的过程中,我学习并使用了某些iOS SDK和库。 随着我的知识的增长,它主要取决于应用程序开发本身,而很少涉及编程概念。 这里要具体说明数据结构和算法。 我在应用商店中发布了我的应用。 在与朋友一起审查该应用程序并谈论其可扩展性时,我了解到我还有很多东西要学习。 不仅是编程语言,数据结构和算法,还涉及解决问题的方法。 我相信通过经验学习,这样我才能更快地学习,解决现实生活中的问题并保持动力。 因此,我一直在浏览有关我应该学习什么以及应该如何开始的网站,并且对初学者学习编程的所有不同选择感到非常困惑。 幸运的是,我的一个朋友向我介绍了Leetcode。 LeetCode是一个平台,允许任何人以越来越困难的方式解决编程问题。 当我开始解决问题时,我觉得LeetCode是一个很好的平台,可以提高您在解决问题和编码方面的技能 。 它支持Swift,因此我也可以掌握编程语言,最终帮助我更快更好地构建iOS应用。 LeetCode 提升您的编码技能,并迅速找到工作。 这是扩展您的知识并做好准备的最佳场所。 leetcode.com 如何开始解决问题的实践: 首先,对要学习的东西有个目标 。 对我而言,这是使用正确的OOPS概念编写更好,更简洁的代码,并对数据结构和算法有深入的了解。 从简单的事情开始,这样您就会获得信心。 然后逐步解决中/硬问题。 尝试在40分钟内解决 。 如果找不到解决方案,请查看提示,然后继续。 当您开始感到更加自信时,请减少时间。 如果您不了解某些内容,请不要犹豫 。 当我说Google时,请不要用Google搜索问题本身。 Google会根据您的想法解决问题,并了解如何实施这些想法。 对于数据结构(DS)学习 ,首先列出要保留的数据结构 。 然后阅读有关google,GeeksforGeeks等中的内容的信息,一旦您掌握了一些知识,请先使用您选择的编程语言来实施DS ,然后再使用DS解决问题。 然后在LeetCode中搜索数据结构的实现问题。 解决该问题的方法有助于我理解如何将特定类型的数据结构应用于问题。 测试您的代码并提交 。 如果您的代码没有通过,请不要放弃。 尝试修复错误,直到正确为止。 LeetCode的主要学习成果: 了解面向对象的编程。 更好地解决问题 。 开始掌握时间和空间的复杂性 。 了解哈希表和B树 。 […]

Swift数据结构:堆

堆是一个非常整洁的数据结构,可以对最小值或最大值进行优先级排序。 它与树的分层和节点结构有些相似,但是由于它是线性的,因此可以轻松地存储在数组中。 对于视觉人来说,如果我们将其绘制出来,这就是堆的外观: 上图显示了最小(最小)堆,该堆优先排列顶部数据集中的最小值作为根父节点。 在下面,存在值为3和8的节点,它们分别作为父节点的左和右子节点(值为2)存在。 值为3的节点的左子节点为4,右子节点为7。此过程将一直进行下去,直到所有数据集中的值都已布置好为止。 请注意,这些值通常随从顶部到底部的增加而增加。 它们本身不是从左到右组织的,而是按行组织的。 第1行在根节点的位置包含值2。 第2行的左,右子节点的值3和8都大于2。第3行包含了节点3和8的左右子节点。如您所见,两个节点的子节点在值。 希望您开始注意到一种模式。 最小堆中的每个父级可以有0、1或2个子级-所有这些子级的值都大于父级。 最大堆的工作方式完全相反。 堆利用索引系统(如数组)来确定值的顺序及其在堆中的位置(从索引0开始并向上计数)。 如果我们从较早之前引用可视堆图,则索引从上到下,从左到右递增,如下所示: 到目前为止,您所看到的示例都显示了静态数据。 我们没有添加或删除任何项目,但是最重要的是我们可以更改Heap中的数据,否则此数据结构将毫无价值。 在Swift中,我们将首先创建一个名为MinHeap的结构, MinHeap所示: 遵循堆的规则,您可以看到从上到下的每一行通常会逐渐变大,并且每个父节点的子节点都大于其自身。 调用peek()返回您期望的2值,而调用poll()在删除第一项后重新排列堆。 若要查看实际效果,请将以下代码添加到MinHeap结构的底部,然后再次调用dump(myHeap.items) : 我们做到了! 现在,我们已经成功地构建了一个最小堆,它对传入的最小值进行优先级排序。删除值后,堆将重新排序,因此下一个最小值位于顶部。 但是在现实世界中可以在哪里使用呢? 在Github Gist上获得完整的源代码:https://gist.github.com/kalub92/d269ba6b2bf05ca7dcbaae64b4ff7a2d 想象一下,您正在为儿科急诊室建立患者摄入系统。 医院希望优先考虑最年轻的患者,以便他们能够尽快接受护理。 想象一下,有几个6、7和8岁的孩子在候诊室,但一个病得很重的1岁孩子进入候诊室并经历了摄入过程。 在时间上,1岁应排在第4位,但该医院希望首先照顾最年轻的患者。 如果在患者摄入计划中使用了Heap,则1岁的孩子会马上去找儿科医生见面。 这是一个特定的用例,但我想知道您的想法。 您认为堆可以在现实世界中有用地实现在哪里。 在下面发表评论,让我们知道! 如果您准备加入我们并了解有关Swift,数据结构和iOS开发的更多信息,请查看Devslopes并注册我们的Apple坡度,以学习构建自己的应用程序和启动基于应用程序的初创公司所需的所有技能。 。

可爱的队列

我知道你们已经在这个队列上等待了太长时间。 因此,让我们深入研究问题代码。 与堆栈不同,队列全部与FIFO有关,请考虑FIFA,除非并非如此。 当您处于排队状态时,您希望排队的第一个人将首先得到服务。 考虑到这一点,让我们来构建它! 我们创建了一个变量,它将所有项目组合在一起。 然后,我们创建了一个将追加新项目的函数。 附加的项目将进入队列的末尾。 此外,当我们使一个项目出队时,我们需要检查是否还有一个项目开始。 不要成为冒昧的程序员,不要承担任何责任,检查自己并检查可选组件! 因此,一旦我们保护了队列中的项目,我们还将检查第一个元素是否确实存在,如果确实存在,那就让我们返回它! 但是,如果没有,则应该返回nil,因为队列中没有任何内容! 最后,偷看方法应该很明显,您希望看到谁在队列中,并且您最关心的项目或人员还是第一人。 让我们看一个实际的例子: 因此,这里有Lannisters。 当我们第一次窥视内部时,我们的队列中没有兰尼斯特。 但是,将其中的三个相加后,您会看到我们将返回我们也预计将在本赛季死亡的Lannister。 队列和塞雷的死对任何人都不应该感到惊讶。 当尝试为Queue编写代码时,请尝试与用户保持同理心,而我的意思是想想您正在排队或为某人服务的时间……您将如何帮助他们? 这种心态应该可以帮助您编写队列代码并记住其核心概念!