目前关于图的问题 Problem Problem Description Solution Efficiency paths Find a path from s to every reachable vertex. DepthFirstPaths.javaDemo O(V+E) timeΘ(V) space shortest paths Find the shortest path from s to every reachable vertex. BreadthFirstPaths.javaDemo O(V+E) timeΘ(V) space shortest weighted paths Find the shortest path, considering weights, from s to every reachable vertex. DijkstrasSP.javaDemo O(E log V) timeΘ(V) space shortest weighted path Find the shortest path, consider weight ...

Lab知识点 如何从命令行运行 Java 并运行 Capers 的测试（Gitlet 的测试非常非常相似）。 如何在 Java 中使用文件和目录。 如何将 Java 对象序列化为文件并在以后读回它们（也称为持久性）。 重要说明：静态变量在两次执行之间不会在 Java 中保留。当程序完成执行时，所有实例和静态变量都将完全丢失。我们可以在执行之间保持持久性的唯一方法是将数据存储在文件系统上。 命令行不用shell和cmd，我们用git bash来打开文件夹 首先，确保您当前的工作目录是 sp21-s***/lab6/capers 。这些命令将带您到达那里： 12$ cd $REPO_DIR$ cd lab6/capers 编译JAVA文件1$ javac *.java *.java 通配符仅返回当前目录中的所有 .java 文件。再次运行 ls ，您将看到一堆新 .class 文件，包括 Main.class .这些文件构成编译的代码。让我们看看它是什么样子的。 查看JAVA文件1$ cat Main.class 该命令将打印出文件的内容。你会看到大部分带有许多特殊字符的垃圾。这被 ...

【超干货】CS61B 2021sp全攻略（上）|一亩三分地公开课版 (1point3acres.com)的建议: 我做proj2花了大概10天代码大概一共800行推荐到springbreak的时候做这个项目写之前要把lab6复习一遍再把Lecture12看完然后推荐先把spec读一遍再看intro视频磨刀不误砍柴这个时候终于对要写几个对象、分别实现什么功能有点概念了然后再读一遍spec对着指令一条一条实现缺少一个整体设计概念的话不建议着急写代码否则你debug40多条指令的时间会远远高于这些思考的时间我感觉merge是最复杂的可以先看助教的视频他给你总结好了7种情况分类讨论下来有点心累但提交autograde看到1600满分的时候爽爆了 Lec12： cs61b 2021 lec12 command line programming, data structures preview - Google 幻灯片 Spring 2021: Live Lecture 12 (youtube.com) Lec12命令行的介绍 版本控制 Approach Number Informat ...

我们现在将学习一个名为 Tries 的新数据结构。这些将作为 Set 和 Map 的新实现（根据我们之前所学到的），该 Map 对某些类型的数据和信息具有一些特殊功能。 Trie的介绍回顾由于我们正在考虑 ADT Set和Map，让我们回顾一下到目前为止所学到的实现。过去，我们主要学习如何使用二叉搜索树或哈希表来实现这些 ADT。让我们回顾一下这两者的运行时： 平衡搜索树： contains(x): $Θ(logN)$ add(x): $Θ(logN)$ 调整单独的链接哈希表的大小： contains(x) ： $Θ(1) $（假设点差均匀） add(x) ： $Θ(1)$ （假设均匀点差和摊销） 我们可以看到，与 Sets 和 Maps 相关的操作的实现速度非常快。 问题：我们能做得比这更好吗？这可能取决于我们问题的性质。如果我们知道钥匙的特殊特性会怎样？ 答：是的，例如，如果我们总是知道我们的键是 ASCII 字符，那么不要使用通用的 HashMap，只需使用一个数组，其中每个字符都是我们数组中的不同索引： 123456789101112public class Da ...

The Search Problem我们面临的问题是：给定一个数据流，检索感兴趣的信息。 有哪些这样的例子？ 网站用户在个人页面上发帖。仅向好友提供内容。 给定数千个气象站的日志，显示指定日期和时间的天气图。 狗主人要求最好的宠物店，选择在价格、质量或氛围方面定义他们最好的商店。 到目前为止，我们讨论的所有数据结构都是为了解决搜索问题。你可能会怎么问？我们学到的每个数据结构都用于将信息存储在方案中，从而在特定场景中提高搜索效率。 Search Data Structures 搜索数据结构 Name Store Operation(s) Primary Retrieval Operation Retrieve By List 列表 add(key), insert(key, index) get(index) index Map put(key, value) get(key) key identity Set add(key) containsKey(key) key identity PQ add(key) getSmallest() key order ( ...

Uniform Partitioning 统一分区Motivation 赋予动机 假设我们想对空间中的一组 Body 对象执行操作。例如，也许我们想问一些关于二维图像空间中的太阳体（如下图所示）的问题。 First Question: 2D Range Finding 第一个问题：2D 测距我们可能会问的一个问题是：一个区域中有多少个对象，例如在上面突出显示的绿色矩形中？ Second Question: Nearest Neighbors 第二个问题：最近邻我们可能会问的另一个问题是：离另一个物体最近的物体是什么，比如哪个太阳离我们的太空马最近？（通过目视检查发现的所需答案是太阳最接近其后蹄。 Initial Attempt: HashTable 初始尝试：HashTable问题：如果我们的太阳集存储在 HashTable 中，那么找到最近邻问题的答案的运行时是什么？ 解决方案：每个物体所在的桶实际上是随机的，因此我们必须遍历所有 $N$ 物品，以检查每个太阳是否可能最接近马。 Θ(N) 。 让我们试着改进，这样我们就不必看我们布景中的每一个太阳来找到我们的答案。 Secon ...

设置教程:Lab 2 Setup: Library Setup | CS 61B Spring 2021 (datastructur.es)