CS61B，启动！

注：本文中的week对应课程时间安排。

week return 1今天先把昨天剩下的列表练习做了。根据UCB的课程要求，代码不能公开。先把列表部分停一停，做做proj0——2048。难绷的是，2048的tilt机翻成”倾斜”，其实是向某个方向滑动所有方块的意思。

   }
   return 1 + this.rest.size(); // this 指的是"正在调用这个方法或访问这个变量的那个对象"。

} return 1今天先把昨天剩下的列表练习做了。根据UCB的课程要求，代码不能公开。先把列表部分停一停，做做proj0——2048。难绷的是，2048的tilt机翻成”倾斜”，其实是向某个方向滑动所有方块的意思。+ this.rest.size(); // this 指的是”正在调用这个方法或访问这个变量的那个对象”。
} return 1今天先把昨天剩下的列表练习做了。根据UCB的课程要求，implements List61B<Item> 本质上是一个承诺。AList 表示**”我承诺我将拥有并定义List61B 接口中指定的所有属性和行为”，二者的关系实际上是“is-a”**。

Overriding码不能公开。先把列表部分停一停，做做proj0——2048。难绷的是，2048的tilt机翻成”倾斜”，其实是向某个方向滑动所有方块的意思。+ this.rest.size(); // this 指的是”正在调用这个方法或访问这个变量的那个对象”。
} return 1今天先把昨天剩下的列表练习做了。根据UCB的课程要求，代码不能公开。先把列表部分停一停，做做proj0——2implements List61B<Item> 本质上是一个承诺。AList 表示**”我承诺我将拥有并定义List61B 接口中指定的所有属性和行为”，二者的关系实际上是“is-a”**。

Overriding48。难绷的是，2048的tilt机翻成”倾斜”，其实是向某个方向滑动所有方块的意思。+ this.rest.size(); // this 指的是”正在调用这个方法或访问这个变量的那个对象”。
} return 1今天先把昨天剩下的列表练习做了。根据UCB的课程要求，代码不能公开。先把列表部分停一停，做做proj0：2048implements List61B<Item> 本质上是一个承诺。AList 表示**”我承诺我将拥有并定义List61B 接口中指定的所有属性和行为”，二者的关系实际上是“is-a”**。

Overriding难绷的是，2048的tilt机翻成”倾斜”，其实是向某个方向滑动所有方块的意思。+ this.rest.size(); // this 指的是”正在调用这个方法或访问这个变量的那个对象”
}return另外课后还布置了额外的练习。

5.19

今天先把昨天剩下的列表练习做了。根据UCB的课程要求，代码不能公开。先把列之后是在子类中，需要定义implements关系。public class AList<Item> implements List61B<Item>{...}
implements List61B<Item> 本质上是一个承诺。AList 表示**”我承诺我将拥有并定义List61B 接口中指定的所有属性和行为”，二者的关系实际上是“is-a”**。

Overriding分停一停，做做proj0：2048。难绷的是，2048的tilt机翻成”倾斜”，其实是向某个方向滑动所有方块的意思。

5.23 this.rest.size(); // this 指的是”正在调用这个方法或访问这个变量的那个对象”

}

5.15

学习了java的基本语法和结构。java是一门面向对象语言。程iimplements List61B` 本质上是一个承诺。AList 表示**”我承诺我将拥有并定义List61B 接口中指定的所有属性和行为”，二者的关系实际上是“is-a”**

Overridingplements List61B` 本质上是一个承诺。AList 表示**”我承诺我将拥有并定义List61B 接口中指定的所有属性和行为”，二者的关系实际上是“is-a”**

Overriding文件都是由一个个类构成，代码必须在函数内执行。与python需要区别语法是，它以大括号作为分隔，并且每行语句结束需要;，其实大部分语法和cpp比较接近。对于变量都要声明类型。以hello world为例：

public class hello_world{
	public static void main(String[] args){
		System.out.println("hello world");
		}
}

另外对于方法而言，Java 允许我们定义两种类型方法：

