详情
Object-Oriented Programming
- A model for organizing programs
- Modularity: Define each piece without worrying about other pieces, and they all work together.
- Allows for data abstraction: You can interact with an object without knowing how it’s implemented.
- Objects
- An object bundles together information and related behavior.
- Each objet has its own local state.
- Several objects may all be instances of a common type.
- Classes
- A class serves as a template for all of its instance.
- Each object is an instance of some class.
提示
CS61A Review
详情
Static and non-static
- 静态方法和常量只能通过类名调用
- 非静态方法可以通过实例名调用
Question
据我所知，静态方法内能执行的只有静态方法，那么通过调用实例的非静态方法是如何执行的?
- 静态方法始终只能调用的是同一个类中的静态方法，而实例与它无关
- 静态方法无法直接访问实例方法或实例变量，但可以通过接受实例对象作为参数间接调用实例方法
详情
Primitive Types and References Types
- 等号的黄金法则：
=始终传递变量空间（memory box）的比特位 - 原始类型变量的变量空间保存变量的值，引用类型变量的变量空间保存实例的空间地址
Build a List
- 正向构建列表和反向构建列表，递归和迭代计算链表长度，根据索引获取值
java
public class IntList {
public int first;
public IntList rest;
public IntList (int f, IntList r) {
first = f;
rest = r;
}
}详情
SLLists
- 用 SSLists 实现对 IntNode 的封装
java
public class SLList {
public IntNode first;
public SLList (int x) {
first = new IntNode(x, null);
}
}Sentinel Node
- 采用哨兵节点优化特判
java
public class SLList {
/* the first item, if it exists, is at sentinal.next.*/
public IntNode sentinel;
public SLList (int x) {
sentinel = new IntNode(-1, null);
sentinel.next = new IntNode(x, null);
}
}Invariants
An invariant is condition that is guaranteed to be true during code execution (assuming there are no bugs in your code).
Invariants make it easier to reason about code:
- Can assume they are true to simplify code.
- Must ensure that methods preserve invariants.
详情
DLLists
- 双向链表优化查找时间
Arrays vs. Classes
- Array indices can be computed at runtime.
- Class member variable names CANNOT be computed and used at runtime.
变量名在编译时被处理成内存地址，所以类成员变量名是无法在运行是计算并查找的
提示
符号表： 变量名仅在编译时存在于符号表中，用于记录变量名及其相关信息（如类型、作用域、内存地址）。在生成的机器代码中，变量名本身并不会分配实际的内存地址。
内存地址： 变量名对应的值会分配一个内存地址，例如：int a = 10。在编译后，变量 a 的值（10）会存储在某个内存地址中，比如 0x1000，但是 a 这个名字在运行时并不存在，它只是一个在编译时用于符号解析的标识。
详情
Testing
java
import org.junit.jupiter.api.Test;
public class SLListTest {
@Test
public void testSLList() {
SLList L = new SLList(15);
L.addFirst(10);
L.addFirst(5);
assertEquals(5, L.getFirst());
assertEquals(10, L.size());
}
}详情
详情
Static Type vs. Dynamic Type
Every variable in Java has a "compile-time type", a.k.a. "static type"。
- This is the type specified at declaration. Never changes!
Variables also have a "run-time type", a.k.a. "dynamic type".
- This is the type specified at instantiation (e.g. when using new).
- Equal to the type of the object being pointed at.
Interface vs. Implementation Inheritance
Interface inheritance (a.k.a. what):
- Allow you to generalize code in powerful simple way.
Implementation inheritance (a.k.a. how):
- Allows code-reuse: Subclasses anc rely on superclasses or interfaces.
- Example: print() implemented in List61B.java.
- Gives another dimension of control to subclass designers: Can decide whether or not to override default implementation.
Important: In both case, we specify "is-a" relationship, not "has-a".
- Good: Dog implements Animal, SLList implements List61B.
- Bad: Cat implements Claw, Set implements SSList.
详情
Dynamic Method Selection and Type Checking Puzzle
For each line of code, determine:
- Does that line cause a compilation error?
- Which method does dynamic method selection use?
- 编译时检查: 确保所有语法正确，并检查类型安全。
- 运行时检查: 动态方法选择根据对象的实际类型选择适当的方法实现。
Type Checking and Casting
- 编译器不关心如何实现，只关心静态类型是否匹配
- 慎用类型转换
详情
Subtype Polymorphism
The biggest idea of the last couple of lectures: Subtype Polymorphism
- Polymorphism: "providing a single interface to entities of different types"
Consider a variable deque of static type Deque：
- When you call deque.addFirst(), the actual behavior is based on the dynamic type.
- Java automatically selects the right behavior using what is sometimes called "dynamic method selection".
Example:
java
public class Dog<T> implements Comparable<T> {
public String name;
public int size;
public Dog(String n, int s) {
name = n;
size = s;
}
/* Dog barks. */
public void bark() {
System.out.println(name + " says: bark");
}
/* Compare two dogs based on their sizes. */
@Override
public int compareTo(T t) {
return this.size - ((Dog) t).size;
}
/* Compare two dogs based on their names. */
public static class NameComparator implements Comparator<Dog> {
@Override
public int compare(Dog d1, Dog d2) {
return d1.name.compareTo(d2.name);
}
}
}详情
Summary
This course we built our own Array based Set implementation.
To make it more industrial strength we:
- Added an exception if a user tried to add null to the set.
- There are other ways to deal with nulls. Our choice was arguably bad.
- Added support for "ugly" then "nice" iteration.
- Ugly iteration: Creating a subclass with next and hasNext methods.
- Nice iteration: Declaring that ArraySet implements Iterable.
- Added a toString method.
- Beware of String concatenation.
- Added a equals method.
- Used instanceof to check the class of the passed object.
详情
详情
Summary
- 程序运行时会进行两次检查：编译时检查和运行时检查，编译时检查主要检查语法和类型安全，运行时检查主要检查动态方法选择。
- 注意静态上下文中不能够使用泛型，泛型参数与类的实例相关联，而静态变量与方法与类相关联。
- access modifier（访问修饰符）: public, protected, default, private
详情
详情
详情
详情
LLRB Tree
- LLRB 和 2-3 树具有相同的旋转操作；
- LLRB 将两个节点连接的情况视作一个红链接（虚拟节点）；
- 红链接总是向左倾斜；
- LLRB 最坏情况下的高度为 2-3 树的两倍。
提示
LLRB（Left-Leaning Red-Black Tree，左倾红黑树）是一种自平衡二叉搜索树，它通过维护树的平衡性质，确保基本操作（如插入、删除和查找）的时间复杂度保持在 O(logN)。 LLRB 是红黑树的一种变体，具有与红黑树相似的性能，但实现起来相对更简单。它由 Robert Sedgewick 提出，主要特点是所有红链接都倾向于左边。
详情
详情
详情
详情
详情
详情
A*
- A* 算法是一种启发式搜索算法，用于最快查找图中两个节点之间的最短路径（不一定正确）。
- 根据现有距离的大小施加惩罚，距离越小，惩罚越大。因为相较距离的大的点，距离小的点到达终点时需要查询的点更多。
- 如果想要避开某个顶点，可以将其惩罚值设置为最大，但是不一定能避开该顶点。
详情
Cut Property
- 将顶点随机划分成两组，两组顶点集的连接边中的最短边必然是最小生成树中的边。
- 反证，任选一条连接边构成最小生成树，然而有更短的连接边存在，这怎么可能，所以矛盾。
Prim
- Prim 算法是一种贪心算法，用于查找图中的最小生成树。
- 从一个顶点开始，每次选择距离最近的顶点，直到所有顶点都被访问。
- 用 Cut Property 解释就是，一开始任选一个顶点为一组，然后每次选择距离该顶点集最近的顶点加入该组，直到所有顶点都被加入。
详情
详情
详情
详情
详情
详情
Summary
- 采用比较方法的排序算法，其时间复杂度的期望值为 θ(NlogN)，无法找到更快的排序算法。
- 证明，通过决策树判断任意两点大小，一共产生 N! 种排序结果，查找时间复杂度为 Ω(logN!) = Ω(NlogN)。
详情
详情
详情
详情
详情
Shannon Entropy
- Formal definition:
E(-log(p(X))), where E is expected value and p(X) is the probability that X is a given value (averaged over all possible values of X).
详情
详情
- 本文链接：https://io.helltractor.top/posts/course/CS61B
- 版权声明：本博客所有文章除特别声明外，均默认采用 CC BY-NC-SA 许可协议。
