Author: Mike

问题背景

时间复杂度

• 平衡二叉树基于二叉查找树的特性，在查找的过程中，在每一层只会访问一个结点，也即平衡二叉树的时间复杂度与树的高度有关。
  对于一颗 满二叉树，时间复杂度为

故 O(n) = logN;

• 树的层数越少，查找数据的平均查找时间就会越少

  平衡二叉树是具有以下性质的二叉查找树：对于树中的任意一个结点，都有该结点的左子树的高度与右子树的高度之差的绝对值小于2。与普通的BST相比，AVL树只是多定义了旋转操作，使得当左右子树的高度差的绝对值大于或者等于2时，平衡树可以自动地进行树形调整，以重新满足上述性质。

存在的问题

当所给予的关键字序列是有顺序的时候，将会出现如下尴尬的二叉树。树的结构会变为单向左子树或者单向右子树，二叉树退化为单向链表，时间复杂度为 O(n)，

结论

尽可能降低树的高度，主要是通过二叉树的旋转来达到降低树高度的目的，也就是接下来讨论的内容。

旋转

先来看几个概念

平衡因子

某结点的 左子树 与 右子树 的高度(深度) 差 即为该结点的平衡因子（BF,Balance Factor）。平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。
举例子如下, 结点旁边数据即为平衡因子

最小不平衡子树

最小不平衡子树以离插入结点最近、且平衡因子绝对值大于 1 的结点作根结点的子树。

结点失衡

调整失衡结点的手段为旋转操作，一共有日下四种旋转

• LL 在结点A的左孩子（L）的左子树（L）插入新结点导致不平衡 –> LL单右旋操作
  

• RR 在结点A的右孩子（R）的右子树（R）插入新结点导致不平衡 –> RR单左旋操作
  

• LR 在结点A的左孩子（L）的右子树（R）插入新结点导致不平衡 –> LR旋转。
  可以先假设在D结点有一个右孩子，为null，也即虚构的右孩子，由此可见 LR 旋转 = LL旋转 + RR旋转

具体例子

• RL 在结点A的右孩子（R）的左子树（L）插入新结点导致不平衡 –> RL旋转，与LR旋转的理论类似，RL 旋转 = RR旋转 + LL旋转

具体例子

操作

平衡二叉树的增删查改操作
https://zhuanlan.zhihu.com/p/25320155?refer=hinus

结点定义

1
2
3
4
5
6
7
8
9
10
11
12
13

public class AVLNode<T extends Comparable> {
    public AVLNode<T> left;
    public AVLNode<T> right;
    public T data;
    public int height;

    public AVLNode(T data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.height = 1;
    }
}

LL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
     * 左左单旋转(LL旋转) w变为x的根结点, x变为w的右子树
     *
     * @param x
     * @return
     */
    private AVLNode<T> singleRotateLeft(AVLNode<T> x) {
        //把w结点旋转为根结点
        AVLNode<T> w = x.left;
        //同时w的右子树变为x的左子树
        x.left = w.right;
        //x变为w的右子树
        w.right = x;
        //重新计算x/w的高度
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        w.height = Math.max(height(w.left), x.height) + 1;
        return w;//返回新的根结点
    }

RR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
     * 右右单旋转(RR旋转) x变为w的根结点, w变为x的左子树
     *
     * @return
     */
    private AVLNode<T> singleRotateRight(AVLNode<T> w) {

        AVLNode<T> x = w.right;

        w.right = x.left;
        x.left = w;

        //重新计算x/w的高度
        x.height = Math.max(height(x.left), w.height) + 1;
        w.height = Math.max(height(w.left), height(w.right)) + 1;

        //返回新的根结点
        return x;
    }

LR

1
2
3
4
5
6
7
8
9
10

/**
 * 左右旋转(LR旋转) x(根) w y 结点 把y变成根结点
 * @return
 */
private AVLNode<T> doubleRotateWithLeft(AVLNode<T> x){
    //w先进行RR旋转
    x.left=singleRotateRight(x.left);
    //再进行x的LL旋转
    return singleRotateLeft(x);
}

RL

1
2
3
4
5
6
7
8
9
10
11

/**
 * 右左旋转(RL旋转)
 * @param w
 * @return
 */
private AVLNode<T> doubleRotateWithRight(AVLNode<T> x){
    //先进行LL旋转
    x.right=singleRotateLeft(x.right);
    //再进行RR旋转
    return singleRotateRight(x);
}

插入

与BST（二叉查找树）的插入实现原理一样，使用递归算法，根据值大小查找到插入位置，然后进行插入操作，插入完成后，我们需要进行平衡判断，评估子树是否需要进行平衡修复，需要则利用上述的四种情景套入代码即可，最后要记得重新计算插入结点路径上的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

/**
* 插入方法
* @param data
*/
@Override
public void insert(T data) {
   if (data==null){
       throw new RuntimeException("data can\'t not be null ");
   }
   this.root=insert(data,root);
}

