读书笔记-算法

几个对数组的算法

1， 找出数组中的最大值：

1
2
3
4
5

double max = a[0];

for(int i = 1; i < a.length; i++)

    if(a[i] > max) max = a[i];

//把最大值马上设定为数组的第一个元素，然后遍历数组，如果有别当前这个最大值更大的元素，则把最大值更新，直到遍历结束；

2， 计算数组的平均值：

1
2
3
4
5
6
7

double sum = 0.0;

for(int i = 0; i < a.length; i++)

    sum += a[i];

double average = sum / a.length;

//算出总值，然后除以数组的元素数；

3，复制数组：

1
2
3
4
5
6
7

double[] b = new double[a.length];

for(int i = 0; i < a.length; i++) 

    b[i] = a[i];

//new 一个和原数组同length同类型的数组，然后遍历赋值每个元素；

4，颠倒数组元素的顺序：

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

double [] b = new double[a.length];

for(int i = a.length - 1, j = 0; i > -1 && j < b.length ; i--, j++) 

    b[j] = a[i];

//这是个直观低效率算法，时间消耗(a.length)，空间消耗(2 * a.length)，并且有两个循环指数i, j；

for(int i =0; i < a.length / 2; i++) {

    double temp = a[i];

    a[i] = a[a.length - 1 - i];

    a[a.length - 1 - i] = temp;
}

偶数个元素的交换过程：

< 2 1, 2, 3, 4

0 4, 2, 3, 1

1 4, 3, 2, 1

奇数个元素的交换过程：

< 2 1, 2, 3, 4, 5

0 5, 2, 3, 4, 1

1 5, 4, 3, 2, 1

//可见，无论是偶数个还是奇数个元素，交换的次数都一样，都是a.length/2，偶数个的时候是全交换，奇数个的时候，是以中间的那个元素为中心点，其他元素都交换，中间元素并不在a.length/2的遍历范围内；这个算法，时间(a.length/2)，空间(a.length)；

5，a[][] * b[][] = c[][]， 矩阵相乘（方阵）：

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

int n = a.length;

double[][] c = new double[n][n];

for(int i = 0; i < n; i++)

    for (int j = 0; j < n; j++) {

        for(int k = 0; k < n; k++) //计算行i和列j的点乘

            c[i][j] += a[i][k] * b[k][j];

    }

典型静态方法的实现

1，计算整数的绝对值：

1
2
3
4
5

public static int abs(int x) {
    if(x < 0)    return -x;

    else    return x;
}

//绝对值的规则很简单：不小于零就是本身，反之就返回-x；

2， 计算浮点数的绝对值：

1
2
3
4
5

public static double abs(double x) {
    if( x < 0.0)    return -x;

    else    return x;
}

3， 判断一个数是否是素数：

1
2
3
4
5
6
7
8
9

