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

week1

5.15

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

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

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

static，静态方法，由类本身执行的操作。

x = Math.sqrt(100);
非静态方法，实例方法，只能由类的特定实例执行。

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的元素。

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的2048。难绷的是，2048的tilt机翻成“倾斜”，其实是向某个方向滑动所有方块的意思。

5.23

先完成proj0 的前几个方法，对于tilt,只需要完成一个方向，其余的则使用board.setViewingPerspective(side)。算法思想是分两步走，移动+合并+移动。对于移动的实现，从上到下，对每个pos 一一确认。从顶部开始，如果非空，则移动到pos ，然后一个pos 就确认好了。如果为空，那么当前的pos 就没有被确认。

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。也就是说：

引入双指针prev和next。
两端加入哨兵节点。亦或是构造循环链表，共用一个哨兵节点。
代码实现会在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:

1	Glorp[] items = new Glorp[8];

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

1	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 运行一个被覆盖的方法时，它会在其动态类型中搜索适当的方法签名并运行它。
这一块还不太理解。