最短路径(SPT)回顾到目前为止，我们有以下方法可以完成以下任务： 找到从给定顶点 s 到图中每个可到达顶点的路径。 找到从给定顶点 s 到图中每个可到达顶点的最短路径。（…或者我们找到了吗？） 在我们回答上述神秘问题之前，让我们进一步回顾一下我们可以使用的两种搜索类型：BFS 或 DFS。 两者都始终正确吗？是的。哪一个结果更好？BFS找到了最短路径，而DFS则没有。在运行时间上，哪一个更有效率？都不是。在空间上，哪一个更有效率？ 对于稀疏图，DFS更糟糕。想象一下一个有10000个节点且都很稀疏的图。我们最终会进行10000次递归调用，这对空间来说是不好的。 对于“树状”图，BFS更糟糕，因为我们的队列会经常被使用。 回答神秘问题我们是否开发了一种算法来找到从给定顶点到每个其他可到达顶点的最短路径？嗯，有点像是。我们开发了一种在没有边标签的图上运行良好的算法。这是我们做的：我们开发了一种算法，它从给定的源顶点找到了我们最短（其中最短的意思是最少的边数）的路径。 但这并不总是最短的正确定义。有时，我们的图边可能有‘权重’，如果 A-B 边的权重为5，而 A-C 边的权重只有3 ...

github仓库:xxbaizero0/PuzzleFlutterGame: A flutter game (github.com) AspectRatio参考文章 - Flutter 约束宽高比的控件 AspectRatio - 掘金 (juejin.cn) - flutter系列之:按比例缩放的AspectRatio和FractionallySizedBox - 掘金 (juejin.cn) GridView参考文章Flutter网格型布局 - GridView篇 - 掘金 (juejin.cn) 对话框参考文章: Flutter之Dialog使用和踩坑 - 掘金 (juejin.cn) privide参考文章 - Flutter Provider状态管理—八种提供者使用分析 - 掘金 (juejin.cn) - https://flyingstudio.feishu.cn/wiki/E2TSwTtZ9ik92EkCLpHcjAvbnRu?from=from_copylink 预览 UI界面 Header部分 Panel部分 游戏逻辑 数据源与游戏初始化 图片切割 ...

GitHub仓库:xxbaizero0/game_2048: Flutter game (github.com) AspectRatio参考文章 Flutter 约束宽高比的控件 AspectRatio - 掘金 (juejin.cn) flutter系列之:按比例缩放的AspectRatio和FractionallySizedBox - 掘金 (juejin.cn) GridView参考文章Flutter网格型布局 - GridView篇 - 掘金 (juejin.cn) GestureDetector参考文章 Flutter 手势系列教程—GestureDetector - 掘金 (juejin.cn) shared_preferences参考文章 Flutter shared_preferences的基本使用、源码分析、封装 - 掘金 (juejin.cn) privide参考文章 Flutter Provider状态管理—八种提供者使用分析 - 掘金 (juejin.cn) https://flyingstudio.feishu.cn/wiki/E2TSwTtZ ...

树的遍历树的回顾树的定义回想一下，一棵树由以下部分组成： 一组节点（或顶点）。 连接这些节点的一组边。 约束：任意两个节点之间只有一条路径。 树有什么用？到目前为止，我们已经了解了搜索树、尝试、堆、不相交集等。这些在我们创建高效算法的过程中非常有用：加快搜索项、允许添加前缀、检查连通性等。 但事实是它们比我们意识到的更加普遍。考虑一个组织结构图。在这里，总统是“根”。 “VP”是根的子代，依此类推。 另一个树结构是桌面上的 61b/ 目录（它就在您的桌面上，不是吗？）。正如我们所看到的，当您遍历到子文件夹时，它会转到后续子文件夹，依此类推。这简直就像树一样！ Tree Iteration Traversal回想一下我们如何学会遍历列表的？有一种遍历列表的方式感觉很自然。就是从开头开始…然后继续往下走。 或者也许我们做了一些有点奇怪的事情，比如遍历列表的反向。回想一下，我们还在讨论中编写了迭代器，以跳过没有在 Office Hours 排队中写描述的学生。 现在如何遍历一棵树呢？什么是正确的“顺序”？ 在回答这个问题之前，我们不能使用迭代这个词。相反，我们将称之为“遍历树” ...

