A.R.L's Blog HomeArchivesCategoriesAbout
UCB CS61B(2021)
|KnowledgeAlgorithm

【双语字幕】CS 61B 数据结构 | 整合版 | UCB Data Structure Spring 2021 | 转码必看 Java 算法 Leetcode_哔哩哔哩_bilibili

直接拉取框架代码（简介里面有），搜索autograder邀请码【知乎搜索“cs61b"】（网站是gradescope）以便测试自己的代码，视频上述链接，b站有另一个包括discussion更全的合集自行搜索

（踩坑：一定要找到对应2021课程的邀请码）

听过软工一所以直接从project 0 做起，可以看一看debug的lab，对于不太会用debug的选手来说非常友好

Project 0

测试全通过就没问题

2048（GUI）无法在本地运行（踩坑）：Windows系统必须把默认语言改为英语，非专业版win改不了

Lecture 1-8

快速略过，与软工一内容相似

可以重点看一下用Java构造链表部分

Lecture 9

继承变量

子类继承父类一切变量（包括私有变量）

子类不可以直接使用父类私有，用 super(). 方法调用

继承方法调用

1
2
3
4
5
6
7
8
9
//Dog father class
public void bark(){
    barkmany(1);
}
public void barkmany(int x){
    for(int i = 0;i < x;i++){
        System.out.println("bark");
    }
}
1
2
3
4
5
6
7
8
9
//VerboseDog extends Dog (child class)
//VerboseDog does not contain bark method
@Override
public void barkmany(int x){
    System.out.println("As a dog, i say:");
    for(int i = 0;i < x;i++){
        bark();
    }
}
1
2
VerboseDog me = new VerboseDog();
me.barkmany(3)

上述代码运行时陷入无穷循环，vd的barkmany调用dog类的bark方法，bark再调用vd中的barkmany方法。

Higher order function

1
2
3
public interface IntUnaryFunction{
    int apply(int x);
}
1
2
3
4
5
public class TenX implements IntUnaryFunction{
    public int apply(int x){
        return 10 * x;
    }
}
1
2
3
4
5
6
7
8
9
public class Hdemo{
    public static doTwice(IntUnaryFunction f,int x){
        return f.apply(f.apply(x));
    }
    public static void main(String[] args){
        IntUnaryFunction tenX = new Tenx();
        System.out.println(doTwice(tenX,2);  //200
    }
}

Lab 4 git merge

solving conflicts : do it manually

git exercise A & B 都做不了，把skeleton直接拉到自己的仓库里了

Lecture 10

通用比较(interface)

构建interface然后在自己的类中执行，注意类型转换

1
2
3
public interface OurComparable {
   int compareTo(Object obj);
}
1
2
3
4
5
6
7
public class Dog implements OurComparable {
    public int compareTo(Object obj) {
    	/** Warning, cast can cause runtime error! */
       Dog uddaDog = (Dog) obj;
       return this.size - uddaDog.size;
    }
}
1
2
3
4
5
6
7
8
9
public class Maximizer {
  public static OurComparable max(OurComparable[] items) {
    ...
    int cmp = items[i];
    for(...)
    compareTo(items[maxDex]);
    ...
  }
}
1
2
Dog[] dogs = new Dog[]{d1, d2, d3};
Dog largest = (Dog) Maximizer.max(dogs);

Comparable

1
2
3
4
//java standard library
public interface Comparable<T> {
     public int compareTo(T obj);
} 
1
2
//内置api，只要实现comparable
Collection.max()

Comparator

1
2
3
4
5
6
7
8
9
10
public class Dog{
    private static class myComparator implements Comparator<T>{
        public int compare(T o1,T o2){
            ...
        }
    }
    public static Comparator<T> getComparator(){
        return new myComparator();
    }
}

Lecture 11

ArrayList

.add .contains

Exceptions

1
throw new IlegalArgumentException("Error Message");

Iterator

construct a class that implements iterator interface

1
2
3
4
public interface Iterator<T>{
    boolean hasNext();
    T next();
}
1
2
3
4
public class ArrayDeque<T> implements Iterable<T>{
    public Iterator<T> iterator(){}
}
//可以对类中元素使用for each
1
2
3
4
5
6
7
8
//java自带
public class Collection<E> extends Iterable<E>{
    public Iterator<E> iterator(){}
}

public class Set<E> extends Collection<E>{
    public Iterator<E> iterator(){}
}

获取类的类型

1
2
object.getclass()
Array.class//已知固定类型

Extra : of method

1
2
3
4
5
6
7
8
//Type ... items : take in var argument(不定量）
public static <Type> ArraySet<Type> of(Type ... items){
    ArraySet<Type> returnSet = new ArraySet<Type>();
    for(Type x:items){
        returnSet.add(x);
    }
    return returnSet;
}

Project 1

看完 Lecture 10 和 Lecture 11才可以完整完成(Lecture 10: comparator/Lecture 11: iterator)

debug daily :

