算法_摘要

发表于 | 分类于 ， | 阅读次数: ℃
字数统计: 2.5k | 阅读时长 ≈ 15
纯粹想到什么写什么，做个知识的总结

算法_摘要

1. 基础

  • java 允许整型溢出并返回错误值，所以要小心。
  • Math.abs(-2147483648) = -2147483648.

  • a/b的商向0取整了;(a/b)*b+a%b=a; -14/3=14/-3=-4 ； -14%3=-2 ； 14%-3=2

  • 每个类都是Java的Object类子类，意味着每个类都含有getClass(),toString(),equals(),hashCode()等方法的实现。

  • 默认toString()一般只会返回一个对象内存地址。

  • 当一个int值需要和一个String值连接时，类型会被转换为Integer并触发toString()方法。

  • public boolean equals(Object x){

    　　//三个通用对比

    　　if (this == x) return true;

    　　if (x == null) return false;

    　　if (this.getClass() != x.getClass()) return false;

    　　if …具体内容比较。

    }

  • 一个引用类型的实例变量含有修饰符final，该实例变量的值（某个对象的引用）就永远无法改变——它将永远指向同一个对象，但对象的值本身仍然是可变的。

  • 原始数据类型更接近计算机硬件所支持的数据类型，因此使用原始数据类型比使用引用类型运行更快。

  • 创建一个含有N个对象的数组，需要使用N+1次new关键字。

  • Iterable 和 Iterator。一个类实现 Iterable接口，表明该类是可迭代的，需要在类中实现一个返回实现Iterator接口的类的方法，该类需要实现hasnext()、next()和remove()方法。

    Iterator将访问逻辑从不同的集合类中抽象出来，避免暴露集合的内部结构，还能起到解耦的作用。

    之所以要实现Iterable和Iterator两个接口是因为，可能有多个地方同时遍历数据，如果只有实现Iterator接口，没法维护每个遍历的指针，所以需要实现一个内部类为每个遍历提供一个单独的对象。

    如果在使用迭代器时，改变了数据容量，则迭代器需要抛出异常。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public interface Iterable<T> {
        Iterator<T> iterator();
    }
    public interface Iterator { 
        boolean hasNext(); 
        Object next(); 
        void remove(); 
    } 
    // 示例
    public class ArrayTest implements Iterable<Integer>{
        private int[] a = new int[10];
        private int N=0;
        public Iterator<Integer> iterator(){
            return new ArrayIterator();
        }
        private class ArrayIterator implements Iterator<Integer>{
            private int i=N;
            public boolean hasnext(){return i>0;}
            public Integer next(){return a[--i];}
            public void remove(){}
        } 
    }

  • 内存：

    • 一个对象本身一般需要16字节的开销，比如一个Integer使用24字节（16个对象开销，4个用于保存int值，4个填充字节）。
    • 一般内存使用会填充为8字节的倍数（因为64位计算机）。
    • 由于链表每个结点都是一个node对象需要额外的空间，而数组一般只需要24字节的头信息+保存值内存即可，所以数组的内存开销远远小于链表。（比如同Integer，链表约为32+64N，数组约为24+24N）
    • 字符串，String,StringBuilder,StringBuffer见单章。

2. 排序

见单章。

3. 查找

  • 顺序查找

  • 有序二分查找

  • 二叉查找树（BST），每个结点都大于左子树所有结点，小于右子树所有结点。

    • 平均比较次数约1.39lgN。
    • 插入一定在叶结点。
    • 删除，从右子树选一个最小的值代替。
    • 容易造成树不平衡，查找时间不稳定。

  • 平衡二叉树（AVL），每棵子树中的左子树和右子树的深度差不能超过 1。

    • 平均比较次数为lgN。

    • 平衡因子：每个结点都有其各自的平衡因子，表示的就是其左子树深度同右子树深度的差。只可能是：0、1 和 -1。

    • 4种调整情况。

  • 红黑树，从任何一个结点开始，一直到其子孙的叶子结点的长度称为路径，任意结点的内部路径之间长度不超过两倍。

    • 平均查找时间lgN。
    • 同平衡二叉树相比较，红黑树没有像平衡二叉树对平衡性要求的那么苛刻，虽然两者的时间复杂度相同，但是红黑树在实际测算中的速度要更胜一筹！

  • B-树，每个结点可以拥有多个子树。

    • 具有分支多层数少的特点，使得它更多的是应用在数据库系统中。

  • B+树，与B-树类似，但叶子结点中包含了全部关键字的信息且叶子结点本身依关键字的大小自小而大顺序链接。

    • 有两种查找方式：1.叶子节点循序查找。2.从根节点一层层多分查找。

    • 更多的是用于文件索引系统。

  • hash表，见单章。