项目2：Gitlet | CS 61B 2021 年春季 — Project 2: Gitlet | CS 61B Spring 2021 (datastructur.es)要求介绍 翻译项目 2: Gitlet关于此规范的说明此规范相当长。前半部分详细描述了您将支持的每个命令，另一半是测试详细信息和一些建议。为了帮助您理解，我们准备了许多高质量的视频，描述了规范的各个部分，并提供建议。所有视频都链接在本规范的相关位置，但我们也将在此列出它们以方便您查看。请注意：这些视频中的一些是在 2020 年春季创建的，当时 Gitlet 是项目 3，Capers 是 Lab 12，并且一些视频简要提及了 Hilfinger 教授的 CS 61B 设置（包括名为 shared 的远程，名为 repo 的存储库等）。请忽略这些内容，因为它们对本学期的您没有任何有用的信息。任务的实际内容没有改变。 Git 介绍 - 第 1 部分 Git 介绍 - 第 2 部分 直播讲座 12 Gitlet 介绍播放列表 第 1 部分 第 2 部分 第 3 部分 第 4 部分 Itai 使用的幻灯片 合并概述和示 ...

代码介绍在Lab8 起始代码在skeleton-sp21/lab8 at master · Berkeley-CS61B/skeleton-sp21 (github.com)仓库中 收获点本次Lab主要介绍了工厂化代码的思想 启动文件的继承结构如下： 1234567Map61B.java└── MyHashMap.java ├── MyHashMapALBuckets.java ├── MyHashMapHSBuckets.java ├── MyHashMapLLBuckets.java ├── MyHashMapPQBuckets.java └── MyHashMapTSBuckets.java 在这个哈希表中，有一个工厂方法 createBucket() 和 createTable(int tableSize)。 createBucket() 方法用于创建一个存储 Node 的桶。在下面的实现中，使用 LinkedList 作为桶的数据结构，因此这个工厂方法返回了一个 LinkedList<Node>。你可以通过重写 ...

为什么要使用PQ？我们学到的最后一个 ADT 是二叉搜索树，它使我们能够高效搜索，只需要 logN 时间。这是因为我们可以在搜索的每一步中剔除一半的元素。如果我们更关心快速找到最小或最大元素而不是快速搜索怎么办？ 同时，二叉树中，我们不允许存在两个具有相同的值的情况重新，因此就有了PQ。 优先级队列接口要理解这个抽象数据类型，请考虑一袋物品。您可以向这个袋子中添加物品，也可以从中移除物品等等。唯一的限制是您只能与这个袋子中的最小的物品进行交互。 123456789101112/** (Min) Priority Queue: Allowing tracking and removal of * the smallest item in a priority queue. */public interface MinPQ<Item> { /** Adds the item to the priority queue. */ public void add(Item x); /** Returns the smallest item in the ...

本文由GPT翻译，原文链接为: 原文 数学天花板：你的认知瓶颈在哪里？本·奥林 思考 2015年4月8日 4分钟 某天下午，我的系主任在教职工休息室里碰到了我，提出了一个发人深思的问题。 （他后来承认，他只是好奇是否能够在这个博客上玩傀儡。答案是一个响亮的“是的”：我像一个傀儡一样跳舞。） 那么，我们有天花板吗？ 传统的正统说：“绝对有。”有高智商和低智商。有“数学人”和“非数学人”。有些孩子就是“懂得了”；而其他人则不是。 试着问问成年人有关他们的数学教育：他们把它看作是某种NCAA锦标赛。每个人都会被淘汰，问题只是你能在游戏中坚持多久。“我处理不了代数”意味着第一轮的淘汰。“我在多元微积分停下了”意味着“嘿，我没赢，但我为进入最后四强而自豪。” 但是教师们中间有一个新的正统观念，那就是“绝对没有”。 你得欣赏这种乐观主义，这种大众主义。（看看你椅子下面——每个人都得到了一本范畴论教材！）但我认为你也得像我的朋友Karen一样怀疑。 Karen，我们有天花板吗？ Karen很努力。Karen会问问题。Karen相信自己。但Karen仍然觉得某些数学超出了她的能 ...