private AVLNode<T> insert(T data , AVLNode<T> p){

   //说明已没有孩子结点,可以创建新结点插入了.
   if(p==null){
       p=new AVLNode<T>(data);
   }else if(data.compareTo(p.data)<0){//向左子树寻找插入位置
       p.left=insert(data,p.left);

       //插入后计算子树的高度,等于2则需要重新恢复平衡,由于是左边插入,左子树的高度肯定大于等于右子树的高度
       if(height(p.left)-height(p.right)==2){
           //判断data是插入点的左孩子还是右孩子
           if(data.compareTo(p.left.data)<0){
               //进行LL旋转
               p=singleRotateLeft(p);
           }else {
               //进行左右旋转
               p=doubleRotateWithLeft(p);
           }
       }
   }else if (data.compareTo(p.data)>0){//向右子树寻找插入位置
       p.right=insert(data,p.right);

       if(height(p.right)-height(p.left)==2){
           if (data.compareTo(p.right.data)<0){
               //进行右左旋转
               p=doubleRotateWithRight(p);
           }else {
               p=singleRotateRight(p);
           }
       }
   }
   else
    ;//if exist do nothing
   //重新计算各个结点的高度
   p.height = Math.max( height( p.left ), height( p.right ) ) + 1;

   return p;//返回根结点
}

Author: Harry

一、单链表

说到链表，我们可以结合数组的一些特性进行分析。数组和链表都有各自的特性，下面我们就先从数组的一些局限性进行分析。

数组

基本的数组操作我就不再讲了，我们可以定义一个大小为5的数组a，然后初始化一些数据a[0]=1，a[1]=2，a[2]=3，如图。

现在想要在数组的第三个位置插入一个数，这时数组执行的操作将a[2]的数据拿出，然后再插入到a[3],最后将数据插入a[2]。

如果插入数据时发现数组的容量已经满了，这时操作就更加麻烦了，需要初始化一个更加大容量的数组将原有的数据拷贝到新数组，然后再执行插入操作。
这里只说了插入操作，同样的删除操作也是一个麻烦的事情。这时候我们就可以使用链表进行操作，可以体现出链表的优势。

链表

通过上面看到一些数组的局限性，从而我们就想有没有什么方法可以避免数组的容量局限性。
这样我们就想到了链表，链表可以快速的实现增删改操作而不必关注扩容问题,链表的概念我就不过多赘述了，如图：

在链表中插入一项：

