程序员考试刷题-swift-algorithm-club:快速算法俱乐部

  • A4_225037
    了解作者
  • 8.9MB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-05-27 06:55
    上传日期
程序员考试刷题 欢迎来到 Swift 算法俱乐部! 在这里,您将找到使用大家最喜欢的新语言 Swift 实现的流行算法和数据结构,并详细解释了它们的工作原理。 如果您是一名计算机科学专业的学生,​​需要在考试中学习这些东西 - 或者如果您是一名自学的程序员,想要复习您的技术背后的理论 - 您来对地方了! 这个项目的目标是解释算法是如何工作的。 重点是代码的清晰度和可读性,而不是制作可重用的库,您可以将其放入自己的项目中。 也就是说,大部分代码应该可以用于生产,但您可能需要对其进行调整以适应您自己的代码库。 代码与Xcode 10和Swift 4.2兼容。 我们将使用最新版本的 Swift 进行更新。 如果您对存储库的 GitHub 页面版本感兴趣,请查看 。 :smiling_face_with_heart-eyes: 欢迎提出建议和贡献! :smiling_face_with_heart-eyes: 重要链接 薄煎饼! 担心这不是你的一杯茶吗? 然后读这个。 . 我们经常说“这个算法是O(n)” 。 如果您不知道这意味着什么,请先阅读此内容。 . 您如何创建自己的算法? . 报告问题以留下反馈,或提交拉取请求。 从哪儿开始? 如果您不熟悉算法和数据结构,这里有一些不错的入门方法: 和 算法 搜索
swift-algorithm-club-master.zip
内容介绍
# Weighted graph general concepts Every weighted graph should contain: 1. Vertices/Nodes (I will use "vertex" in this readme). 2. Edges connecting vertices. Let's add some edges to our graph. For simplicity let's create directed graph for now. Directed means that edge has a direction, i.e. vertex, where it starts and vertex, where it ends. But remember a VERY IMPORTANT thing: * All undirected graphs can be viewed as a directed graph. * A directed graph is undirected if and only if every edge is paired with an edge going in the opposite direction. 3. Weights for every edge. Final result. Directed weighted graph: Undirected weighted graph: And once again: An undirected graph it is a directed graph with every edge paired with an edge going in the opposite direction. This statement is clear on the image above. Great! Now we are familiar with general concepts about graphs. # The Dijkstra's algorithm This [algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) was invented in 1956 by Edsger W. Dijkstra. It can be used when you have one source vertex and want to find the shortest paths to ALL other vertices in the graph. The best example is a road network. If you want to find the shortest path from your house to your job or if you want to find the closest store to your house then it is time for the Dijkstra's algorithm. The algorithm repeats following cycle until all vertices are marked as visited. Cycle: 1. From the non-visited vertices the algorithm picks a vertex with the shortest path length from the start (if there are more than one vertex with the same shortest path value then algorithm picks any of them) 2. The algorithm marks picked vertex as visited. 3. The algorithm checks all of its neighbours. If the current vertex path length from the start plus an edge weight to a neighbour less than the neighbour current path length from the start than it assigns new path length from the start to the neighbour. When all vertices are marked as visited, the algorithm's job is done. Now, you can see the shortest path from the start for every vertex by pressing the one you are interested in. I have created **VisualizedDijkstra.playground** game/tutorial to improve your understanding of the algorithm's flow. Besides, below is step by step algorithm's description. A short sidenote. The Swift Algorithm Club also contains the A* algorithm, which essentially is a faster version of Dijkstra's algorithm for which the only extra prerequisite is you have to know where the destination is located. ## Example Let's imagine that you want to go to the shop. Your house is A vertex and there are 4 possible stores around your house. How to find the closest one/ones? Luckily, you have a graph that connects your house with all these stores. So, you know what to do :) ### Initialisation When the algorithm starts to work initial graph looks like this: The table below represents graph state: | | A | B | C | D | E | |:------------------------- |:---:|:---:|:---:|:---:|:---:| | Visited | F | F | F | F | F | | Path Length From Start | inf | inf | inf | inf | inf | | Path Vertices From Start | [ ] | [ ] | [ ] | [ ] | [ ] | >inf is equal infinity which basically means that algorithm doesn't know how far away is this vertex from start one. >F states for False >T states for True To initialize our graph we have to set source vertex path length from source vertex to 0 and append itself to path vertices from start. | | A | B | C | D | E | |:------------------------- |:---:|:---:|:---:|:---:|:---:| | Visited | F | F | F | F | F | | Path Length From Start | 0 | inf | inf | inf | inf | | Path Vertices From Start | [A] | [ ] | [ ] | [ ] | [ ] | Great, now our graph is initialised and we can pass it to the Dijkstra's algorithm, let's start! Let's follow the algorithm's cycle and pick the first vertex which neighbours we want to check. All our vertices are not visited but there is only one has the smallest path length from start. It is A. This vertex is the first one which neighbors we will check. First of all, set this vertex as visited. A.visited = true After this step graph has this state: | | A | B | C | D | E | |:------------------------- |:---:|:---:|:---:|:---:|:---:| | Visited | T | F | F | F | F | | Path Length From Start | 0 | inf | inf | inf | inf | | Path Vertices From Start | [A] | [ ] | [ ] | [ ] | [ ] | ### Step 1 Then we check all of its neighbours. If checking vertex path length from start + edge weight is smaller than neighbour's path length from start then we set neighbour's path length from start new value and append to its pathVerticesFromStart array new vertex: checkingVertex. Repeat this action for every vertex. for clarity: ```swift if (A.pathLengthFromStart + AB.weight) < B.pathLengthFromStart { B.pathLengthFromStart = A.pathLengthFromStart + AB.weight B.pathVerticesFromStart = A.pathVerticesFromStart B.pathVerticesFromStart.append(B) } ``` And now our graph looks like this one: And its state is here: | | A | B | C | D | E | |:------------------------- |:----------:|:----------:|:----------:|:----------:|:----------:| | Visited | T | F | F | F | F | | Path Length From Start | 0 | 3 | inf | 1 | inf | | Path Vertices From Start | [A] | [A, B] | [ ] | [A, D] | [ ] | ### Step 2 From now we repeat all actions again and fill our table with new info! | | A | B | C | D | E | |:------------------------- |:----------:|:----------:|:----------:|:----------:|:----------:| | Visited | T | F | F | T | F | | Path Length From Start | 0 | 3 | inf | 1 | 2 | | Path Vertices From Start | [A] | [A, B] | [ ] | [A, D] | [A, D, E] | ### Step 3 | | A | B | C | D | E | |:------------------------- |:----------:|:----------:|:----------:|:----------:|:----------:| | Visited | T | F | F | T | T | | Path Length From Start | 0 | 3 | 11 | 1 | 2 | | Path Vertices From Start | [A] | [A, B] |[A, D, E, C]| [A, D] | [A, D, E ] | ### Step 4 | | A | B | C | D | E | |:------------------------- |:----------:|:----------:|:----------:|:----------:|:----------:| | Visited | T | T | F | T | T | | Path Length From Start | 0 | 3 | 8 | 1 | 2 | | Path Vertices From Start | [A] | [A, B] | [A, B, C]| [A, D] | [A, D, E ] | ### Step 5 | | A | B | C | D | E | |:------------------------- |
评论
    相关推荐
    • Xcode Apps-开源
      问卷 App:检索 JSON 数据;... 拒绝非数字输入 Places Ive Being App:持久化/核心数据存储 最喜欢的地方 App:地图视图; 编辑/重新排序表格功能界面生成器应用程序:元素大小、位置和对齐方式; 设备方向; 本土化
    • TwoWindows:Xcode 示例
      如果它不是窗口控制器,它是一个警告存储。 在这里,我们将收到“Push Me”按钮的动作,因此从按钮的动作中连接第二个视图控制器并选择模态。如果您在此处选择 Sheet 或 Popover,外观将发生变化。 在第二个视图中...
    • XcodeServer:Xcode 服务器实验
      这个存储库的目标只是测试 Xcode 服务器并为以下用例提供一些收据: 全局技巧 创建机器人时,您需要处于要在 Xcode Server 上构建的确切配置(相同的分支,相同的方案,...) 确保您要构建的方案是共享的。 ...
    • xcode_tutorials:Xcode教程存储
      xcode_tutorials:Xcode教程存储
    • Xcode-Configuration:Xcode 配置文件、步骤和构建设置的存储
      Xcode-配置 Xcode 项目很难正确配置并包含不同级别的许多不同设置。 该项目旨在通过提供有关如何配置项目的一些想法来帮助具有不同配置、方案和选项的每个人。 它包含示例、针对不同情况的 xcconfig 文件、指南和...
    • xcode-playgrounds:实验
      :man_bouncing_ball: 斯威夫特游乐场 该存储库包含Xcode游乐场的集合,我曾经用它们来编写的博客文章。 :person::cooking: 在今天的菜单上
    • CodeSnippets:XCode 代码片段
      将此存储库的内容克隆到~/Library/Developer/Xcode/UserData/CodeSnippets并重新启动 XCode。 代码片段应该出现在代码片段库中。 创建你自己的 将codesnippet.template复制到your-snippet-name.codesnippet 使用...
    • cpp-competitive-xcode-template:该存储库实现了用于竞争性编程的自定义Xcode C ++模板
      存储库实现了用于竞争性编程的自定义Xcode C ++模板。 如果需要,可以轻松定义输入和预期输出。 选项 该模板提供了添加其他目标以从输入文件读取或写入输出文件的选项。 选项包括: 没有任何 这不包括任何处理输入...
    • behaviors:code Xcode行为脚本可提高效率
      行为举止 :red_apple: Xcode行为脚本可提高效率...克隆或下载存储库 打开Xcode首选项 选择行为选项卡 选择加号 转到底部,然后选择“运行”复选框 选择列表中的脚本之一 通过选择行为名称旁边的按钮来设置键盘快捷方式
    • xcode ios 打包脚本
      基于 xcode 命令的 ios 项目打包脚本。 使用python 编写 功能包括:制作icon 图标,剪切图片,打包(store,deve,adhoc)