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)

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