public static boolean isPrime(int n) {
    if(n < 2)    return false;                        //大于1的自然数，1不是素数

    for(int i = 2; i * i <= n; i++) {              //i * i <=n

        if(n % i == 0)    return false;

    return true;
}

//素数，就是质数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。

判断的关键点：

a, 小于2，不是；

b，从2到n遍历，遍历到一个i i > n之前的数就提前结束遍历，因为2到满足i i <= n的i之间的这些数如果能整除n，那么i之后到n的这些数也能；以满足i * i <=n为分界线，1…n之间的数对于整除n来说，是对称的；

判断n能否被i整除：n % i 的值是否为0；

4， 计算平方根（牛顿迭代法）：

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

public static double sqrt(double c) {

    if(c < 0) return Double.NaN;

    double err =1e-15;                 //1乘以10的负15次方

    double t = c;

    while(Math.abs(t - c / t) > err *t)

        t = (c/t + t) / 2.0;
    return t;
}

//不懂， TODO

5， 计算直角三角形的斜边：

1
2
3
4

public static double hypotenuse(double a, double b) {

    return Math.sqrt(a * a + b * b);
}

6， 计算调和级数：

1
2
3
4
5
6
7
8
9
10

public static double H(int n) {

    double sum = 0.0;

    for(int i = 1; i <=n; i++) 

        sum += 1.0 / i;

    return sum;
}

//形如1/1+1/2+1/3+…+1/n+…的级数称为调和级数，它是 p=1 的p级数。 调和级数是发散级数。在n趋于无穷时其部分和没有极限（或部分和为无穷大）。

二分查找的递归和循坏实现法

递归总有一个最简单的情况-方法的第一条语句总是包含return的条件语句；

递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况;

递归调用的父问题和尝试解决的子问题之间不应该有交集；

二分查找：

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

public static int rank(int key, int[] a) {

    return rank(key, a, 0, a.length - 1);

}

public static int rank(int key, int[] a, int lo, int hi) {

    if(lo > hi)

        return -1;

    int mid = lo + (hi - lo) / 2;   //数组并没有被拆分，所以这里(hi - lo)/2必须再加上lo

    if(key < a[mid])     return rank(key, a, lo, mid - 1);

    else if(key > a[mid]     return rank(key, a, mid +1, hi);

    else     return mid;
}

//如果原始的方法参数不怎么适合递归或者不够递归方法，就另写一个满足要求的递归方法，用原始的调用之；

比如二分查找的时候，并没有给定递归时需要的低坐标和高坐标，如果坚持要在原始方法中使用递归，那么必须对数组进行拆分和复制，效率低下，浪费空间；

在不拆分数组的情况下，“父问题和子问题之间不应该有交集“， 所以mid不是简单的lo + hi /2了；mid不用再被传给子问题，因为== mid的话就是解了已经，低位传lo到mid-1；高位传mid + 1到hi；

循环实现：

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

int lo = 0;

int hi = a.length - 1;

while(lo <= hi) {

    int mid = lo + (hi - lo) / 2; //不拆分数组的话，始终是这个公式

    if(key < a[mi])     hi = mid - 1;

    if(key > a[mi])     lo = mid + 1;

    else     return mid;
}

return -1;

不用temp实现swap

1
2
3
4
5

a = a + b;

b = a - b;

a = a - b;

Dijkstra双栈算术表达式求值法

双栈：一个操作数栈，一个操作符栈；

从左到有遍历算数表达式：

1， 忽略左括号；

2， 将数字push入操作数栈；

3， 将运算符push入操作符栈；

4， 遇到有括号时，pop一个运算符，pop出所需数量的操作数，并将运算符和操作数的运算结果push入操作数栈。

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

public static double calc(String[] equation) {

    Stack<String> ops = new Stack<String>();

    Stack<Double> vals = new Stack<Double>();

    for(String s : equation) {

        if(s.equals("("))

            ;

        else if(s.equals("+"))

            ops.push(s);

        else if(s.equals("-"))

            ops.push(s);

        else if(s.equals("*"))

            ops.push(s);

        else if(s.equals("/"))

            ops.push(s);

        else if(s.equals("sqrt"))

            ops.push(s);

        else if(s.equals(")")) {

            String op = ops.pop();

            double v = vals.pop();

            if(op.equals("+")) 

                v = vals.pop() + v;

            if(op.equals("-")) 

                v = vals.pop() - v;

            if(op.equals("*")) 

                v = vals.pop() * v;

            if(op.equals("/")) 

                v = vals.pop() / v;

            if(op.equals("sqrt")) 

                v = Math.sqrt(v);

            vals.push(v);

        } else

            vals.push(Double.parseDouble(s));

    }

    return vals.pop();
}

这其实就是编译原理中的解释器。

应该也有其他方法，比如全部push入栈之后再依次出栈，前提是优先级用括号来明示。

堆栈的数组和链表实现以及队列的链表实现

堆栈的意义：

堆栈并不是为了迭代的一个容器，虽然它是一个可迭代的容器，但它不应该被应用于静态的数据存储场景；

堆栈应该应用于动态的运算、过滤等场景；

创建泛型类型的数组作为数据存储：

直接创建泛型数组是不可以的：T[] items = new T[2];

只能通过这种方式创建：T[] items = (T[])(new Object[2]);

动态增减数组大小：

动态增减的数组实现：没有高深的方法，就是new一个新的数组，把值拷贝过来，再把引用赋予新的数组对象：

1
2
3
4
5
6
7

T[] temp = (T[]) new Object[newLength];

for(int i = 0; i < N; i++)     //如果是减小数组，这里的条件需要修改

    temp[i] = a[i];

a = temp;

增：当数组满的时候，直接增加1倍；

减：当数组不满1/4的时候，减少至1/2；

以上是基于内存开销和性能之间的平衡，尤其是缩减数组，不能一个一个减，也不能不满1/2的时候直接减掉1/2，这样数组马上又满了，可能又需要增。

Stack内部使用动态增减的数组后，

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

public void push(T item) {

    if(N == a.length)

        resize(2 * a.length)

    a[N++] = item;

}

public T pop() {

    T item = a[--N];

    a[N] = null;  

    if(N > 0 && N == a.length / 4) //如果堆栈只满1/4，减为1/2，还能有1/2的空余；

        resize(a.length / 2);

    return item;
}

pop()方法中要避免内存泄漏：

对象游离： Stack的pop方法写的不好，就有可能导致内存泄漏；

用数组实现堆栈，pop之后，当前对象在堆栈范围内已经无用了，如果客户代码那也用完了这个对象，其该被回收，但是，因为Stack内部的数组还有对这个对象的引用，导致无法被GC，除非再次push，该数组位的引用值被重新指向另一个对象，原来那个对象就被GC了；

如果用API中的List实现堆栈，因为List本身的remove方法已经采取了避免对象游离的措施，所以就没这个问题；

用数组存储和用链表存储：

堆栈本身并不用于遍历，所以操作（push和pop）的用时都跟集合大小无关，不管是用数组还是用链表实现；

用数组存储的明显缺点就在于，push，pop会不定期地引起数组的调整，调整数组的耗时和栈大小成正比，克服这个缺陷就是用链表代替之：

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

private Node first = null; //栈顶节点

private Class Node { //描述栈帧的节点内部类定义

    T item;

    Node next;

}

public void push(T item) {

    Node oldFirst = first;

    first = new Node();

    first.item = item;

    first.next = oldFirst;

    N++;

}

public T pop() {

    T item = first.item;

    first = first.next();

    N--;

    return item;
}

不用担心对象游离的问题，first = first.next之后，由于堆栈里并没有数组结构，出栈的对象在栈内不会再被引用，没用就回收掉了；

堆栈也是集合，也要实现迭代器：

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

Stack<T> implements Iterable<T>

public Iterator<T> iterator() {

    return new Iterator<T> {

        private int i = N;

        public boolean hasNext() {

            return i > 0;

        }

        public T next() {

            return a[--i];

        }

        ...

    }

链表实现的迭代：

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

Stack<T> implements Iterable<T>

public Iterator<T> iterator() {

    return new Iterator<T> {

        private Node current = first;

        public boolean hasNext() {

            return current != null;

        }

        public T next() {

             T item = current.item;

            current = current.next;

            return item;

        }

        ...

    }

链表实现的队列就是一种堆栈，仍然从first出队，但是从last入队：

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

public boolean isEmpty() {

    return first === null;

}

public void enqueue(T item) {

    Node oldLast = last;

    last = new Node();

    last.item = item;

    last.next = null;

    if(isEmpty())

        first = last;

    else

        oldLast.next = last;

    N++;

}

public Item dequeue() {

    T item = first.item;

    first = first.next;

    if(isEmpty())

        last = null;

    N--;

    return item;
}

到底用数组还是链表：

堆栈是LIFO，数组实现的话，总是在数组的末尾进行赋值和置null，这个可以接受；但数组的调整大小问题导致数组实现又不是特别能接受，而链表就完全不存在这个问题；

队列是FIFO，数组实现的话，假如入队末尾，那么出队必然在开头，删除开头元素要引起数组整体挪动；或者反过来，入队在开头，则出队在末尾，入队得在开头添加元素，引起数组整体挪动；所以说，队列一点都不适合用数组实现。

常数、对数、线性、线性对数、平方、立方、指数；

一般来说，平方、立方、指数级别的算法对于大规模的问题是不可用的；

logN的底数对算法分析来说相当于一个常数，所以可以忽略底数到底是几；

2-sum问题的平方级算法：

1
2
3
4
5
6
7

for(int i =0; i < N; i++) 

    for(int j = i + 1; j < N; j++) 

        if(a[i] + a[j] == 0)

            count++;

这个复杂度是(N-1) + (N-2) + … + (N-N) = N的平方 + N的平方/2 =-= N的平方；

改进的算法：

1
2
3
4
5
6
7

sort(a);

for(int i = 0; i < N; i++) 

    if(BinarySearch(-a[i], a) > i)

        count++;

这个算法的思路，单循环数组a，对于每一个a[i]：

1， 如果二分查找找不到-a[i]，计数器不增加；

2， 如果二分查找到的-a[i]是a[j]，如果j > i，计数器增加，反之如果j < i，因为a是排序了的，说明这次查找之前已经用a[j]找到过a[i]了，重复了，计算器不增加；

对于N次单循环，每次都二分查找了，二分查找的复杂度是对数级，所以这个算法的总复杂度是线性对数级；

相应的，原来为N的立方的3-sum问题可被优化为N的平方对数级的；

优先队列的二叉堆实现

【优先队列】

堆栈：删除最新元素；

队列：删除最旧元素；

优先队列：删除最大元素和插入元素；

优先队列实现的两个方式：

1， 惰性的，使用无序数据结构，插入元素不做任何操作，删除最大元素时再查找最大元素；

2， 主动的，使用有序数据结构，插入元素时就排到合适的位置，删除最大元素时直接删第一个；

优先队列的初级实现：

                        插入元素                        删除最大元素

有序数组 N 1

无序数组 1 N

栈和队列的操作的复杂度都是个常数；

优先队列用数组初级实现的话，操作的复杂度都是线性的；

我们试图探寻更好性能的优先队列实现；

【二叉堆】

用数组表示完全二叉树：

将二叉树的节点按照层级顺序放入数组中，根节点在位置1，它的子节点在位置2和3，而子节点的子节点则分别在4、5、6、7；

不使用数组的第一个位置；

对于一个节点，它在数组中的是索引是k，那么它的父节点的索引是：下取整(k/2)

子节点的索引分别是2k和2k+1；

堆有序：

当一棵二叉树的每个节点都大于等于它的两个子节点时；

在堆有序的二叉树中，从任意节点向上，都能得到一列非递减的元素；从任意节点向下，都能得到一列非递增的元素；

堆有序化-上浮：

如果堆的有序状态因为某个节点变得比它的父节点更大而打破，就需要交换它和它的父节点；

交换后，这个节点仍然可能比现在的父节点大，所以需要继续往上交换；

1
2
3
4
5
6
7
8

void swim(int k) {

    while(k > 1 && pq[k/2] < pq[k]) {

        swap(pq, k/2, k);

        k = k / 2;
}

同理，下沉：

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

void sink(int k) {

    while(2 * k <= N) {
        int j = 2 * k;

        if(j < N && pq[j] < pq[j+1]) //选取两个子节点中较大的一个往上交换

                j++;

        if(pq[k] >= pq[j])   //结束下沉，已经比字节点大了

                break;

        swap(pq, k, j); //下沉

        k = j;
}

在实现二叉堆的数组中，插入一个数据到末尾是上浮；删除第一个数据，这个数据就是最大元素，然后把数组最末尾的元素放到顶端，让其下沉；

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

public class MaxPQ<Key extends Comparable<Key>> {

    private Key[] pq;

    private int N = 0;

    public MaxPQ(int maxN) {

        pq = (key[]) new Comparable[maxN+1];

    }

    public boolean isEmpty() {

        return N == 0;

    }

    public int size() {

        return N;

    }

    public void insert(Key v) {

        pq[++N] = v;

        swim(N);

    }

    public Key delMax() {

        Key max = pq[1];

        swap(1, N--);

        pq[N+1] = null;

        sink(1);

        return max;

    }
}

由于插入和删除都最多是一次根节点到叶节点的堆秩序恢复，跟节点到叶节点的最长路径是lgN；所以二叉堆实现的优先队列的插入和删除的复杂度都是lgN（比较次数：lgN+1, 2lgN）；

如何检测一个链表中是不是有循环结点？

两个指针，分别表示乌龟和兔子，乌龟每次往下走1步，兔子每次走两步，如果兔子走到了Next为Null的节点，说明没有循环，否则他们一定相遇，表示有循环。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/mosthink/p/5288682.html