首先来看一下我定义的一个单链表节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Node {
    private int data;
    private Node next;
    public Node(int data){
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

这是一个简单的链表结构，包含的内容有data和next，后面会讲到双链表和泛型的结合使用。
这里是单链表的一些简单操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

import singlelink.module.Node;

public class SingleLink {
    public int size;
    private Node first;
    private Node last;

    public SingleLink(){
        size = 0;
        this.first = null;
        this.last = null;
    }

    public boolean insertLast(int data){
        if(this.first == null){
            first = new Node(data);
        }else {
            Node node = new Node(data);
            last.setNext(node);
            last = node;
        }
        size++;
        return true;
    }

    public boolean insertFirst(int data){
        if(first == null){
            first = new Node(data);
            last = first;
        }else {
            Node node = new Node(data);
            node.setNext(first);
            first = node;
        }
        size++;
        return true;
    }

    public boolean insertByIndex(int index, int data){
        if(index > (size + 1) || index < 1 ){
            return false;
        }else if(index == 1){
            insertFirst(data);
        }else {
            Node node = new Node(data);
            Node tmp = first;
            for(int i = 1; i < index - 1; i++ ){
                tmp = tmp.getNext();
            }
            node.setNext(tmp.getNext());
            tmp.setNext(node);
        }
        size++;
        return  true;
    }

    public boolean deleteByIndex(int index){
        if(index > size || index <= 0){
            return false;
        }else if(index == 1){
            Node node = first.getNext();
            first = node;
        }
        else {
            Node tmp = first;
            for(int i = 1; i <= index - 2; i++){
                tmp = tmp.getNext();
            }
            tmp.setNext(tmp.getNext().getNext());
        }
        size--;
        return true;
    }

    public boolean queryData(int data){
        Node temp = first;
        int index = 1;
        while (temp != null){
            if(temp.getData() == data){
                System.out.println("found data and it index is: " + index);
                return true;
            }
            index++;
            temp = temp.getNext();
        }
        return false;
    }
    
    public void display(){
        Node node = first;
        System.out.println("first -> last :");
        while (node != null){
            System.out.print(node.getData() + "->");
            node = node.getNext();
        }
    }

}

我们可以看到，链表在增删改的时候是比较好操作的，刚好避免了数组这一方面的不足，不用担心扩容的问题。
但是链表有优势的同时也有不足，在查找的时候，每一次都需要从头到尾遍历一次，使得时间复杂度变高。

二、双链表

双向链表，顾名思义就是可以通过对当前节点，可以知道上一个节点和下一个节点，如图：

链表的节点定如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Node<T> {
    private Node<T> left;
    private Node<T> right;
    private T data;
    public Node(T data){
        this.data = data;
    }

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

这里我使用到了泛型来定义节点，这里同样的含有data，只不过这里的data我没有指定类型，可以方便存储不同类型的数据，在例子中我使用到的是User对象，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class User {
    private String name;
    private int age;

    public User(String name, int age){
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

链表中的操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

import doublelink.module.Node;
import java.util.Comparator;

public class DoubleLink<T> {
    private int size;
    private Node<T> first;
    private Node<T> last;
    public DoubleLink(){
        this.size = 0;
        this.first = null;
        this.last = null;
    }

    public int getSize() {
        return size;
    }

    public boolean insertFirst(T data){
        if(first == null){
            first = new Node<T>(data);
            last = first;
        }else {
            Node<T> temp = new Node<T>(data);
            temp.setRight(first);
            first.setLeft(temp);
            first = temp;
        }
        size++;
        return true;
    }

    public boolean insertLast(T data){
        if(first == null){
            first = new Node<T>(data);
            last = first;
        }else {
            Node<T> node = new Node<T>(data);
            node.setLeft(last);
            last.setRight(node);
            last = node;
        }
        size++;
        return true;
    }

    public T queryData(int index){
        if(index < 1 || index >size){
            System.out.println("You input index invalid!");
            return null;
        }
        else if(index == 1){
            return first.getData();
        }else {
            Node<T> temp = first;
            for(int i = 1; i <= index - 1; i++){
                temp = temp.getRight();
            }
            return temp.getData();
        }
    }

    public void display(){
        Node<T> node = first;
        while (node != null){
            System.out.print(node.getData().toString() + "->");
            node = node.getRight();
        }
    }

    public boolean remove(Object o) {
        if (o == null) {
            for (Node<T> x = first; x != null; x = x.getRight()) {
                if (x.getData() == null) {
                    unlink(x);
                    return true;
                }


            }
        } else {
            for (Node<T> x = first; x != null; x = x.getRight()) {
                if (o.equals(x.getData())) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    public boolean removeFirst(){
        if(size > 0){
            unlink(first);
            return true;
        }else {
            return false;
        }
    }

    public boolean removeLast(){
        if(size > 0){
            unlink(last);
            return true;
        }else {
            return false;
        }
    }

    T unlink(Node<T> x) {
        final T element = x.getData();
        final Node<T> right = x.getRight();
        final Node<T> left = x.getLeft();

        if (left == null) {
            first = right;
        } else {
            left.setRight(right);
            x.setLeft(null);
        }

        if (right == null) {
            last = left;
        } else {
            right.setLeft(left);
            x.setRight(null);
        }

        x.setData(null);
        size--;
        return element;
    }

    public T removeByComparator(T data,Comparator<T> comparator){
        if(comparator == null){
            return null;
        }else {
            for (Node<T> x = first; x != null; x = x.getRight()) {
                if (comparator.compare(data, x.getData()) == 0) {
                    return unlink(x);
                }
            }
        }
        return null;
    }
}

我需要讲一下的是remove操作，这里我使用了两种remove的方法，一种的仿照JDK的remove方法，是通过equal比较对象是否为同一个，然后再删除，这个需要查找到已经存在的对象，才能删除。
另外一种是我使用了Comparator接口，重写了compare方法，从而使得删除数据更加灵活，只需要写一个比较器传入就可以remove了。

这里写了两个比较器，一个是比较所有内容，另外一个只比较名字，可以根据需求定义不同的比较器，灵活性更好。

1
2
3
4
5
6
7
8

public class UserAllInfoComparator implements Comparator<User> {
    public int compare(User user1, User user2) {
        if(user1.getName().equals(user2.getName()) && user1.getAge() == user2.getAge()){
            return 0;
        }
        return -1;
    }
}

1
2
3
4
5
6
7
8

public class UserNameComparator implements Comparator<User> {
    public int compare(User user1, User user2) {
        if(user1.getName().equals(user2.getName())){
            return 0;
        }
        return -1;
    }
}

三、队列

说到队列，我们大概来看一下Java中容器的关系，如图：

单向队列

单向队列是单向的，只能从一边进来，另一边出去，而且是先进先出，与栈刚好相反。我们可以用数组模拟，也可以用链表实现。其原理如图：

双向队列

双向队列可以重两边进来，同样可以从两边出去，如图：

循环队列

这里有数组实现了一个简单循环队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

public class Deque {
    private int[] data;
    private int head;
    private int tail;
    private int length;
    private final static int DEFAULT_SIZE = 10;

    public int getLength() {
        return length;
    }
    public Deque(){
        data = new int[DEFAULT_SIZE];
        head = 0;
        tail = 0;
        length = 0;
    }

    public Deque(int size){
        if(size > 0){
            data = new int[size];
        }else {
            data = new int[DEFAULT_SIZE];
        }
        head = 0;
        tail = 0;
        length = 0;
    }

    public boolean isFull(){
        return length == data.length;
    }

    public boolean isEmpty(){
        return length == 0;
    }

    public boolean insertLast(int element){
        if(!isFull()){
            data[tail] = element;
            length++;
            if(!isFull() && tail <= data.length - 2 && (tail + 1 != head)){
                tail++;
            }else if(!isFull() && tail == data.length - 1 && head != 0){
                tail = 0;
            }else if(isFull()){
                tail = head;
            }
            return true;
        }else {
            System.out.println("The queue is full!");
            return false;
        }
    }

    public int removeFirst(){
        if(!isEmpty() && head < data.length - 1){
            head++;
            length--;
            return data[head-1];
        }else if(!isEmpty() && head == data.length - 1){
            head = 0;
            length--;
            return data[data.length - 1];
        }else {
            head = tail;
            System.out.println("The queue is empty!");
            return 0;
        }
    }
}

其实队列的实现使用链表比使用数组好很多，读者可以自己用链表实现一下。

Author: Kelvin

一、什么是数据结构

  数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。在初学阶段，你可以认为数据结构就是关于数据在计算机中如何组织的一门课程。

  比如，我要往一个数组中，存1，3，2这三个整数，那么，我实际存的时候，是按照从小到大排着存呢，还是从大到小存，还是没有顺序随便存，这要根据实际的需求来决定。根据需求决定数据存储的方式。这就是数据结构要研究的内容.

二、什么是栈

  栈是一种数据结构。栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行，最大的特点就是先进后出。

  想一想，生活中，有很多栈的例子。比如叠在一起的碗盘，叠的时候我们是从底往高处叠，但是取的时候，我们是从最上面的一个依次向下取。这也是一个典型的栈：后进先出，先进后出。

三、栈的实现

• 使用int数组

  1 2 3 4 5 6 7 8 9 10

  public class Stack { private int[] data; private int size; private int top = 0; // 指向栈的顶部 public Stack(int size) { this.size = size; this.data = new int[size]; } }

• 使用泛型

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

  package cn.kelvin.stack; import java.util.ArrayList; import java.util.Arrays; import java.util.Stack; public class MyStack<T> { Object[] datas = {}; int size; int top=0; public MyStack() { } public MyStack(int size){ this.size = size; datas = new Object[size]; } //压栈操作 public void push(T t){ ensureCapacity(top); datas[top++] = (Object) t; } //当栈中的元素超出最大容量时扩容 private void ensureCapacity(int newSize) { if(newSize>=size){ size = (int)(Math.round(size + size*1.5+1)); datas = Arrays.copyOf(datas,size); } } //出栈操作 public T pop(){ if(top<=size && top>0){ return (T) datas[--top]; } return null; } //访问栈顶元素 public T getTop(){ int n = top - 1; if(n<size && n>=0){ return (T) datas[n]; } return null; } public int size(){ return top; } public boolean isEmpty(){ return top==0; } }

  也可以使用java中的list来作为stack的底层元素容器，读者可以自己尝试去实现。另外可以去看看jdk中stack的相关实现，读源代码是最好的学习方式。

四、栈的应用

  栈在计算机编程中可以说是最基础也是最重要的数据结构了。其功能之强大，可能出乎很多人的意料。

• 使用栈实现括号间的匹配验证（使用上文中泛型栈）

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

  public static boolean isMatch(String matchStr){ MyStack<Integer> stack = new MyStack<>(); char[] chs = matchStr.toCharArray(); for(int i=0;i<chs.length;i++){ if(chs[i]=='(' || chs[i]=='[' || chs[i]=='{'){ stack.push(Integer.valueOf(chs[i])); }else { if(stack.isEmpty()){ System.out.println("stack empty"); return false; }else{ if(')'==chs[i]){ if((stack.getTop()+1)==Integer.valueOf(chs[i])){ stack.pop(); }else{ System.out.println("not match"); return false; } }else if(']'==chs[i] || '}'==chs[i]){ if((stack.getTop()+2)==Integer.valueOf(chs[i])){ stack.pop(); }else{ System.out.println("not match"); return false; } }else { return false; } } } } if(stack.isEmpty()){ return true; } return false; }

该程序仅支持 ({[ 之间的匹配，对于输入包含其他字符的字符串，会直接return false，读者可以自行输入测试。

• 使用栈实现后缀表达式求值
  该程序的实现需要借助另一个工具类：TokenStream, 该类是对System.in的一个适配器类。TokenStream接口定义：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

  public interface TokenStream { public Token getToken() throws IOException; public void consumeToken(); } public class Token { public enum TokenType { LPAR, RPAR, PLUS, MINUS, MULT, DIV, INT, NONE, } TokenType tokenType; Object value; public Token(TokenType tokenType, Object value) { this.tokenType = tokenType; this.value = value; } @Override public String toString() { String val = String.valueOf(value); try { Integer.valueOf(val); return "{" + tokenType + ", INTEGER(" + value + ")}"; } catch (Exception e) { return "{" + tokenType + ", " + '"'+val+'"' + "}"; } } public TokenType getTokenType() { return tokenType; } public void setTokenType(TokenType tokenType) { this.tokenType = tokenType; } public Object getValue() { return value; } public void setValue(Object value) { this.value = value; } }

• 我的一个实现类（实现的方法应该会有所差异，读者可以尝试去使用自己的方式实现）

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

  package cn.kelvin.adapter; import java.io.IOException; import java.io.InputStream; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import cn.kelvin.adapter.Token.TokenType; public class MyTokenStream implements TokenStream{ private int tokenIndex=0; private List<Token> tokenCache = new ArrayList<>(); InputStream in; @SuppressWarnings("resource") public MyTokenStream(InputStream in) { this.in = in; String input = new Scanner(in).nextLine(); parseInput(input); } private void parseInput(String input) { if(null==input || "".equals(input)){ return; } int i=0; while(i<input.length()){ char ch = input.charAt(i); switch (ch) { case '(': tokenCache.add(new Token(Token.TokenType.LPAR, String.valueOf(ch))); break; case ')': tokenCache.add(new Token(Token.TokenType.RPAR, String.valueOf(ch))); break; case '+': tokenCache.add(new Token(Token.TokenType.PLUS, String.valueOf(ch))); break; case '-': tokenCache.add(new Token(Token.TokenType.MINUS, String.valueOf(ch))); break; case '*': tokenCache.add(new Token(Token.TokenType.MULT, String.valueOf(ch))); break; case '/': tokenCache.add(new Token(Token.TokenType.DIV, String.valueOf(ch))); break; default: try { Integer num = Integer.valueOf(String.valueOf(ch)); tokenCache.add(new Token(Token.TokenType.INT, num)); } catch (Exception e) { // e.printStackTrace(); } break; } i++; } } @Override public Token getToken() throws IOException { if(tokenIndex<tokenCache.size()){ return tokenCache.get(tokenIndex); } return new Token(TokenType.NONE, null); } @Override public void consumeToken() { tokenIndex ++; } }

• java虚拟机的实现是基于栈的
  
  这里举一个简单的例子来说明在java虚拟机中是如何使用栈。Java虚拟机规范里定义了Java所使用的字节码。我们知道Java文件要先编译成字节码文件，也就是class文件，请看example：

  1 2 3 4 5

  public class Main { // Main.java public static int add(int a, int b){ return a + b; } }

• 执行javac Main.java（或者javap -c Main）后可以看到编译后的字节码：

  1 2 3 4 5 6

  public static int add(int, int); Code: 0: iload_0 1: iload_1 2: iadd 3: ireturn

add 函数被编成了四条字节码指令，这四条字节码是什么意思呢？

你可以认为Java的每一个函数都有一个操作数栈，每条指令就是在对这个操作数栈进行操作。比如 iload_0，就代表把第一个参数 push 进操作数栈，iload_1代表把第二个参数 push 进操作数栈，而 iadd 代表，从栈上连续pop两次，取两个数，将其相加，再把结果送到栈上。ireturn 则表示把栈顶的值做为返回值传给调用者。Java字节码的整个执行过程都是在这样一个栈上的。如果用图来表示，这四个步骤就是:

• iload_0，使a先进栈

• iload_1， 使b进栈

• iadd，做了三件事情，b 和 a 出栈，计算 a+b，将计算结果入栈：

• ireturn 将当前栈顶的值返回出去。

Author: Oscar

目录

• 基础题目
• 计算二进制数中1的个数
• 异或
• 巧解找数字问题

基础题目

当执行乘法，除法和模运算时，有出现关于2的整数次幂的，往往可以使用位操作来解决。例如，求n mod 16，比较好的写法是

1

int t = n & 0xf; // not n % 16

判断一个数的奇偶性

1
2
3
4

// 奇数返回 true
boolean isOdd(int n) {
    return n & 1 == 1;
}

对整数n乘(除)以2的整数次幂，可以使用左(右)移来实现，而不是直接乘或者除。有一道笔试题，不准使用乘法，实现 n*7 ，答案是

1
2

n << 3 − n;
// 当然，也可以使用 n << 2 + n << 1 + n，这种办法要差一些。

计算二进制数中1的个数

一个整数，要求去掉它的二进制表示法的最后一次出现的1，例如， 110，去掉最后一个1就是100。

1
2
3
4

int expellOne(int a) {
    //a的最后一个1的位置，对应于a-1是0
     return a & (a − 1);
}

统计整数转成二进制后总共有多少位是1。例如110，统计的结果就是2。

1
2
3
4
5
6
7
8

int calcOnes(int a) {
    int count = 0;
    while(a != 0) {
        a = expellOne(a);
        count++;
    }
    return count;
}

异或

异或是按位操作，相同为0，不同为1。异或有三个特点：

1. 0^0=0,0^1=1 0异或任何数＝任何数
2. 1^0=1,1^1=0 1异或任何数－任何数取反
3. 任何数异或自己＝把自己置0
   

因此，在汇编语言中，经常使用“xor ax, ax”这样的语句来清零寄存器。异或遵循结合律和交换律，从而有“a xor b xor a = a xor a xor b = (a xor a) xor b = 0 xor b = b”。

不使用第三个变量，交换整型变量 a 和 b 的值。可以使用异或来解决。代码是:

1

a = a ˆ b, b = a ˆ b, a = a ˆ b;

巧解找数字问题

一个整型数组里除了一个数字之外，其他的数字都出现了两次。请找出这个数字。

我们可以使用异或来解决这个问题，把数组里的所有元素全部进行异或操作。由于异或操作的交换律和结合律我们知道，所有出现了两次的数字，都与自己先结合进行运算，那么结果就是0，最后，剩下的那个数字就是要找的数字。

1
2
3
4
5
6
7
8
9
10

public class Demo03_05_02 {
    public static void main(String[] args) {
        int [] nums = {1,3,5,6,8,9,5,6,1,3};
        int result = 0;
        for(int num : nums){
            result^=num;
            System.out.println("result:"+result);
        }
    }
}

如果数组中只出现了一次的数字有两个，而其他数字都出现了两次呢？

思路是，如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照上一题的办法就可以分别求出这两个只出现一次的数字了。

还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或的过程中全部抵消掉了。由于这两个数字不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至 少就有一位为1。我们在结果数字中找到第一个为1的位的位置，记为第 N 位。这两个数字不 同，意味着为1的那个位是相异的。现在我们以第 N 位是不是 1 为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第 N 位都为1，而第二个子数组的每个数字的第 N 位都为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class Demo03_05_03 {

    public static void main(String[] args) {
        int[] nums = {2, 3, 6, 4, 5, 3, 4, 6};
        findNums(nums, nums.length);
    }

    public static int findNums(int[] data, int length) {
        int num1 = 0;
        int num2 = 0;

        if (length < 2)
            return -1;

        int ansXor = 0;
        for (int i = 0; i < length; i++)
            ansXor ^= data[i];               //异或

        int pos = findFirstOne(ansXor);
        for (int i = 0; i < length; i++) {
            if (testBit(data[i], pos))
                num1 ^= data[i];
            else
                num2 ^= data[i];
        }
        System.out.println("the two numbers are " + num1 + " and " + num2);
        return 0;
    }

    public static int findFirstOne(int value)  //取二进制中首个为1的位置
    {
        int pos = 0;
        while ((value & 1) != 1) {
            value = value >> 1; //向右移一位
            pos++;
        }
        return pos;
    }

    public static boolean testBit(int value, int pos) //测试某位置是否为1
    {
        return ((value >> pos) & 1) != 0;
    }
}

1-1000中少了两个数，找出没有出现的两个数，数组是无序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class Demo03_05_04 {

    public static void main(String[] args) {
        int[] num = {1, 3, 5, 7, 2, 6, 9, 0, 0, 10};
        int num1 = 0;
        int num2 = 0;
        findLostTwo(num, num.length, num1, num2);
    }

    public static void findLostTwo(int num[], int length, int num1, int num2) {
        int temp = 0;
        int i;
        //返回的temp就是缺失的两个数的异或
        for (i = 0; i < 10; i++) {
            temp ^= (i + 1);
            temp ^= num[i];
        }
        int first_not_zero = 1;
        while ((temp & 1) == 0) {
            first_not_zero++;
            temp = temp >> 1;
        }
        for (i = 0; i < 10; i++) {
            if (testBit(i + 1, first_not_zero - 1))
                num1 ^= (i + 1);
            else
                num2 ^= (i + 1);
            if (testBit(num[i], first_not_zero - 1))
                num1 ^= num[i];
            else
                num2 ^= num[i];
        }
        System.out.println("num1:" + num1 + ",num2:" + num2);
    }

    public static boolean testBit(int value, int pos) //测试某位置是否为1
    {
        return ((value >> pos) & 1) != 0;
    }

}

Author: Oscar

目录

• 递归算法
• BNF范式
  • 定义
  • 终结符和非终结符
  • 语法
• 递归下降求值法

递归算法

1. 递归算法是把问题转化为规模缩小了的同类问题的子问题，然后递归调用函数（或过程）来表示问题的解。子问题与原始问题为同样的事情，且更为简单
   
2. 不能无限的调用本身，须有个出口。

BNF范式

定义

BNF范式也叫巴科斯范式，它奠定了现代计算机的基础。它以递归方式描述语言中的各种成分，凡遵守其规则的程序就可保证语法上的正确性。BNF由于其简洁、明了、科学而广泛接受，成为描述各种程序设计语言的常用工具。

终结符和非终结符

终结符：不能单独出现在推导式左边的符号，即不能再进行推导，是不可再拆分的最小元素。

非终结符：可理解为一个可拆分的元素

语法

公式： <符号> ::= <使用符号的表达式1>|<使用符号的表达式2>

这里的<符号>是非终结符，即可以继续拆分，用<>括起来的是非终结符。::=和:=是同一个意思，都表示为定义。| 表示或，即可用表达式1或表达式2

示例

<句子> ::= <主语> <谓语> <宾语>

<谓语> ::= <动词> | <动词短语>

<主语> ::= 你 | 我 | 他

<句子><谓语><主语><宾语>等等带<>的，都是非终结符，可以继续拆分，而你我他则是最小元素，不可拆分。

递归下降

传统上，编写语法分析器有两种方法，一种是自顶向下，一种是自底自上。自顶向下是从起始非终结符开始，不断地对非终结符进行分解，直到匹配输入的终结符；自顶向下方法就是我们所说的递归下降。

示例

使用BNF语法分析简单的四则运算表达式（一元多项式）

如：1 + 3 * (4 + 2)

1 2 3 4 5 6 7 8 9 10

<expr> ::= <expr> + <term> | <expr> - <term> | <term> <term> ::= <term> * <factor> | <term> / <factor> | <factor> <factor> ::= ( <expr> ) | Num

有了BNF方法后，采用递归向下的方法来实现编译器是很直观的。

Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

public class MyParser {
    public static int pos = 0;

    public static double expr(char[] s) {
        double t = term(s);
        while (s[pos] == '+' || s[pos] == '-') {
            if (s[pos] == '+'){
                pos++;
                t = t + term(s);
            }
            else if (s[pos] == '-'){
                pos++;
                t = t - term(s);
            }
        }
        return t;
    }

    public static double term(char[] s) {
        double t = factor(s);
        while (s[pos] == '*' || s[pos] == '/') {
            if (s[pos] == '*'){
                pos++;
                t = t * factor(s);
            }
            else if (s[pos] == '/'){
                pos++;
                t = t / factor(s);
            }
        }
        return t;
    }

    public static double factor(char[] s) {
        if (s[pos] == '('){
            pos++;
            double t = expr(s);
            if (s[pos] == ')'){
                pos++;
            }
            return t;
        }else{
            int t = 0;
            while('0' <= s[pos] && s[pos] <= '9'){
                t = t * 10 + s[pos] - '0';//t * 10 处理两位数以上;char[pos] - '0' =>'8'->int 8
                pos++;
            }
            return (double)t;
        }
    }

    public static void main(String[] args){
        String expression = "1+3*(4+2)#";
        double result = expr(expression.toCharArray());
        System.out.println("result : "+result);
    }

}

Author: Oscar

目录

• 堆的介绍
• 堆的工作过程

堆的介绍

Java把内存划分为两种，一种是栈内存，另外一种是堆内存。 在函数中定义的一些基本类型的变量和对象的引用变量都是在函数的栈内存中分配的，而一般new出来的对象或者定义的数组，则分配到堆内存。

栈内存和堆内存区别之一是，栈内存能够在方法执行完后，自动出栈，自动销毁方法里的变量。而堆内存的对象需要交给Java的垃圾回收器处理,即垃圾回收机制。

在创建对象的时候，真正的对象存放在堆里，而对象的引用地址则存放在栈里。

堆的工作过程

示例

1
2
3
4
5
6
7
8
9
10
11
12

public class Demo03_01_05 {
    public static void main(String args[]) {
        A a = new A();       
        a.num = 5;           
        A aa = a;            
        aa.num = 6;
        System.out.println(a.num); 
    }
}
class A {
    int num = 4;
}

过程分析

1. 当new A()时，A()放在堆里，同时num=4也在堆里，变量a 放在栈里，A()引用地址 0x005赋值给a
   
2. a.num = 5，修改了A()里num的值为5
   
3. A aa = a时，变量a把A()的引用地址赋值给变量aa，因此aa和a同时指向了A()
   
4. aa.num = 6，修改了A()里num的值为6
   
5. 如果变量a和aa都设为null，这时就没有变量引用这个对象，这个对象就成为了垃圾，Java的垃圾处理器就会在一定的时间内把这个对象回收。
   

传递String类型

1
2
3
4
5
6
7
8
9
10

public class Demo03_02_01 {
    public static void main(String args[]) {
        String a = "a";
        change(a);
        System.out.println("a:"+a);
    }
    public static void change(String a) {
        a = "b";
    }
}

java中String类型也是对象型变量，所以它传递的是引用的副本。String是一个非可变类，当字符串发生变化时，会自动生成一个新的String对象。

Author: Oscar

目录

• 函数与方法的区别
• Java调用方法的过程

函数与方法的区别

函数与方法在不同的场景下，叫法不同。函数一般出现在面向过程，比如C语言，通过函数名就可以调用这个函数。而方法一般出现在面向对象，与对象相关联，通过对象调用里面的方法。

Java调用方法的过程

当Java启动一个线程的时候，就会创建一个栈。每当线程执行一个方法的时候，就会压入一个栈帧。只有处于栈顶的栈帧才是最有效的，称为当前栈帧，即当前方法。注意，当前方法没有返回或抛异常中断时，当前栈帧是不会出栈的。

栈帧：主要由四部分组成，分别是局部变量表（Local Stack Frame）、操作数栈（Operand Stack）、动态链接（Dynamic Linking）以及返回地址（Reture Address）。

• 局部变量表：保存函数的参数以及局部变量用
• 操作数栈：存放一些操作后的结果
  

示例

Java Code :

1
2
3
4
5
6
7

public class Main {
    public static void main(String args[]) {
        int a = 1;
        int b = 2;
        int t = a + b;
    }
}

ByteCode

1
2
3
4
5
6
7
8
9

0: iconst_1  //把常量1 放到操作数栈顶
1: istore_1  //从操作数栈取出栈顶的值，并将其存入局部变量表里的第一个位置，可以理解为索引为1
2: iconst_2  //把常量2 放到操作数栈顶
3: istore_2  //从操作数栈取出栈顶的值，并将其存入局部变量表里的第二个位置，可以理解为索引为2
4: iload_1   //把局部变量表的第一个位置，及索引为1的值，放入操作数栈的栈顶
5: iload_2   //把局部变量表的第二个位置，及索引为2的值，放入操作数栈的栈顶
6: iadd      //把操作数栈的两个数取出来，求和，再把结果放入操作数栈的栈顶
7: istore_3  //从操作数栈取出栈顶的值，并将其存入局部变量表里的第三个位置，可以理解为索引为3
8: return

栈帧组成结构

习题一

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Main {
    public static void main(String args[]) {
        int a = 1, b = 2;
        swap(a, b); 
        System.out.println("a is " + a + ", b is " + b); 
    }   

    public static void swap(int a, int b){ 
        int t = a;
        a = b;
        b = t;
    }   
}

方法调用过程

1.当主线程启动的时候，就会创建一个栈。执行main函数，创建main帧，并压入栈。

2.当主线程执行swap方法时，创建swap帧，并压入栈，注意：同时把main帧的a=1,b=2的数值也拷贝一份，在swap帧也创建了变量a和b，因此，修改swap帧的变量，也不会影响main帧的变量。经过一系列操作，swap帧里的变量a=2，b=1，t=1。这是传值，适用于Java的基础数据类型，如int,float,double等等

3.当执行完swap方法时，swap帧就会出栈，swap帧里的变量a,b,t也会随着出栈而被回收。

习题二

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class Main {
    public static void main(String args[]) {
        int n = 5;
        int t = fact(n);
        System.out.println(t);
    }

    public static int fact(int n){
        if (n == 0)
            return 1;
        else
            return n * fact(n - 1);
    }
}

方法调用过程

Author: Yellow

进击的Java新人Week.1学习笔记

Week.1的课程主要包括以下几部分:

1. 有符号整数在计算机中的表示、不同进制之间的转换；
2. Java中static、final关键字；
3. Java中自动装箱拆箱的坑

有符号整数在计算机中的表示、不同进制之间的转换

1. 原码、反码与补码

对于有符号（sign）整数来说，由于其最高位要用来表示符号 （0 = 非负，1 = 负），所以其能表示的数的最大绝对值要比无符号数小一半。已Java中的byte来作为例子，由于其长度为8bit，所以其表示范围为-128~127（即-2^7 ~ 2^7-1，为什么右边要减一？因为“0”占了一个位置啊）。

对于正数来说，它的原码、反码、补码都等于其二进制形式。

对于负数来说，它的原码、反码、补码是不同的：

1. 原码：把符号位设为1，后面的数字等于这个负数的绝对值，例如-15就变成了10001111。
2. 反码：在原码的基础上，保持符号位不变，后面的数字全部取反，例如-15就变成了11110000。
3. 补码：它是由反码加1得到的。例如，-1的反码是11111110，再加1就是11111111。

使用补码的好处包括，0和-0的表示是相同的，正负数可以直接进行加减法运算，不必再做额外的转换。而原码和反码则不具备这样的优点。所以现代计算机都是使用补码来表示负数。

2. 不同进制之间的转换

首先，十进制和二进制的互换是最简单的。基本上十进制 -> 二进制就是通过除法求余数：

二进制 -> 十进制则是通过乘法：

对于任意进制之间的转换，基本就是先转成10进制, 再由10进制转换成目标进制的方法。

3. Java中数值类型的隐式转换

平时写程序时，如果二元运算符两边都是数字，则要特别注意其中隐式转换的坑：

1. Byte.MAX_VALUE + 1 会隐式向上转型成int（字面量“1”被认为是int）
2. 向上提升时会保持符号位
3. 向下转型时会丢失精度或符号位
4. byte -> short,char → int → long → float → double（从左往右精度不断上升）
5. boolean不能转换成数值

4. “老鼠喝毒药”的解法

没看过题目的可以先看题目。

本质上是用每一只老鼠表示二进制的每一个bit, 则10只老鼠能组合成2^10=1024种组合.

则1000杯水可以按序号用二进制编码:

第1杯 -> 00000 00001

第2杯 -> 00000 00010

第3杯 -> 00000 00011

….

然后第n杯酒就让二进制bit为1的老鼠喝, 看看谁挂掉, 由挂掉老鼠的bit就知道是对应哪杯水