  • deep equal : 多维比较
  • 写equal不需要考虑顺序？，只需要考虑是否包含
  • iterator 按照课上方法写构造私有类，但是gradescope会报api check error，没有执行 iterable interface，但是整体类又实现了deque interface，待解决…
  • ArrayDeque debug log，照着gradescope上未通过的测试自己写一些用例即可
  • 不想特意去看style guide，api和style扣分没管，所有测试用例通过

Lecture 12

simulate git commit (java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Commit implements Serializable {
    public String author;
    public String date;
    public String commitMessage;
    public String parentID;
   
    public Commit(String a,String d,String c,String p){
        author = a;
        date = d;
        commitMessage = c;
        parentID = p;
    }

    public static void main(String[] args){
        Commit c = new Commit("Josh","Feb","message","...");
        File f = new File("CommitExample.txt");
        Utils.writeObject(f,c);
}

Lab 5

mainly discussion --skip

Lecture 13&15

mainly about description of algorithm scales (quick skip)

Lecture 14

this lesson is very important in improving algorithm

视频看完感觉不够再看一下lecture guide

question : weighted quick union : why tree hight is lgNlgN

After listening to lecture 15(binary search part) we can see that tree is organized with 2 leafs for one node

Lab 6

File

1
2
3
4
5
6
File f = new File("path");
if(!f.exists()){
    f.createNewFile();
}
//write content to file using utils
Utils.writeContents(f, "Hello World");

Directory

1
2
File d = new File("dummy");
d.mkdir();

Serializable

Serialization is the process of translating an object to a series of bytes that can then be stored in the file.

1
2
3
4
5
6
7
8
9
10
11
12
import java.io.Serializable;
public class Model implements Serializable {
    //This interface has no methods
    Model m;
    File outFile = new File(saveFileName);
    // Serializing the Model object
    writeObject(outFile, m);

    File inFile = new File(readFileName);
    // Deserializing the Model object
    m = readObject(inFile, Model.class);
}

Lecture 16

some useful data structures in Java : List, Map, Set

binary search tree (BST)

order: left < node < right

trap: deleting move children upwards to keep left < node < right

Lecture 17

adding something to a tree(B-tree)

have multiple elements in one node, but set the largest num.

move the left middle up and split the most left.

Lecture 18

rotate the tree item

  • merge with children/parent
  • move down/up

Left-leaning Red Black Tree (LLRB or LLRBBST)

LLRB operations Always insert with a red link at the correct location. Then use the following three operations to “fix” or LLRB tree. See slides for visual

  1. If there is a right leaning red link, rotate that node left.
  2. If there are two consecutive left leaning links, rotate right on the top node.
  3. If there is a node with two red links to children, flip all links with that node.

Lab 7

忽略了api checker 报错

HW 2

直接在gradescope上做，有选项判分系统（未知：submit之后还是ungraded？）

Lecture 19

code word

hash code

1
2
Math.floorMod(-1,4) //return 3
-1 % 4 == -1 //true

Lecture 20

Heap

Binary min-heap: Binary tree that is complete and obeys min-heap property.

  • Min-heap: Every node is less than or equal to both of its children.
  • Complete: Missing items only at the bottom level (if any), all nodes are as far left as possible.

the array for first picture will be 0，5，1，8，8，6，2

Add and Remove

add: 补叶子

romove: 移除root，将最下方最右端的叶子放到root上，再和下方节点逐次交换到相应位置

Lecture 21&22

Lecture 21 几乎都是讲离散数学里面的概念（一部分深度优先搜索和广度优先搜索），快速掠过

Graph discription

  1. use matrix to represent
  2. use hashset that includes every edge of the graph
  3. use hashmap, each cell contains the adjacent node

Project 2

草草读一下文档开头感觉是一项大工程，关于commands部分有推荐看的lecture，先把lecture看完再写（一直看到 lecture22）

文件结构(.gitlet)

  • branch（按照名字存储文件名）

    • master
    • others

  • commit（commit使用tostring()，sha1后存储文件名）

  • blob（见tips，用文件名+文件内容sha1后）

  • stage（被缓存的文件文件名sha1后）

  • HEAD（同branch）

Tips

CS61B Gitlet - 知乎 (zhihu.com) 上面有许多注意事项可供参考

  • blob生成blobId(sha-1 id)的时候，需要通过文件名+文件内容(字节流)生成。若只用文件内容生成blobId，不同名的两个文件内容都为空时，生成的blobId是一致的, 使用文件名+文件对象生成的sha-1哈希也是同样的结果。
  • 同样也是commit生成sha1 id，把commit里面commit message 和time转成字符串然后再使用utils.sha1()函数
  • mkdir()只能在存在的目录下再创建，而mkdirs()会把所有不存在的目录全部创建；创建目录不用try catch。
  • 交checkpoint时init总是说sha1的object不对，utils包里面封装的sha1要求输入的参数必须是string或者byte array的混合类型，详情参考CS61B Gitlet入坑指南 - 知乎 (zhihu.com)这篇文章 **（血泪教训：一定要先好好看utils里面的封装注释！！！）**😢
  • 从lab 6开始无论在当前工作目录下或者testing文件夹下面跑make check都没有办法跑通测试，但是完全按照lab6里面配置，只能自己手动输命令测试
  • 判断untracked files使用之前写的isInStage和isInCommit来判断，既不在缓存区也没有提交过的文件就是untracked file
  • utils里面封装的plainfilename方法生成的不是java.util.ArrayList而是java.util.Arrays.ArrayList，所以不能使用remove（使用remove来删除掉这个project文件夹自带的配置文件，因为这些都在CWD下面但是不是untracked file。这篇博文 removeAll引发得java.lang.UnsupportedOperationException异常_IPI715718的博客-CSDN博客讲的很清楚）

Lecture 23&24

lecture 23 主要讲离散里面最短路径的算法

lecture 24 有关霍夫曼编码和压缩算法要仔细看一看

Lecture 25

k-d tree : k维树

example ：2d tree, divide tree into left and right according x, then divide up and down according to y (treat equal as right/up)


Lecture 26

tries/try : a new structure good for prefix, blue nodes mark the end of a word

if there is no branch in one path then can be compressed into one node

map the priority nums on it -> priority queue

Lecture 27-28

mainly software engineering philosophy（软工一已经包含了）quick skip

Lecture 29

Selection Sort

【O(n2 )】

Approach : find the smallest and put it to the front

Improvement : Naive Heap Sort 【O(nloglogn)】

Approach : make the array into a heap（this one is top down, meaning the biggest at top），then delete the root , make it into the end of an array.

Way To Make a Max Heap : sink

if there is a bigger number under a root node then sink the root down (exchange with the bigger one)

Merge Sort

【O(n loglog n)】(recursive) merge cost most O(N), split cost O(logN)

Approach : split the array into two pieces and sort them individually, then merge

Selection Sort

【O(n2 )】

Approach：from the start to end, move the first item into the sorted one’s right place

Improvement : Inplace-selection sort

from left to right, just exchange the item place

move 15 to the front, then compare 2 to 32, move front, compare, then front

Lecture 30 quick sort

思想：分而治之

First divide : select a pivot, move every item smaller than pivot to the left, bigger to the right

Then do it recursively

Best :【O(NlogNNlogN)】Worst : 【O(N2 )】

Lecture 32

about partition in quick sort : a new method (inplace exchange)

use partition to find the median

Lecture 36

理论分析的算法运行速度比较和实际运行的比较会结果不同

just in time compiler

java 的编译器会对代码运行过程进行优化

Lecture 38

prefix free code

按照树节点查找，找到一个字符后从头开始新一轮查找

shanon-fano code&huffman coding

根据每个字符出现的频率使用