1. static，静态方法，由类本身执行的操作：

   x = Math.sqrt(100);

2. 非静态方法，实例方法，只能由类的特定实例执行：

   Math m = new Math();
   x = m.sqrt(100);

---

week2

5.17

主要学习了测试的方法，还有一些细节。java中不可以滥用!=，因为该运算符表示的是内存地址不同，如果内容相同但是内存地址不同那么是符合这个运算符的。如果比较内容，可以使用equal()方法。

在测试中，可以使用JUnit来简化。但是需要注意的是JUnit 要求测试方法必须是public、非 static、无参数的方法，且带有@Test 注解。这一章节只是看了slides。没有仔细学习。

5.18

Lists

如果一个变量不是基本类型，那么它就是引用类型。当我们声明对象变量时，我们使用引用类型变量来存储对象在内存中的位置。而对于基本类型和方法，Java 采用的是pass-by-value
eg.

public static void main(String[] args) {
    Walrus walrus = new Walrus(3500, 10.5);
    int x = 9;
    doStuff(walrus, x);
    System.out.println(walrus);
    System.out.println(x);
}
public static void doStuff(Walrus W, int x) {
    W.weight = W.weight - 100;

    x = x - 5;

在这段代码中，W 是引用类型，所以在doStuff方法中，与主方法指向用一个内存地址。而x 呢？x 作为基本类型，在doStuff方法中，本质是对原来主方法x的二进制位的复制。x = 9，在传入 doStuff(walrus, x) 时，是将 9 的拷贝传给doStuff。在 doStuff 中修改的是那个拷贝的 x，对 main 中的 x 没有影响。

IntLists

使用链表构造了一个列表，对于列表长度，则使用递归来解决。当然也可以使用迭代，这里就不写了。

这里还要求构造一个获取i 索引元素的方法。使用了一个挺妙的递归：基线条件是索引为0，返回首位。否则向剩余列表获取索引为i-1的元素。```java
public class IntList {
public int first;
public IntList rest;
public IntList(int f, IntList r) {
first = f;
rest = r;
}
public int size(){
if (rest == null){
return 1;
}
return 1 + this.rest.size(); // this 指的是“正在调用这个方法或访问这个变量的那个对象”�? }
public int get(int i){
if (i==0){
return first;
}
return rest.get(i-1);
}
public static void main(String[] args) {
IntList l = new IntList(15,null);
}
}

另外课后还布置了额外的练习。
## 5.19
今天先把昨天剩下的列表练习做了。根据UCB的课程要求，代码不能公开。先把列表部分停一停，做做proj0�?048。难绷的是，2048的`tilt`机翻成“倾斜”，其实是向某个方向滑动所有方块的意思�?
## 5.23
先完成proj0 的前几个方法，对于`tilt`,只需要完成一个方向，其余的则使用`board.setViewingPerspective(side)`。算法思想是分两步走，移动+合并+移动。对于移动的实现，从上到下，对每个pos 一一确认。从顶部开始，如果非空，则移动到pos ，然后一个pos 就确认好了。如果为空，那么当前的pos 就没有被确认。

```java
private boolean move_up(int col,int top){  
    boolean moved = false;  
    int pos = top;  
    for (int row = top; row >= 0; row--) {  
        Tile t = board.tile(col, row);  
        if (t != null){  
            if (row != pos){  
                board.move(col,pos,t);  
                moved = true;  
            }  
            pos--;  
        }  
    }  
    return moved;  
}

5.24

对于proj0 的合并部分，使用一个变量存储上一次的合并情况。然后一行行遍历列，如果上一次合并了，说明这次所在的行是上一次合并前的方块所在的行，所以跳过，并且重新记录。

private boolean merge(int col) {  
    boolean merged = false;  
    int top = board.size() - 1;  
    boolean lastMerged = false; // 标记上一个Tile 是否已合并 
  
    for (int row = top; row > 0; row--) {  
        if (lastMerged) {  
            lastMerged = false;  
            continue;  
        }  
  
        Tile current = board.tile(col, row);  
        Tile below = board.tile(col, row - 1);  
  
        if (current != null && below != null && current.value() == below.value()) {  
            board.move(col, row, below); // 合并到当前位置
            score += below.value() * 2;  
            merged = true;  
            lastMerged = true; // 跳过下一个Tile
        }  
    }  
    return merged;  
}

因为我们的合并只是移动了below，所以方块没有到达最终位置，需要再进行一次移动。这次的移动后就不需要合并了，这是游戏的规则。最后把两个方法集中到tilt 汇总：

public boolean tilt(Side side) {  
    boolean changed;  
    changed = false;  
    board.setViewingPerspective(side);  
    int top = board.size() - 1;  
    for (int col = 0; col < board.size(); col++) { //movement  
        boolean moved1 = move_up(col,top);  
        boolean merged = merge(col);  
        boolean moved2 = move_up(col,top);  
  
        if (moved1 || merged || moved2){  
            changed = true;  
        }  
  
    }  
    board.setViewingPerspective(Side.NORTH);  
    checkGameOver();  
    if (changed) {  
        setChanged();  
    }  
    return changed;

5.28

新学习了列表的实现，SLLists

public class SLList {  
    private IntNode first;  
  
    public SLList(int x) {  
       first = new IntNode(x,null);  
    }  
  
    public void addFirst(int x) {  
       // add x to the 1st position  
       first = new IntNode(x,first);  
    }  
    public int getFirst(){  
       return first.item;  
    }  
    public void addLast(int x) {  
       IntNode p = first;  
       while (p.next != null) {  
          p = p.next;  
       }  
       p.next = new IntNode(x, null);  
    }  
  
    public  int size(){  
       int size = 1;  
       IntNode p = first;  
       while (p.next != null){  
          p = p.next;  
          size++;  
       }  
       return size;  
    }  
  
    public static void main(String[] args) {  
       SLList list = new SLList(1);  
       list.addFirst(2);  
       System.out.println(list.getFirst());  
    }  
}

6.7

应付学校杂事，学习进度断了好久。今天学了Java 的嵌套类。以及private的使用。比较简单。SLList主要是针对IntNode的封装。所以在这个过程学习了一些封装知识与概念。

6.8

哨兵节点的学习，因为SLList对于空列表不方便 addlast，所以将结点类型改为 private，其次设置哨兵结点(sentinel)，即添加一个始终位于最前端的结点，确保数据结构不是空的。

public void addLast(int x){
	size += 1;
	IntNode p = sentinel;
	while (p.next != null){
		p = p.next;
	}
	p.next = new IntNode(x,null);
}

week3

6.9

前面构造了单向链表。但是我们调用addLast时，总会遍历整个链表。所以引入了双向链表DLList。也就是说：

1. 引入双指针prev和next。
2. 两端加入哨兵节点。亦或是构造循环链表，共用一个哨兵节点。

代码实现会在proj1 中完成。
显然，当前所学习的链表只支持整型。现在引入泛型的概念，使得链表通用化。

public class DLList<zhanweifu>{
	private StuffNode sentinel;
	private int size;

	public class StuffNode{
		public StuffNode prev;
		public zhanweifu item;
		public StuffNode next;
	}
}

然后当我们创建实例时，只需要在占位符中填入我们所需要的对象类型即可。

...
public static void main(String[] args){
	DLList<String> s1 = new DLList<>("bone");
}

Since generics only work with reference types, we cannot put primitives like int or double inside of angle brackets, e.g. <int>. Instead, we use the reference version of the primitive type, which in the case of int case is Integer

LinkedListDeque

磕磕绊绊写了一下午，把链表部分写的差不多了。

package deque;  
  
import java.util.NoSuchElementException;  
  
public class LinkedListDeque<T> {  
    private static class Node<T>{  
        T item;  
        Node<T> next;  
        Node<T> prev;  
  
        Node(T item, Node<T> next, Node<T> prev){  
            this.item = item;  
            this.next = next;  
            this.prev = prev;  
        }  
    }  
  
    private final Node<T> head;//sentinel  
    private final Node<T> tail;  
    private int size;  
  
    public LinkedListDeque(){  
        head = new Node<>(null, null, null);  
        tail = new Node<>(null, null, null);  
        head.next = tail;  
        tail.prev = head;  
        size = 0;  
    }  
  
    public int size(){  
        return size;  
    }  
  
    public void addFirst(T item){  
        Node<T> newNode = new Node<>(item,head.next,head);  
        head.next.prev = newNode;  
        head.next = newNode;  
        size++;  
    }  
  
    public void addLast(T item){  
        Node<T> newNode = new Node<>(item,tail,tail.prev);  
        tail.prev.next = newNode;  
        tail.prev = newNode;  
        size++;  
    }  
  
    public boolean isEmpty(){  
        return size == 0;  
    }  
  
    public T removeFirst(){  
        if (isEmpty()) return null;  
        Node<T> target = head.next;  
        head.next = target.next;  
        head.next.prev = target.prev;  
        size--;  
        return target.item;  
    }  
  
    public T removeLast(){  
        if (isEmpty()) return null;  
        Node<T> target = tail.prev;  
        tail.prev = target.prev;  
        tail.prev.next = tail;  
        size--;  
        return target.item;  
    }  
  
    public T get(int i){  
        if (i < 0 || i >= size) return null;  
        Node<T> p = head.next;  
        for (int cnt = 0;cnt < i;cnt++){  
            p = p.next;  
        }  
        return p.item;  
    }  
  
    private T RecursiveTrigger(Node<T> node,int i){  
        if (i == 0) return node.item;  
        return RecursiveTrigger(node.next,i-1);  
    }  
  
    public T getRecursive(int i){  
        if (i < 0 || i >= size) return null;  
        return RecursiveTrigger(head.next,i);  
    }  
  
    public void printDeque(){  
        Node<T> p = head.next;  
        while (p != tail){  
            System.out.print(p.item + " ");  
            p = p.next;  
        }  
        System.out.println();  
    }  
      
}

disc3

值传递机制

主要讲述原始类型和引用类型。原始类型变量存储了数据本身，引用类型变量存储了内存地址。

作用域隔离

public static void change(int level) {
    level = 50;
}

public static void main(String[] args) {
    int level = 18;
    change(level);
    System.out.println(level);  // 输出 18，不是50
}

ArrayDeque

介绍了数组的语法

int[] z = null;
int[] x, y;

x = new int[]{1, 2, 3, 4, 5};
y = x;
x = new int[]{-1, 2, 5, 4, 99};
y = new int[3];
z = new int[0];
int xL = x.length;

String[] s = new String[6];
s[4] = "ketchup";
s[x[3] - x[1]] = "muffins";

int[] b = {9, 10, 11};
System.arraycopy(b, 0, x, 3, 2);

System.arraycopy takes five parameters:

• The array to use as a source
• Where to start in the source array
• The array to use as a destination
• Where to start in the destination array
• How many items to copy

补充：

• 对于基本类型：拷贝的是值本身（深拷贝）

• 对于引用类型：拷贝的是引用地址（浅拷贝）
  Compared to arrays in other languages, Java arrays:

• Have no special syntax for “slicing” (such as in Python).

• Cannot be shrunk or expanded (such as in Ruby).

• Do not have member methods (such as in Javascript).

• Must contain values only of the same type (unlike Python).

6.10

AList

构造了AList，比较重要的是resize部分，一开始的方案是深拷贝给一个tmp，tmp长度是长一个单位，然后tmp 接受值之后返回给原列表。

int[] a = new int[size + 1];
System.arraycopy(items, 0, a, 0, size);
a[size] = 11;
items = a;
size = size + 1;

对于时间复杂度的优化

对于一开始的resize，我们只是拓宽一个长度。在addLast当中，我们可以采取size*rfactor来调整，从而减少后续重复的resize

对于泛型的支持There is one significant syntactical difference: Java does not allow us to create an array of generic objects due to an obscure issue with the way generics are implemented. That is, we cannot do something like:

Glorp[] items = new Glorp[8];

Instead, we have to use the awkward syntax shown below:

Glorp[] items = (Glorp []) new Object[8];

The other change we make is that we null out any items that we “delete”.

6.16

继承与实现

继续学习Java 的语言特性。以一个计算最长单词的函数为例：

public static String longest(SLList<String> list){  
    int maxindex = 0;  
    for (int i = 0; i < list.size(); i++){  
        String word = list.get(i);  
        String longString = list.get(maxindex);  
        if (word.length() > longString.length()){  
            maxindex = i;  
        }  
    }  
    return list.get(maxindex);  
}

如果我们需要支持AList 类型的列表，目前的知识告诉我们只能函数重载，即写一个几乎相同的函数。由此我们引入了接口继承的概念。#### interface inheritance
接口继承
In Java, in order to express this hierarchy, we need to do two things:

• Step 1: Define a type for the general list hypernym – we will choose the name List61B.
• Step 2: Specify that SLList and AList are hyponyms of that type.

public interface List61B<Item> {
    public void addFirst(Item x);
    public void add Last(Item y);
    public Item getFirst();
    public Item getLast();
    public Item removeLast();
    public Item get(int i);
    public void insert(Item x, int position);
    public int size();
}

之后是在子类中，需要定义implements关系。public class AList<Item> implements List61B<Item>{...}
implements List61B<Item> 本质上是一个承诺。AList 表示**“我承诺我将拥有并定�?List61B 接口中指定的所有属性和行为�?，二者的关系实际上是*”is-a�?Overriding
如果在子类中的方法有覆盖的话，那么在方法签名的定模需要包含@Override标签。这是一种代码规范。

@Override
public void addFirst(Item x) {
    insert(x, 0);
}

区分

• extends：继承了”什么是什么” + “怎么做”
• implements：承诺”我是什么” + “我会做什么”（但要自己实现怎么做）

  特征	extends	implements
  用途	类继承	接口实现
  继承对象	具体类	接口
  数量限制	只能继承1个类	可以实现多个接口
  获得内容	实现 + 声明	只获得声明

实现继承

default public void print() {
    for (int i = 0; i < size(); i += 1) {
        System.out.print(get(i) + " ");
    }
    System.out.println();
}

default 关键字是接口中的方法实现，让接口方法有默认行为，子类可以选择是否重写。

静态类型和动态类型

当Java 运行一个被覆盖的方法时，它会在其动态类型中搜索适当的方法签名并运行它。这一块还不太理解。

7.14

期末周结束了

类继承

通过extend关键字，子类继承父类的所有成员：

1. 所有实例和静态变量
2. 所有方法
3. 所有嵌套类
   The extends keyword defines “is-a”, or hypernymic relationships. A common mistake is to instead use it for “has-a”, or meronymic relationships.

高阶函数

在Python 中，可以直接将函数作为输入：

def tenx(x):
	return 10*x

def twice(f,x):
	return f(f(x))
print(twice(tenx,2))

但是在Java 中，变量不能包含指向函数的指针。所以利用接口继承来实现函数的嵌套调用：

public interface IntUnaryFunction {
    int apply(int x);//输入一个整数，处理后是一个整数
}
public class TenX implements IntUnaryFunction {
    public int apply(int x) {
        return 10 * x;
    }
}
public static int do_twice(IntUnaryFunction f, int x) {
    return f.apply(f.apply(x));
}
//System.out.println(do_twice(new TenX(), 2));

多态考虑一个静态类型为 Deque 的变量 deque 。在执行时，调用 deque.addFirst() 将取决于 addFirst 被调用时 deque 的运行时类型或动态类型。正如我们在上一章中看到的，Java 使用动态方法选择来决定调用哪个方法。