4. 图

  • 图的表示方法：邻接矩阵、边的数组、邻接表数组。

无权图：

  • 无向无权图：
    • 可达性，是否成环（深度优先DFS）
    • 最短路径，节点之间的间隔（广度优先BFS）
  • 有向无权图：
    • 可达性，Java对象的垃圾回收判断，（深度优先DFS）
    • 最短路径（广度优先BFS）
    • 强连通图，即结点之间都互通，（Kosaraju：1.计算反向图$G^R$的逆后序排列。2.根据排列顺序进行深度优先遍历。3.能够遍历到的点即互相连通）。
  • 有向无权无环图：
    • 优先级限制下的调度问题。（拓扑排序、逆后序，将后序遍历倒着输出，能够保证先输出的优先级一定不小于后输出的。）
    • 拓扑排序：给定一幅有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素（或者无法做到、存在环）。使用深度优先实现时，第一遍判断是否存在环，第二遍生成逆后序排列。

有权图：

  • 无向加权图：
    • 最小生成树，连通所有点的权重和最小的无环树，可以减少网络成本。基于切分定理。
    • 切分定理：在一幅加权图中，给定任意切分，它的横截面中的权重最小者必然属于图的最小生成树。
    • Prim，逐步扩张，每次扩张值最小的相邻边。
      “延时实现：”维护一个相邻边的小顶堆，每次扩张更新一次。空间与E（边数）成正比，时间与ElogE成正比（最坏情况）。
      “即时实现：”维护一张非树节点到树权重的最小值表，每次扩张更新一次。空间与V（顶点）成正比，时间与ElogV成正比（最坏情况）。
    • Kruskal，每次取最小值边加入，且保证不会成环，该方法将起始状态视为V棵树，然后根据切分定理不断进行树的合并。需要对所有的边进行排序，没有Prim快。空间与E（边数）成正比，时间与ElogE（排序时间）成正比。
  • 有向加权图：
    • 最短路径-权重非负。Dijkstra，形成最短路径树，每次将距离起点最近的点加入树，并将该点“松弛”，即更新与该点相连点的与起点最小距离。
    • 最短路径-无环。直接按照拓扑顺序遍历点并放松。
    • 最长路径。优先级下并行调度问题，处理器无限，最短处理时间及求最长路径。将权重取反求最短。
  • 普通加权有向有环有负图：
    • 最短路径。Bellman-Ford，前提：无负权重环，以任意顺序放松图的所有边并重复V轮。

5. 字符串

排序：

  • 低位优先（LSD）。就是基数排序，适用于长度相同的字符串排序。
  • 高位优先（MSD）。就是桶排序。由于每次都要分成n（字符总类数）个桶，导致存在一些缺陷。1.对于小型子桶也需要分成n个桶很浪费。2.对于相同前缀的字符串，进行不必要的分桶。总的来说就是因为往往桶的个数太多造成大量空间的浪费。一般采用策略“对前d个字符均相同的字符串执行插入排序”来提高效率。
  • 三向快速排序。桶排序和快排的结合，每次只分小于、等于、大于三个桶（等于的桶进行下一个字符的判断，另两个桶继续三向分割），大大降低的空间的使用，高位优先存在的问题统统解决。

查找：

  • 构建单词查找树，同一父节点的结点用一个1*n的数组表示，同样很耗空间。
  • 三向单词查找树，同样的分为大等小3类，结构有点像B-树。

子字符串查找：

  • 暴力
  • KMP，为匹配字符串建一个回退数组，每次回退到指定位置。详见单章。
  • Rabin-karp指纹查找，通过计算Hash值判断是否相同。
-------------本文结束感谢您的阅读-------------