java学习重点 笔试面试考点 之 数据结构与算法

java学习重点之数据结构与算法，从丘奇-图灵论到图灵机与算法本质，从数据底层实现到复杂数据结构，内容全面，重点突出，同一概念的称呼不同称呼和命名都经过统一整理；贴出来的算法实现都使用JAVA语言，且经过测试和优化，并补充了递归或迭代这两种实现方式。

数据结构与算法

• 丘奇-图灵论/Church-Turing Thesis
  • 图灵提出图灵机前思考的三个问题：1.世界上是否所有的数学问题都有明确的答案？2.如果有明确的答案，是否可以通过有限步骤的计算得到答案？3.对于那些有可能在有限步骤计算出来的学习问题，是否有一种假想的机械，让它不断运行，最后机器停下来的时候，那个数学答案就计算出来了？ 一切合理的计算模型都等同于图灵机。 凡是能用算法方法解决的问题也一定能用图灵机解决；凡是图灵机解决不了的问题任何算法也解决不了。 如果一种语言能被某一图灵机判定，则称该语言是图灵可判定的，也称递归语言。
  • 计算过程
    • 递归
      • 如果一个对象部分地由自己组成，或者是按它自已定义的，则称为是递归的。
    • λ演算
      • λ 演算可以被称为最小的通用程序设计语言，可以用来清晰地定义什么是一个可计算函数。
    • 图灵机
      • 图灵机是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
  • 所有递归都可转迭代
• 编程=数据结构+算法
• 数据（对象）的逻辑结构
  • 线性结构
    • 一对一
  • 树形结构
    • 一对多
  • 图形结构
    • 多对多
  • 集合
    • 同属一个集合
• 计算机存储
  • 底层存储结构
    • 数组
      • 连续
    • 链表
      • 分散
  • 存储方法
    • 顺序存储
      • 物理位置连续
    • 链接存储
      • 指针
    • 索引存储
      • 索引表
    • 散列/哈希存储
      • 根据关键字计算存储地址
• 数据结构
  • 线性结构
    • 数组
      • 一维数组
      • 二维数组
        • 稀疏数组
          • 列数=3：行号+列号+值
          • 行数=有效值个数
          • 第一行保存数组大小
      • 三维数组
        • 魔方游戏
      • 多维数组
        • 游戏归类数据：装备、技能、状态
    • 链表
      • 单链表
        • 带头节点
          • 头节点
            • 不存放具体数据单链表的头，指向第一个数据
          • 增删改查
        • 不带头节点
          • 递归反转
        • 面试题
          • 求单链表有效节点个数
          • 查找链表倒数第k个节点
          • 单链表的反转
            • 直接反转
            • 新建单链表反转
          • 从尾到头打印单链表
            • 反向遍历
            • Stack栈
              • 递归实现
      • 双向链表
        • 双向查找
        • 自我删除
      • 单向环形链表
        • 约瑟夫环
          • 构建
            • 1.创建第一个节点，头指针指向该节点，next指向自己，形成环形。2.每创建一个新节点，将新节点加入已有环形链表
          • 遍历
            • 1.创建辅助节点等于第一个节点。2.while循环遍历，辅助节点指向第一个节点后结束
          • 出圈
            • 用户输入：n：总人数，k：第几个人开始报数，m：数几下 1.创建辅助节点f和h，f=第一个节点，h=最后一个节点，报数前将f和h移动k-1次。2.报数时，f和h同时移动m-1次3.将f指向出圈的人：f=f.next; h.next=f;
        • 求链表中是否有环
          • 快慢指针
            • 运用快慢指针，快指针速度为慢指针的二倍，如果有环，快指针一定会追上慢指针。 /** * Definition for singly-linked list. * class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public boolean hasCycle(ListNode head) {        ListNode slow = head;        ListNode fast = slow;                if(head ==null || head.next ==null ||head.next.next ==null)            return false;                while(fast != null && fast.next !=null)        {            fast = fast.next.next;            slow = slow.next;                        if(fast == slow )                return true;        }             return false;    }}
    • 线性表
      • 同一类型的数据元素组成的有序序列的线性结构。
    • 受限线性表
      • 队列
        • 先进先出的有序列表
          • 排队叫号系统
        • 数组实现队列
          • 最大容量
          • 队列头
            • 指向队列头的前一个位置
          • 队列尾
            • 指向队列尾的数据(即就是队列最后一个数据)
        • 数组实现环形队列
          • size:最大容量+1
            • 需要空出一个空间
          • f:队列头
            • 指向队列的第一个元素，初始值为0
          • r:队列尾
            • 指向队列的最后一个元素的后一个位置，要空出一个空间，初始值为0
          • 有效数据个数:(size+r-f)%size
        • 链表实现队列
          • 单链表实现
            • 头结点
            • 尾结点
            • 队列长
      • 栈
        • 先进后出的有序列表
          • 增删只操作栈顶
        • 应用
          • 子程序调用
          • 递归调用
          • 表达式转换
            • 中缀转后缀表达式
              • 1.初始化两个栈：运算符栈s1和储存中间结果的栈s2；2.从左至右扫描中缀表达式；3.遇到操作数时，将其压s2；4.遇到运算符时，比较其与s1栈顶运算符的优先级：(1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；(2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较； 5.遇到括号时：(1) 如果是左括号“(”，则直接压入s1(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃6.重复步骤2至5，直到表达式的最右边7.将s1中剩余的运算符依次弹出并压入s28.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
              • 实例
                • 扫描到的元素s2(栈底->栈顶)s1 (栈底->栈顶)说明11空数字，直接入栈+1+s1为空，运算符直接入栈(1+ (左括号，直接入栈(1+ ( (同上21 2+ ( (数字+1 2+ ( ( +s1栈顶为左括号，运算符直接入栈31 2 3+ ( ( +数字)1 2 3 ++ (右括号，弹出运算符直至遇到左括号×1 2 3 ++ ( ×s1栈顶为左括号，运算符直接入栈41 2 3 + 4+ ( ×数字)1 2 3 + 4 ×+右括号，弹出运算符直至遇到左括号-1 2 3 + 4 × +--与+优先级相同，因此弹出+，再压入-51 2 3 + 4 × + 5-数字到达最右端1 2 3 + 4 × + 5 -空s1中剩余的运算符
          • 二叉树遍历
          • 图的深度优先搜索
        • 数组实现栈
          • 1.定义top为栈顶，初始化为-1。2.入栈：top++;stack[top]=val;2.出栈：int val=stack[top];top--;return val;
        • 表达式
          • 前缀/波兰表达式
            • 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。 例如: (1+2)×3-4 对应的前缀表达式就是 - × + 1 2 3 4, 对前缀表达式求值步骤如下: 1.从右至左扫描，将4、3、2、1压入堆栈2.遇到+运算符，因此弹出1和2（1为栈顶元素，2为次顶元素），计算出1+2的值，得3，再将3入栈3.接下来是×运算符，因此弹出3和3，计算出3×3=9，将9入栈4.最后是-运算符，计算出9-4的值，即5，由此得出最终结果
          • 中缀表达式
            • 常见的运算表达式(1+2)×3-4
          • 后缀/逆波兰表达式
            • 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果 例如: (2+3)×4-5 对应的后缀表达式就是 2 3 + 4 × 5 -, 后缀表达式求值步骤如下: 1.从左至右扫描，将2和3压入堆栈；2.遇到+运算符，因此弹出2和3，计算出2+3的值，得5，再将5入栈；3.将4入栈；4.接下来是×运算符，因此弹出4和5，计算出4×5=20，将20入栈；5.将5入栈；6.最后是-运算符，计算出20-5的值，即15，由此得出最终结果
            • 逆波兰计算器
  • 非线性结构
    • 广义表
      • 广义表是线性表的推广，也是由n个元素组成的有序序列。广义表中存储的元素可以是单元素或另一个广义表，线性表中的元素都是存储单元素。由于广义表中的元素本身又可以具有结构，它是一种带有层次的非线性结构，因此难以用顺序存储结构表示，通常采用链式存储结构。
    • 树
      • 术语
        • 结点node
          • 数据元素及其分支
          • 根节点/树根
          • 分支结点
            • 度不为0的结点
          • 叶子结点
            • 度为0的结点
        • 树/全树
          • 以根结点为根的树。
          • 子树
            • 以其他结点作为根的树
        • 度
          • 结点的度
            • 节点分支个数
          • 树的度
            • 树中所有节点的度的最大值
        • 层次/深度
          • 自顶向下
          • 结点的层次/深度
            • 从结点到根结点的路径中边的条数（若假设根节点层次为1，则层次=条数+1）
          • 树的层次/深度
            • 树中所有结点中的最大深度
        • 高度
          • 自下向顶
          • 节点的高度
            • 从一个结点出发，一直到它的叶子结点的最大路径中的边的条数。
          • 树的高度
            • 根结点的高度
        • 森林
          • 彼此不相交的树的集合
      • 定义
        • 基本定义
          • 树（tree）是包含n（n>=0）个结点的有穷集。1.每个元素称为结点（node）。2.有一个特定的结点被称为根结点或树根（root）。3.除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
        • 递归定义
          • 1.单个结点是一棵树，树根就是该结点本身。2.设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称n1,n2,..,nk为结点n的子树。
        • 族谱定义
          • 树最初来源族谱，所以也可以这么定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。若一个结点有子树，那么该结点称为子树根的“双亲”，子树的根称为该结点的“孩子”。有相同双亲的结点互为“兄弟”。双亲在同一层的结点互为“堂兄弟”。一个结点的所有子树上的任何结点都是该结点的后裔或子孙。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
      • 无序树/自由树
        • 树中任意节点的子节点之间没有顺序关系
      • 有序树
        • 树中任意节点的子节点之间有顺序关系
        • 二叉树
          • 树的任意节点至多包含两棵子树
          • 满二叉树
            • 叶子节点都在同一层并且除叶子节点外的所有节点都有两个子节点
            • 国外版定义
              • A binary tree in which each node has exactly zero or two children.
          • 完全二叉树
            • 对于一颗二叉树，假设其深度为d（d>1）。除第d层外的所有节点构成满二叉树，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树
            • 国外版定义
              • A binary tree in which every level (depth), except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.
            • 堆
              • 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树。
              • 最大堆/大根堆/大顶堆
                • 根节点最大
              • 最小堆/小根堆/小顶堆
                • 根节点最小
              • 堆排序
                •  import java.util.Arrays;/** *  * @author Administrator * */public class HeapSort {    public static void main(String []args){        int []arr = {7,6,7,11,5,12,3,0,1};        System.out.println("排序前："+Arrays.toString(arr));        sort(arr);        System.out.println("排序前："+Arrays.toString(arr));    }     public static void sort(int []arr){        //1.构建大顶堆        for(int i=arr.length/2-1;i>=0;i--){            //从第一个非叶子结点从下至上，从右至左调整结构            adjustHeap(arr,i,arr.length);        }        //2.调整堆结构+交换堆顶元素与末尾元素        for(int j=arr.length-1;j>0;j--){            swap(arr,0,j);//将堆顶元素与末尾元素进行交换            adjustHeap(arr,0,j);//重新对堆进行调整        }     }     /**     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）     * @param arr     * @param i     * @param length     */    public static void adjustHeap(int []arr,int i,int length){        int temp = arr[i];//先取出当前元素i        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点                k++;            }            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）                arr[i] = arr[k];                i = k;            }else{                break;            }        }        arr[i] = temp;//将temp值放到最终的位置    }     /**     * 交换元素     * @param arr     * @param a     * @param b     */    public static void swap(int []arr,int a ,int b){        int temp=arr[a];        arr[a] = arr[b];        arr[b] = temp;    }}
          • 二叉查找树/二叉排序树/二叉搜索树/BST树
            • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 任意节点的左、右子树也分别为二叉查找树； 没有键值相等的节点；
            • 平衡树/平衡二叉树/AVL树
              • 每个节点的左子树和右子树的高度最多差1的二叉查找树，并且左右两个子树都是一棵平衡二叉树
              • R树
                • 1.除根结点之外，所有非根结点包含有m至M个记录索引（条目）。根结点的记录个数可以少于m。通常，m=M/2。2.对于所有叶子中存储的记录（条目），I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意：此处所说的“矩形”是可以扩展到高维空间的）。3.对于所有非叶子结点上的记录（条目），i是最小的可以在空间上完全覆盖这些条目所代表的点的矩形（同性质2）。
            • 红黑树
              • 每个节点或者是黑色，或者是红色。根节点是黑色。每个叶子节点（NIL）是黑色。如果一个节点是红色的，则它的子节点必须是黑色的。从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
            • 伸展树/分裂树
              • 伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。伸展树保证从空树开始任意连续M次对树的操作最多花费O(M*logN)时间。
          • 赫夫曼树/哈夫曼树/最优二叉树
            • 带权路径最短的二叉树
            • 赫夫曼编码
              • //哈夫曼树类public class HaffmanTree {    //最大权值    static final int MAXVALUE=1000;    int nodeNum ; //叶子结点个数        public HaffmanTree(int n)    {       this.nodeNum = n;    }        //构造哈夫曼树算法    public void haffman(int[] weight,HaffNode[] nodes)//权值数组，所有节点数组    {        int n = this.nodeNum;        //m1,m2,表示最小的两个权值，x1,x2,表示最小两个权值对应的编号,m1表示最小，m2表示次小        int m1,m2,x1,x2;                 //初始化所有的结点，对应有n个叶子结点的哈夫曼树，有2n-1个结点。        for(int i=0;i < 2*n-1;i++)        {            HaffNode temp = new HaffNode();            //初始化n个叶子结点，就是输入的节点。0、1、2、3是叶子节点也是输入的节点            if(i < n)            {               temp.weight = weight[i];                }            else            {               temp.weight = 0;                }            temp.parent = 0;            temp.flag = 0;            temp.leftChild = -1;            temp.rightChild = -1;            nodes[i] = temp;        }                for(int i=0;i<n-1;i++){//初始化n-1个非叶子结点，n-1表示要循环n-1次求的n-1个数。           m1 = m2 = MAXVALUE;           x1 = x2 =0;           for(int j=0;j< n+i;j++)//求得这n-1个数时，每次都是从0到n+i-1,并且flag=0的，flag=1表示已经加入到二叉树。           {   //以下2步是找出权值最小的2个               if(nodes[j].weight<m1 && nodes[j].flag==0)//if成立了else、else if就不进去了。               {                //m1,x1初始值为第一个元素，后面如果比m1要小，则m1指向更小的，原来m1指向的现在由m2指向，                //如果后面比m1大比m2小，则m2指向这个比m1大比m2小的，                //也就是说m1指向最小的，m2指向第2小的。                  m2 = m1;                  x2 = x1;                  m1 = nodes[j].weight;                  x1 = j;               }               else if(nodes[j].weight<m2 && nodes[j].flag ==0)               {                  m2 = nodes[j].weight;                  x2 = j;               }           }           //将权值最小的2个组合成一个2插树           nodes[x1].parent = n+i;           nodes[x2].parent = n+i;           nodes[x1].flag = 1;           nodes[x2].flag = 1;           nodes[n+i].weight = nodes[x1].weight + nodes[x2].weight;           nodes[n+i].leftChild = x1;           nodes[n+i].rightChild = x2;        }        /*        初始化数组之后：[1,3,5,7,4,9,16]        编码：100、101、11、0        */    }        //哈弗曼编码算法    public void haffmanCode(HaffNode[] nodes,Code[] haffCode)    {        int n = this.nodeNum;        Code code = new Code(n);//4        int child,parent;                for(int i=0;i<n; i++)//给前面n个输入的节点进行编码        {           code.start = n-1;//3           code.weight = nodes[i].weight;//1           child = i;//0           parent = nodes[child].parent;           //从叶子节点向上走来生成编码，画图即可。           while(parent!=0)           {              if(nodes[parent].leftChild == child)              {                  code.bit[code.start] = 0;              }              else              {                  code.bit[code.start] = 1;              }                            code.start--;               child = parent;              parent = nodes[child].parent;           }                      Code temp = new Code(n);           for(int j=code.start+1;j < n;j++)           {               temp.bit[j] = code.bit[j];           }           temp.weight = code.weight;           temp.start = code.start;           haffCode[i] = temp;        }    }} //哈夫曼树的结点类public class HaffNode {       int weight; //权值    int parent ;//他的双亲    int flag ;//标志，是否为叶子节点    int leftChild; //他的左孩子    int rightChild;//他的右孩子        HaffNode()    {            }    } //哈夫曼编码类public class Code {     int[] bit;  //编码的数组    int start;  //编码的开始下标    int weight; //权值    Code(int n){        bit = new int[n];        start = n-1;    }} public class Test {     public static void main(String[] args) {                int n = 4;        int[] weight = {1,3,5,7};        HaffmanTree haffTree = new HaffmanTree(n);        HaffNode[] nodes = new HaffNode[2*n-1];        Code[] codes = new Code[n];         //构造哈夫曼树        haffTree.haffman(weight, nodes);        //生成哈夫曼编码        haffTree.haffmanCode(nodes, codes);                //打印哈夫曼编码        for(int i=0;i<n;i++)        {            System.out.print("Weight="+codes[i].weight+" Code=");            for(int j=codes[i].start+1;j<n;j++)            {               System.out.print(codes[i].bit[j]);                }            System.out.println();        }    } }
              • 实现数据的压缩和解压
                • package tree.huffmanTree.huffmanCode; import java.io.*;import java.util.*; public class HuffmenCodeTest {    public static void main(String[] args) {        String msg = "can you can a can as a can canner can a can.";        byte[] bytes = msg.getBytes();        System.out.println(Arrays.toString(bytes));        System.out.println("压缩前的数据长度：" + bytes.length);        //使用赫夫曼编码压缩        byte[] tar = huffmenZip(bytes);        System.out.println("压缩后的数据长度：" + tar.length);        //使用赫夫曼编码表解压        byte[] sourceByte = decodeByHuffmen(tar, mapCode);        System.out.println(new String(sourceByte));         String src = "D:\\javaproject\\DataStructure\\src\\tree\\huffmanTree\\huffmanCode\\white.png";        String dst = "D:\\javaproject\\DataStructure\\src\\tree\\huffmanTree\\huffmanCode\\tar.zip"; //        try {//            zipFile(src, dst);//        } catch (IOException e) {//            e.printStackTrace();//        }         try {            decodeZip(dst, src);        } catch (IOException e) {            e.printStackTrace();        } catch (ClassNotFoundException e) {            e.printStackTrace();        }    }     /**     * 使用哈夫曼编码进行文件压缩     *     * @param src 原文件地址     * @param dst 压缩后的文件地址     * @throws IOException     */    public static void zipFile(String src, String dst) throws IOException {        InputStream in = new FileInputStream(src);        byte[] srcBytes = new byte[in.available()];        in.read(srcBytes);        in.close();        System.out.println("文件压缩前的大小：" + srcBytes.length);        //使用哈夫曼压缩        byte[] tarBytes = huffmenZip(srcBytes);        System.out.println("文件压缩后的大小：" + tarBytes.length);         //输出文件不仅包含压缩后的字节数据，还包含产生的哈夫曼编码，故使用包装类ObjectOutputStream        OutputStream out = new FileOutputStream(dst);        ObjectOutputStream oos = new ObjectOutputStream(out);        oos.writeObject(tarBytes);        oos.writeObject(mapCode);        oos.close();        out.close();    }     /**     * 解压文件     *     * @param zipPath     * @param newPath     */    public static void decodeZip(String zipPath, String newPath) throws IOException, ClassNotFoundException {        InputStream in = new FileInputStream(zipPath);        ObjectInputStream ois = new ObjectInputStream(in);        //读取byte数组        byte[] filedatas = (byte[]) ois.readObject();        System.out.println(Arrays.toString(filedatas));        //读取哈夫曼编码表        Map<Byte, String> mapCode = (Map<Byte, String>) ois.readObject();        //解码        byte[] source = decodeByHuffmen(filedatas, mapCode);        //byte[]输出到文件        OutputStream out = new FileOutputStream(newPath);        out.write(source);        out.close();    }     /**     * 使用赫夫曼编码解压     *     * @param tar         目标数据     * @param huffmenCode 赫夫曼编码表     * @return     */    private static byte[] decodeByHuffmen(byte[] tar, Map<Byte, String> huffmenCode) {        StringBuffer sb = new StringBuffer();        //将byte[]转为二进制字符串        for (int i = 0; i < tar.length; i++) {            if (i == tar.length - 1) {                sb.append(Integer.toBinaryString(tar[i]));            } else {                sb.append(byteToString(tar[i]));            }        }        System.out.println(sb.toString());        //将哈夫曼编码表里面的键值对互换，方便下一步查询        Map<String, Byte> temp = new HashMap<>();        for (Map.Entry<Byte, String> entry : huffmenCode.entrySet()) {            temp.put(entry.getValue(), entry.getKey());        }        System.out.println("哈夫曼编码表键值对互换:" + temp);        //根据哈夫曼编码表将二进制字符串转换成原数据        List<Byte> source = getSource(sb.toString(), temp);//        System.out.println(source);        //把集合转变成数组        byte[] byteSource = new byte[source.size()];        for (int i = 0; i < byteSource.length; i++) {            byteSource[i] = source.get(i);        }        return byteSource;    }     private static List<Byte> getSource(String codeStr, Map<String, Byte> byteMap) {        List<Byte> tempList = new ArrayList<>();        getSingleItem(tempList, codeStr, byteMap);        return tempList;    }     private static void getSingleItem(List<Byte> tempList, String codeStr, Map<String, Byte> byteMap) {        for (int i = 0; i <= codeStr.length(); i++) {            if (byteMap.keySet().contains(codeStr.substring(0, i))) {                tempList.add(byteMap.get(codeStr.substring(0, i)));                getSingleItem(tempList, codeStr.substring(i), byteMap);                break;            }        }    }      private static String byteToString(byte b) {        //将8位扩大到32位，便于 或 运算，提取原来数值中的8位        int temp = b;        temp |= 256;        String str = Integer.toBinaryString(temp);        return str.substring(str.length() - 8);    }     private static byte[] huffmenZip(byte[] bytes) {        //先将每个byte元素以及出现的次数包装成HuffmanNode节点，输出节点列表        List<HuffmenNode> nodeList = getNodeList(bytes);//        System.out.println(nodeList);        //按出现次数的大小排序(从大到小)        Collections.sort(nodeList);//        System.out.println(nodeList);        //创建哈夫曼树        HuffmenNode rootNode = createHuffmenTree(nodeList);//        System.out.println(rootNode);        //创建哈夫曼编码表        Map<Byte, String> byteStringMap = createHuffmenCode(rootNode);//        System.out.println(byteStringMap);        //按照哈夫曼编码表对原bytes进行编码        byte[] targetBytes = encodeByHuffmenCode(bytes, byteStringMap);        return targetBytes;    }     /**     * 数据压缩     * 根据哈夫曼编码表对原bytes进行编码     *     * @param bytes          原bytes数据     * @param huffmenCodeMap 哈夫曼编码表     * @return     */    private static byte[] encodeByHuffmenCode(byte[] bytes, Map<Byte, String> huffmenCodeMap) {        //将bytes转换成二进制字符串        StringBuffer sb = new StringBuffer();        for (byte b : bytes) {            String str = huffmenCodeMap.get(b);            sb.append(str);        }//        System.out.println(sb.toString());        //将二进制字符串转变为处理后的byte        int len = sb.length();        int newLenght = (len % 8 == 0) ? (len / 8) : (len / 8 + 1);        byte[] targetBytes = new byte[newLenght];        for (int i = 0; i < targetBytes.length; i++) {            if ((i + 1) * 8 > len) {                targetBytes[i] = (byte) Integer.parseInt(sb.substring(i * 8), 2);            } else {                targetBytes[i] = (byte) Integer.parseInt(sb.substring(i * 8, (i + 1) * 8), 2);            }        }        return targetBytes;    }     //临时存储编码表    static Map<Byte, String> mapCode = new HashMap();     private static Map<Byte, String> createHuffmenCode(HuffmenNode rootNode) {        StringBuffer sb = new StringBuffer();        if (rootNode != null) {            getCodes(rootNode.leftNode, "0", sb);            getCodes(rootNode.rightNode, "1", sb);            return mapCode;        }        return null;    }     private static void getCodes(HuffmenNode node, String s, StringBuffer sb) {        StringBuffer tempSb = new StringBuffer(sb);        tempSb.append(s);        if (node.data == null) {            getCodes(node.leftNode, "0", tempSb);            getCodes(node.rightNode, "1", tempSb);        } else {            mapCode.put(node.data, tempSb.toString());        }    }      /**     * 创建哈夫曼树     *     * @param nodeList     */    private static HuffmenNode createHuffmenTree(List<HuffmenNode> nodeList) {        int length = nodeList.size();        while (length > 1) {            HuffmenNode huffmenNode01 = nodeList.get(length - 1);            HuffmenNode huffmenNode02 = nodeList.get(length - 2);            HuffmenNode huffmenNodeNew = new HuffmenNode(null, huffmenNode01.weight + huffmenNode02.weight);            huffmenNodeNew.leftNode = huffmenNode01;            huffmenNodeNew.rightNode = huffmenNode02;            nodeList.remove(huffmenNode01);            nodeList.remove(huffmenNode02);            nodeList.add(huffmenNodeNew);            Collections.sort(nodeList);            length = nodeList.size();        }        return nodeList.get(0);    }     /**     * 将bytes的中的元素以及出现次数包装成HuffmanNode列表     *     * @param bytes     * @return     */    private static List<HuffmenNode> getNodeList(byte[] bytes) {        List<HuffmenNode> nodeList = new ArrayList<>();        Map<Byte, Integer> byteIntegerMap = new HashMap<>();        for (byte b : bytes) {            Integer count = byteIntegerMap.get(b);            if (count == null) {                byteIntegerMap.put(b, 1);            } else {                byteIntegerMap.put(b, count + 1);            }        }        for (Map.Entry<Byte, Integer> item : byteIntegerMap.entrySet()) {            Byte b = item.getKey();            Integer weigth = item.getValue();            HuffmenNode node = new HuffmenNode(b, weigth);            nodeList.add(node);        }        return nodeList;    }  }
          • 线索二叉树
            • 对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
            • 前序线索二叉树
            • 中序线索二叉树
            • 后序线索二叉树
          • 遍历方式
            • public static void main(String[] args) { TreeNode[] node = new TreeNode[10];// 以数组形式生成一棵完全二叉树 for (int i = 0; i < 10; i++) { node[i] = new TreeNode(i); } for (int i = 0; i < 10; i++) { if (i * 2 + 1 < 10) node[i].left = node[i * 2 + 1]; if (i * 2 + 2 < 10) node[i].right = node[i * 2 + 2]; } System.out.println("分层序遍历迭代实现（深度优先）："); levelTraversal(node[0]); System.out.println("\r\n前序遍历递归实现："); preorderTraversalRec(node[0]); System.out.println("\r\n前序遍历迭代实现1："); preorderTraversal(node[0]); System.out.println("\r\n前序遍历迭代实现2："); preorderTraversal2(node[0]); System.out.println("\r\n中序遍历递归实现："); inorderTraversalRec(node[0]); System.out.println("\r\n中前序遍历迭代实现："); inorderTraversal(node[0]); System.out.println("\r\n后序遍历递归实现："); postorderTraversalRec(node[0]); System.out.println("\r\n后前序遍历迭代实现："); postorderTraversal(node[0]); } class TreeNode// 节点结构{ int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; } }
            • 前序遍历
              • 先根节点->遍历左子树->遍历右子树
              • 深度优先遍历
              • 递归实现
                • //前序遍历递归实现： （1）如果二叉树为空，空操作 （2）如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树 public static void preorderTraversalRec(TreeNode root) { if (root == null) { return; } System.out.print(root.val + " "); preorderTraversalRec(root.left); preorderTraversalRec(root.right); }
              • 迭代实现
                • //前序遍历迭代实现1：用一个辅助stack，总是把右孩子放进栈  public static void preorderTraversal(TreeNode root) { if (root == null) { return; } Stack<TreeNode> stack = new Stack<TreeNode>(); // 辅助stack stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); // 出栈栈顶元素 System.out.print(cur.val + " "); // 关键点：要先压入右孩子，再压入左孩子，这样在出栈时会先打印左孩子再打印右孩子 if (cur.right != null) { stack.push(cur.right); } if (cur.left != null) { stack.push(cur.left); } } } //前序遍历迭代实现2：用一个辅助stack，总是把右孩子放进栈  public static void preorderTraversal2(TreeNode root) { if (root == null) { return; } Stack<TreeNode> stack = new Stack<TreeNode>(); // 辅助stack stack.push(root); while (!stack.isEmpty()) { while (root != null) { System.out.print(root.val + " "); stack.push(root); root = root.left; } root = stack.pop(); while (root.right == null) { root = stack.pop(); } root = root.right; } }
            • 中序遍历
              • 遍历左子树->根节点->遍历右子树
              • 递归实现
                • // 中序遍历递归实现 （1）如果二叉树为空，空操作。 （2）如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树 public static void inorderTraversalRec(TreeNode root) { if (root == null) { return; } inorderTraversalRec(root.left); System.out.print(root.val + " "); inorderTraversalRec(root.right); }
              • 迭代实现
                • // 中序遍历迭代实现 ，用栈先把根节点的所有左孩子都添加到栈内然后输出栈顶元素，再处理栈顶元素的右子树     public static void inorderTraversal(TreeNode root){          if(root == null){              return;          }          Stack<TreeNode> stack = new Stack<TreeNode>();          TreeNode cur = root;                     while( true ){              while(cur != null){     // 先添加一个非空节点所有的左孩子到栈                  stack.push(cur);                  cur = cur.left;              }                             if(stack.isEmpty()){                  break;              }                                 // 因为此时已经没有左孩子了，所以输出栈顶元素              cur = stack.pop();              System.out.print(cur.val + " ");            //（每个节点的下一个节点是这个节点的右节点的最左节点，右节点没有左节点就是右节点，没有右节点就是栈中弹出的节点）            cur = cur.right;    // 准备处理右子树          }      }
            • 后序遍历
              • 遍历左子树->遍历右子树->根节点
              • 递归实现
                • //后序遍历递归实现 （1）如果二叉树为空，空操作 （2）如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点 public static void postorderTraversalRec(TreeNode root) { if (root == null) { return; } postorderTraversalRec(root.left); postorderTraversalRec(root.right); System.out.print(root.val + " "); }
              • 迭代实现
                •     //后序遍历迭代实现     public static void postorderTraversal(TreeNode root) {          if (root == null) {              return;          }                     Stack<TreeNode> s = new Stack<TreeNode>();      // 第一个stack用于添加node和它的左右孩子          Stack<TreeNode> output = new Stack<TreeNode>();// 第二个stack用于翻转第一个stack输出        //（从s弹出一个加入output,并把弹出的左右加入s,循环。）        s.push(root);          while( !s.isEmpty() ){      // 确保所有元素都被翻转转移到第二个stack              TreeNode cur = s.pop(); // 把栈顶元素添加到第二个stack              output.push(cur);                                    if(cur.left != null){       // 把栈顶元素的左孩子和右孩子分别添加入第一个stack                  s.push(cur.left);              }              if(cur.right != null){                  s.push(cur.right);              }          }                     while( !output.isEmpty() ){ // 遍历输出第二个stack，即为后序遍历              System.out.print(output.pop().val + " ");          }      }
            • 层次遍历
              • 从二叉树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对节点逐个访问。
              • 队列实现
                • /** * 分层遍历二叉树（按层次从上往下，从左往右）迭代 相当于广度优先遍历，使用队列实现。 * 队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点 * 若左子节点或右子节点不为空，将其压入队列 */ public static void levelTraversal(TreeNode root) { if (root == null) { return; } LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); queue.push(root); while (!queue.isEmpty()) { TreeNode cur = queue.removeFirst(); System.out.print(cur.val + " "); if (cur.left != null) { queue.add(cur.left); } if (cur.right != null) { queue.add(cur.right); } } }}
          • 存储结构
            • 顺序存储结构
            • 链式存储结构
          • 二叉树算法题
            • 求二叉树中的节点个数
              • 递归实现
                • /** * 1. 求二叉树中的节点个数 * 递归O(n)  * * @param root 树根节点 * * @return 节点个数 * */ public static int getNodeNumRec(TreeNode root) {  if (root == null) return 0;  return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1; }
              • 迭代实现
                • /** * 1. 求二叉树中的节点个数 * 迭代O(n) * @param root 树根节点 * @return 节点个数 */public static int getNodeNum(TreeNode root) {    if (root == null) {        return 0;    }    Queue<TreeNode> queue =  new LinkedList<>(); // 用队列保存树节点，先进先出    queue.add(root);    int count = 1; // 节点数量    while (!queue.isEmpty()) {        TreeNode temp = queue.poll(); // 每次从对列中删除节点，并返回该节点信息        if (temp.left != null) { // 添加左子孩子到对列            queue.add(temp.left);            count++;        }        if (temp.right != null) { // 添加右子孩子到对列            queue.add(temp.right);            count++;        }    }    return count;}
            • 求二叉树的深度或高度
              • 递归实现
                • /*** 求二叉树的深度* 递归* @return 树的深度*/public static int getDepthRec(TreeNode root) { if (root == null) { return 0; } return Math.max(getDepthRec(root.left), getDepthRec(root.right)) + 1; }
              • 迭代实现
                • /** * 求二叉树的深度 * 迭代 * @param root 树根节点 * @return 树的深度 */public static int getDepth(TreeNode root) {    if (root == null) {        return 0;    }    int currentLevelCount = 1; // 当前层的节点数量    int nextLevelCount = 0; // 下一层节点数量    int depth = 0; // 树的深度     Queue<TreeNode> queue = new LinkedList<>(); // 对列保存树节点    queue.add(root);    while (!queue.isEmpty()) {        TreeNode temp = queue.remove(); // 移除节点        currentLevelCount--; // 当前层节点数减1        if (temp.left != null) { // 添加左节点并更新下一层节点个数            queue.add(temp.left);            nextLevelCount++;        }        if (temp.right != null) { // 添加右节点并更新下一层节点个数            queue.add(temp.right);            nextLevelCount++;        }        if (currentLevelCount == 0) { // 如果是该层的最后一个节点，树的深度加1            depth++;            currentLevelCount = nextLevelCount; // 更新当前层节点数量并且重置下一层节点数量            nextLevelCount = 0;        }    }    return depth;}
            • 求二叉树第k层的节点个数
              • 递归实现
                • /** * 求二叉树第k层的节点个数 * 递归 * @param root 根节点 * @param k 第k个节点 * @return 第k层节点数 */public static int getNodeNumKthLevelRec(TreeNode root, int k) {    if (root == null || k < 1) {        return 0;    }    if (k == 1) {        return 1;    }    return getNodeNumKthLevelRec(root.left, k - 1) + getNodeNumKthLevelRec(root.right, k - 1);}
            • 求二叉树中叶子节点的个数
              • 递归实现
                • /** * 4. 求二叉树中叶子节点的个数 * 递归 * @param root 根节点 * @return 叶子节点个数 */public static int getNodeNumLeafRec(TreeNode root) {    if (root == null) {        return 0;    }    if (root.left == null && root.right == null) {        return 1;    }    return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right);}
              • 迭代实现
                •  /** * 4. 求二叉树中叶子节点的个数（迭代） * 迭代 * @param root 根节点 * @return 叶子节点个数 */public static int getNodeNumLeaf(TreeNode root){    if (root == null) {        return 0;    }    int leaf = 0; // 叶子节点个数    Queue<TreeNode> queue = new LinkedList<>();    queue.add(root);    while (!queue.isEmpty()) {        TreeNode temp = queue.poll();        if (temp.left == null && temp.right == null) { // 叶子节点            leaf++;        }        if (temp.left != null) {            queue.add(temp.left);        }        if (temp.right != null) {            queue.add(temp.right);        }    }    return leaf;}
            • 判断两棵二叉树是否相同的树
              • 递归实现
                • /** * 5. 判断两棵二叉树是否相同的树。 * 递归 * @param r1 二叉树1 * @param r2 二叉树2 * @return 是否相同 */public static boolean isSameRec(TreeNode r1, TreeNode r2) {    if (r1 == null && r2 == null) { // 都是空        return true;    } else if (r1 == null || r2 == null) { // 有一个为空，一个不为空        return false;    }    if (r1.val != r2.val) { // 两个不为空，但是值不相同        return false;    }    return isSameRec(r1.left, r2.left) && isSameRec(r1.right, r2.right); // 递归遍历左右子节点}
              • 迭代实现
                • /** * 5. 判断两棵二叉树是否相同的树（迭代） * 迭代 * @param r1 二叉树1 * @param r2 二叉树2 * @return 是否相同 */public static boolean isSame(TreeNode r1, TreeNode r2){    if (r1 == null && r2 == null) { // 都是空        return true;    } else if (r1 == null || r2 == null) { // 有一个为空，一个不为空        return false;    }    Stack<TreeNode> stack1 = new Stack<>();    Stack<TreeNode> stack2 = new Stack<>();    stack1.add(r1);    stack2.add(r2);    while (!stack1.isEmpty() && !stack2.isEmpty()) {        TreeNode temp1 = stack1.pop();        TreeNode temp2 = stack2.pop();        if (temp1 == null && temp2 == null) { // 两个元素都为空，因为添加的时候没有对空节点做判断            continue;        } else if (temp1 != null && temp2 != null && temp1.val == temp2.val) {            stack1.push(temp1.left); // 相等则添加左右子节点判断            stack1.push(temp1.right);            stack2.push(temp2.left);            stack2.push(temp2.right);        } else {            return false;        }    }    return true;}
            • 判断二叉树是不是平衡二叉树
              • 递归实现
                • /** * 6. 判断二叉树是不是平衡二叉树 * 递归 * @param root 根节点 * @return 是否二叉平衡树（AVL树） */public static boolean isAVLTree(TreeNode root) {    if (root == null) {        return true;    }    if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1) { // 左右子树高度差大于1        return false;    }    return isAVLTree(root.left) && isAVLTree(root.right); // 递归判断左右子树}
            • 求二叉树的镜像
              • 递归实现
                • /** * 7. 求二叉树的镜像 * 递归 * @param root 根节点 * @return 镜像二叉树的根节点 */public static TreeNode mirrorCopyRec(TreeNode root) {    if (root == null) {        return root;    }    TreeNode newRoot = new TreeNode(root.val); // 创建新节点，然后交换左右子树    newRoot.left = mirrorCopyRec(root.right);    newRoot.right = mirrorCopyRec(root.left);    return newRoot;}
              • 迭代实现
                • /** * 7. 求二叉树的镜像 * 迭代 * @param root 根节点 * @return 镜像二叉树的根节点 */public static TreeNode mirrorCopy(TreeNode root) {    if (root == null) {        return null;    }    Stack<TreeNode> stack = new Stack<TreeNode>();    Stack<TreeNode> newStack = new Stack<TreeNode>();    stack.push(root);    TreeNode newRoot = new TreeNode(root.val);    newStack.push(newRoot);    while (!stack.isEmpty()) {        TreeNode cur = stack.pop();        TreeNode newCur = newStack.pop();        if (cur.right != null) {            stack.push(cur.right);            newCur.left = new TreeNode(cur.right.val);            newStack.push(newCur.left);        }        if (cur.left != null) {            stack.push(cur.left);            newCur.right = new TreeNode(cur.left.val);            newStack.push(newCur.right);        }    }    return newRoot;}
            • 判断两个二叉树是否互相镜像
              • 递归实现
                • /** * 8. 判断两个树是否互相镜像 * @param r1 二叉树 1 * @param r2 二叉树 2 * @return 是否互相镜像 */public static boolean isMirrorRec(TreeNode r1, TreeNode r2) {    if (r1 == null && r2 == null) {        return true;    } else if (r1 == null || r2 == null) {        return false;    }    if (r1.val != r2.val) {        return false;    }    // 递归比较r1的左子树的镜像是不是r2右子树    // 和r1的右子树的镜像是不是r2的左子树    return isMirrorRec(r1.left, r2.right) && isMirrorRec(r1.right, r2.left);}
            • 求二叉树中两个节点的最低公共祖先节点
              • 递归实现
                • /** * 9. 求二叉树中两个节点的最低公共祖先节点 * 递归 * @param root 树根节点 * @param n1 第一个节点 * @param n2 第二个节点 * @return 最低公共祖先节点 */public static TreeNode getLastCommonParentRec(TreeNode root, TreeNode n1, TreeNode n2) {    if (findNodeRec(root.left, n1)) { // 如果n1在左子树        if (findNodeRec(root.right, n2)) { // 如果n2在右子树            return root; // 返回根节点        } else { // 如果n2也在左子树            return getLastCommonParentRec(root.left, n1, n2); // 递归处理        }    } else { // 如果n1在右子树        if (findNodeRec(root.left, n2)) { // 如果n2在左子树            return root; // 返回根节点        } else { // 如果n2在右子树            return getLastCommonParentRec(root.right, n1, n2); // 递归处理        }    }} /** * 递归判断一个点是否在树里 * @param root 根节点 * @param node 查找的节点 * @return 是否找到该节点 */private static boolean findNodeRec(TreeNode root, TreeNode node) {    if (node == null || root == null) {        return false;    }    if (root == node) {        return true;    }    // 先尝试在左子树中查找    boolean found = findNodeRec(root.left, node);    if (!found) { // 如果查找不到，再在右子树中查找        found = findNodeRec(root.right, node);    }    return found;} /** * 9. 树中两个节点的最低公共祖先节点 * 递归解法2（更简单） * @param root 树根节点 * @param n1 第一个节点 * @param n2 第二个节点 * @return 最低公共祖先节点 */public static TreeNode getLastCommonParentRec2(TreeNode root, TreeNode n1, TreeNode n2) {    if (root == null) {        return null;    }    // 如果有一个match，则说明当前node就是要找的最低公共祖先    if (root.equals(n1) || root.equals(n2)) {        return root;    }    TreeNode commonLeft = getLastCommonParentRec2(root.left, n1, n2);    TreeNode commonRight = getLastCommonParentRec2(root.right, n1, n2);    // 如果一个在左子树找到，一个在右子树找到，则说明root是唯一可能得最低公共祖先    if (commonLeft != null && commonRight != null) {        return root;    }    // 其他情况是要不然在左子树要不然在右子树    if (commonLeft != null) {        return commonLeft;    }    return commonRight;}
              • 迭代实现
                • /** * 9. 树中两个节点的最低公共祖先节点 * 迭代 * @param root 树根节点 * @param n1 第一个节点 * @param n2 第二个节点 * @return 第一个公共祖先节点 */public static TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2) {    if (root == null || n1 == null || n2 == null) {        return null;    }    ArrayList<TreeNode> p1 = new ArrayList<>();    boolean res1 = getNodePath(root, n1, p1);    ArrayList<TreeNode> p2 = new ArrayList<>();    boolean res2 = getNodePath(root, n2, p2);    if (!res1 || !res2) {        return null;    }    TreeNode last = null;    Iterator<TreeNode> iter1 = p1.iterator();    Iterator<TreeNode> iter2 = p2.iterator();    while (iter1.hasNext() && iter2.hasNext()) {        TreeNode tmp1 = iter1.next();        TreeNode tmp2 = iter2.next();        if (tmp1 == tmp2) {            last = tmp1;        } else { // 直到遇到非公共节点            break;        }    }    return last;} /** * 把从根节点到node路径上所有的点都添加到path中 * @param root 树根节点 * @param node 终点节点 * @param path 路径 * @return 是否是目标节点 */public static boolean getNodePath(TreeNode root, TreeNode node, ArrayList<TreeNode> path) {    if (root == null) {        return false;    }    path.add(root); // 把这个节点添加到路径中    if (root == node) {        return true;    }    boolean found = false;    found = getNodePath(root.left, node, path); // 先在左子树中找    if (!found) {        found = getNodePath(root.right, node, path);    }    if (!found) { // 如果实在没找到证明这个节点不在路径中，删除刚刚那个节点        path.remove(root);    }    return found;}
            • 判断是否为二分查找树BST
              • 递归实现
                • /** * 10. 判断是否为二分查找树BST * @param root 根节点 * @param pre 上一个保存的节点 * @return 是否为BST树 */public static boolean isValidBST(TreeNode root, int pre){    if (root == null) {        return true;    }    boolean left = isValidBST(root.left, pre);    if (!left) {        return false;    }    if(root.val <= pre) {        return false;    }    pre = root.val;    boolean right = isValidBST(root.right, pre);    if(!right) {        return false;    }    return true;}
              • 迭代实现
                • /**  * 10. 判断是否为二分查找树BST * 迭代 * @param root 根节点 */public boolean isValidBST2(TreeNode root){    Stack<TreeNode> stack = new Stack<>();    //设置前驱节点    TreeNode pre = null;    while(root != null || !stack.isEmpty()){        while (root != null) { // 将当前节点，以及左子树一直入栈，循环结束时，root==null            stack.push(root);            root = root.left;        }        root = stack.pop();        //比较并更新前驱，与普通遍历的区别就在下面四行        if(pre != null && root.val <= pre.val){            return false;        }        pre = root;        root = root.right;  //访问右子树    }    return true;}
        • B树/B-tree/B-树
          • 根结点至少有两个子女（如果B树只有一个根节点，这个根节点的key的数量可以为[1~m-1]）每个非根节点所包含的关键字个数 j 满足：⌈m/2⌉ - 1 <= j <= m - 1，节点的值按非降序方式存放，即从左到右依次增加除根结点以及叶子节点以外的所有结点的度数正好是关键字总数加1，故内部节点的子树个数 k 满足：⌈m/2⌉ <= k <= m所有的叶子结点都位于同一层
          • B+树
            • 有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点，其中⌈m/2⌉ <= n <= m所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点
            • B*树
              • ⌈m*2/3⌉ <= n <=m 这里的n是除根节点之外的内部节点的键增加内部节点中兄弟节点的指针，由左边指向右边
          • 面试题
            • B树，B+树使用场景
              • B树主要用于文件系统，和部分数据库索引，如文档型数据库mongodbB+树主要用于mysql数据库索引。
            • 数据库索引有哪些
              • hash索引和B+树索引hash索引等值查询效率高，但是不能排序，因此不能进行范围查询B+树索引数据有序，能够进行范围查询
            • B树和二叉查找树的性能对比
              • B树包括B+树的设计思想都是尽可能的降低树的高度，以此降低磁盘IO的次数，因为一个索引节点就表示一个磁盘页，页的换入换出次数越多，表示磁盘IO次数越多，越低效。B树算法减少定位数据所在的节点时所经历的磁盘IO次数，从而加快存取速度。二叉查找树，若是放在内存中查找到指定数据，效率其实很高logn。但是索引文件很大，要放入磁盘，树的一个节点就是一个磁盘页，查找到指定元素，需要进行大量的磁盘IO，效率就很低了。
            • B+对比B树的优点
              • 因为B树的每个节点除了存储指向子节点的索引之外，还有data域，因此单一节点存储的指向子节点的索引并不是很多，树高度较高，磁盘IO次数较多，而B+树单一节点存储的指向子节点的索引更多，B+树空间利用率高，因此B+树高度更低，磁盘IO次数更少，性能更好。因为B树的中间节点存储了数据，所以整个树的每一层都有可能查找到要查找的数据，查询性能不稳定，而B+树所有的data都存储在叶子节点，且叶子节点位于同一层，因此查询性能稳定。B树如果想要进行范围查找，需要频繁的进行二叉树的中序遍历，进行范围查找比较复杂，B+树要查找的元素都位于叶子节点，且连接形成有序链表，便于范围查找。
            • 为什么数据库索引不用红黑树而用B+树
              • 红黑树当插入删除元素的时候会进行频繁的变色与旋转（左旋，右旋），来保证红黑树的性质，浪费时间。但是当数据量较小，数据完全可以放入内存中，不需要进行磁盘IO，这时候，红黑树时间复杂度比B+树低。比如TreeSet TreeMap 和HashMap （jdk1.8）就是使用红黑树作为底层数据结构。
      • trie/前缀树/字典树
        • 1.根节点不包含字符，除根节点意外每个节点只包含一个字符。2.从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。3.每个节点的所有子节点包含的字符串不相同。
    • 图
      • 图（Graph）是一种复杂的非线性结构，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。
      • 分类
        • 无向图
          • 顶点+无向边
        • 有向图
          • 顶点+有向边
        • 完全图
          • 任意两个顶点之间都存在边。
          • 有向完全图
          • 无向完全图
        • 带权图/网
          • 边带权值的图
      • 表示方式
        • 二维数组表示/邻接矩阵
        • 链表表示/邻接表
          • 数组+链表
      • 遍历
        • /** * 图的广度优先搜索和深度优先搜索实现 */public class GraphSearch<T> {     public StringBuffer searchPathDFS = new StringBuffer();    public StringBuffer searchPathBFS = new StringBuffer();     /**     * 深度优先搜索实现     *     * @param root     */    public void searchDFS(GraphNode<T> root) {        if (root == null) {            return;        }         // visited root        if (searchPathDFS.length() > 0) {            searchPathDFS.append("->");        }        searchPathDFS.append(root.data.toString());        root.visited = true;         for (GraphNode<T> node : root.neighborList) {            if (!node.visited) {                searchDFS(node);            }        }    }     /**     * 广度优先搜索实现,使用队列     *     * @param root     */    public void searchBFS(GraphNode<T> root) {        IQueue<GraphNode<T>> queue = new Queue<GraphNode<T>>();         // visited root        if (searchPathBFS.length() > 0) {            searchPathBFS.append("->");        }        searchPathBFS.append(root.data.toString());        root.visited = true;         // 加到队列队尾        queue.enqueue(root);         while (!queue.isEmpty()) {            GraphNode<T> r = queue.dequeue();            for (GraphNode<T> node : r.neighborList) {                if (!node.visited) {                    searchPathBFS.append("->");                    searchPathBFS.append(node.data.toString());                    node.visited = true;                     queue.enqueue(node);                }            }        }    }}
        • 深度优先遍历
          • 假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。显然，深度优先搜索是一个递归的过程。
        • 广度优先遍历
          • 从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远。
  • 哈希表
    • 散列表（Hash table，也叫哈希表），是根据关键码值(Keyvalue)而直接进行访问的数据结构。
    • 实现方式
      • 数组+链表
      • 数组+链表+红黑树
    • 哈希函数（散列函数）
      • 将任意长度的数据压缩到某一固定长度的数据摘要的函数。特点：一致性、高效性、均匀性
      • 构造方法
        • 直接定址法
          • 直接以关键字k或者k加上某个常数（k+c）作为哈希地址。
        • 数字分析法
          • 提取关键字中取值比较均匀的数字作为哈希地址。
        • 除留余数法
          • 用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址。
        • 分段叠加法
          • 按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
        • 平方取中法
          • 如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址。
        • 伪随机数法
          • 采用一个伪随机数当作哈希函数。
      • 常见哈希函数
        • 字符串
          • Jenkins Hash
            • uint64_t hash(uint64_t key) {  key = (~key) + (key << 21); // key = (key << 21) - key - 1;  key = key ^ (key >> 24);  key = (key + (key << 3)) + (key << 8); // key * 265  key = key ^ (key >> 14);  key = (key + (key << 2)) + (key << 4); // key * 21  key = key ^ (key >> 28);  key = key + (key << 31);  return key;}
          • BKDRHash
            • Java中每个对象都有一个hashcode方法，主要作用是使得这些对象与容器配合使用，提供一个可供hash的整形数值给容器使用。下面是java中String对象的hashcode实现方式。主要代码段：for (int i=0; i<len; i++) h = 31*h + val[i]; 对于一个字符串s[n-1 - 0]，计算出来的hashcode是：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
          • time33
            • 该算法就是不停的将每个字符乘以33（Apache，PHP，Perl都使用了该算法），形式如下：unsigned long hash = 0;    for (int i=0; i<len; i++)    hash = 33*hash + str[i]; 
          • FNV
            • 该算法对于非常相近的字符串效果很好（比如URL，IP地址等），可以保持较小的冲突率。它有两个版本FNV1和FNV1a。
          • DJB
            • unsigned int DJBHash(char *str)    {        unsigned int hash = 5381;             while (*str){            hash = ((hash << 5) + hash) + (*str++); /* times 33 */        }        hash &= ~(1 << 31); /* strip the highest bit */        return hash;    }   //Redis对其进行了部分调整，不区分大小写unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {    unsigned int hash = (unsigned int)dict_hash_function_seed;     while (len--)        hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */    return hash;}
        • 整数
          • MurmurHash3
            • final int hash(Object k) {    int h = hashSeed;    if (0 != h && k instanceof String) {        return sun.misc.Hashing.stringHash32((String) k);    }     h ^= k.hashCode();     // This function ensures that hashCodes that differ only by    // constant multiples at each bit position have a bounded    // number of collisions (approximately 8 at default load factor).    h ^= (h >>> 20) ^ (h >>> 12);    return h ^ (h >>> 7) ^ (h >>> 4);}
          • variant of single-word Wang/Jenkins hash
            • //Java ConcurrentHashMap中使用的版本 private static int hash(int h) {        // Spread bits to regularize both segment and index locations,        // using variant of single-word Wang/Jenkins hash.        h += (h <<  15) ^ 0xffffcd7d;        h ^= (h >>> 10);        h += (h <<   3);        h ^= (h >>>  6);        h += (h <<   2) + (h << 14);        return h ^ (h >>> 16);}
    • 哈希冲突
      • 开放定址法/封闭散列（closed hashing）/再散列法
        • 基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=（H（key）+di）% m   i=1，2，…，n其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。 优点： ①记录更容易进行序列化（serialize）操作 。②如果记录总数可以预知，可以创建完美哈希函数，此时处理数据的效率是非常高的。 缺点： ①存储记录的数目不能超过桶数组的长度，如果超过就需要扩容，而扩容会导致某次操作的时间成本飙升，这在实时或者交互式应用中可能会是一个严重的缺陷 ②使用探测序列，有可能其计算的时间成本过高，导致哈希表的处理性能降低 ③由于记录是存放在桶数组中的，而桶数组必然存在空槽，所以当记录本身尺寸（size）很大并且记录总数规模很大时，空槽占用的空间会导致明显的内存浪费 ④删除记录时，比较麻烦。比如需要删除记录a，记录b是在a之后插入桶数组的，但是和记录a有冲突，是通过探测序列再次跳转找到的地址，所以如果直接删除a，a的位置变为空槽，而空槽是查询记录失败的终止条件，这样会导致记录b在a的位置重新插入数据前不可见，所以不能直接删除a，而是设置删除标记。这就需要额外的空间和操作。
        • 线性探测再散列
          • 增量序列：dii=1，2，3，…，m-1特点：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
        • 二次探测再散列
          • 增量序列：di=12，-12，22，-22，…，k2，-k2    ( k<=m/2 )特点：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
        • 伪随机探测再散列
          • 增量序列：di=伪随机数序列。具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。
      • 再哈希法
        • 这种方法是同时构造多个不同的哈希函数：Hi=RH1（key）  i=1，2，…，k当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
      • 链地址法/开放散列（open hashing）/ 拉链法
        • 基本思想：首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。（将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行）。链地址法适用于经常进行插入和删除的情况。 优点： ①对于记录总数频繁可变的情况，处理的比较好（也就是避免了动态调整的开销）。 ②由于记录存储在结点中，而结点是动态分配，不会造成内存的浪费，所以尤其适合那种记录本身尺寸（size）很大的情况，因为此时指针的开销可以忽略不计了。 ③删除记录时，比较方便，直接通过指针操作即可。 缺点： ①存储的记录是随机分布在内存中的，这样在查询记录时，相比结构紧凑的数据类型（比如数组），哈希表的跳转访问会带来额外的时间开销。 ②如果所有的 key-value 对是可以提前预知，并之后不会发生变化时（即不允许插入和删除），可以人为创建一个不会产生冲突的完美哈希函数（perfect hash function），此时封闭散列的性能将远高于开放散列。 ③由于使用指针，记录不容易进行序列化（serialize）操作。
      • 建立公共溢出区
        • 基本思想：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
    • 应用
      • HashMap
        • HashMap是基于哈希表的Map接口的非同步实现，线程不安全。
      • HashTable
        • Hashtable是基于哈希表的Map接口的同步实现，线程安全。
      • ConcurrentHashMap
        • ConcurrentHashMap是基于segment数组内嵌哈希表的ConcurrentMap接口实现，线程安全。 ConcurrentHashMap的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树是为了提高查找效率。 ConcurrentHashMap的主要实现原理就是使用segments将原本唯一的hashtable分段, 增加并发能力。 ConcurrentHashMap使用两次哈希算法（single-word Wang/Jenkins哈希算法的一个变种）尽量将元素均匀的分布到不同的segment的hashtable中：第一次哈希算法找到segment；第二次哈希算法找到hashentry；这两次哈希算法要求能尽量将元素均匀的分布到不同的segment的hashtable中, ConcurrentHashMap使用的是single-word Wang/Jenkins哈希算法的一个变种
    • 面试题
      • Two Sum
        • Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.Example:Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].
        • 暴力法
          • public int[] twoSum1(int[] nums, int target) {     int length = nums.length;     for (int i = 0; i < length; ++ i)         for (int j = i + 1; j < length; ++ j)             if (nums[i] + nums[j] == target)                 return new int[]{i,j};     return null; }
        • 两遍哈希表
          • //解题思路：以空间换时间public int[] twoSum2(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[] { i, map.get(complement) }; } } throw new IllegalArgumentException("No two sum solution"); }
        • 一遍哈希表
          • //解题思路：所求的两个值，一旦有一个已经在哈希表中，那么另一个值便可在数组遍历过程中找出public int[] twoSum3(int[] nums, int target) { HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();        int[] res = new int[2];        for (int i = 0; i < nums.length; ++i) {            if (m.containsKey(target - nums[i])) {                res[0] = i;                res[1] = m.get(target - nums[i]);                break;            }            m.put(nums[i], i);        }        return res; }
• 算法
  • 算法是为实现某个任务而构造的简单指令集。
  • 递归
    • 递归就是指程序调用自身的编程思想。递归是将大问题化为相同结构的小问题，从待求解的问题出发，一直分解到已经已知答案的最小问题为止，然后再逐级返回，从而得到大问题的解。1. 程序执行到某个方法时，会为该方法开辟独立的空间（入栈）。2. 每个空间的数据（局部变量）独立。3. 栈的特性先进后出，约束条件（递归结束条件）为真时，开始从最顶层方法执行递归函数的其他语句。4. 递归层次过多会造成栈溢出。
    • 应用
      • 数学问题
        • 八皇后
        • 汉诺塔
        • 阶乘
        • 迷宫
        • 球和篮子
      • 用栈解决的问题
      • 部分算法
        • 快速排序
        • 归并排序
        • 二分查找
        • 分治算法
  • 迭代
    • 利用已知的变量值，根据递推公式不断演进得到变量新值的编程思想。
  • 算法复杂度
    • 时间复杂度
      • 指执行算法所需要的计算工作量
      • 时间频度/语句频度T(n)
      • 时间复杂度
      • 大O表示法
        • 常数阶O(1)
        • 线性阶O(n)
        • 对数阶O(logn)
        • 线性对数阶O(nlogn)
        • 平方阶O(2ⁿ)
        • 立方阶O(n³)
        • k次方阶O(n^k)
        • 指数阶O(2ⁿ)
        • 阶乘阶O(n!)
        • 平方根阶O(√n)
    • 空间复杂度
      • 指执行这个算法所需要的内存空间
  • 排序算法
    • 术语
      • 稳定
        • 如果a原本在b前面，而a=b，排序之后a仍然在b的前面
      • 不稳定
        • 如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面
      • 内排序
        • 所有排序操作都在内存中完成
      • 外排序
        • 由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
    • 非线性时间比较类
      • 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
      • 交换排序
        • 冒泡排序
          •  public static int[] bubbleSort(int[] array) {      if (array.length == 0)          return array;      for (int i = 0; i < array.length; i++)          for (int j = 0; j < array.length - 1 - i; j++)              if (array[j + 1] < array[j]) {                  int temp = array[j + 1];                  array[j + 1] = array[j];                  array[j] = temp;              }      return array;  }
        • 快速排序
          • 快排算法是基于分治策略的排序算法，其基本思想是，对于输入的数组a[low, high]，按以下三个步骤进行排序。(1)分解：以a[p]为基准将a[low: high]划分为三段a[low：p-1]，a[p]和a[p+1：high]，使得a[low：p-1]中任何一个元素小于等于a[p]， 而a[p+1: high]中任何一个元素大于等于a[p]。(2)递归求解：通过递归调用快速排序算法分别对a[low：p-1]和a[p+1：high]进行排序。(3)合并：由于对a[low：p-1]和a[p+1：high]的排序是就地进行的，所以在a[low：p-1]和a[p+1：high]都已排好序后，不需要执行任何计算，a[low：high]就已经排好序了。
          • 基准选择
            • 固定基准
            • 随机基准
              • /** * 快速排序方法 * @param array * @param start * @param end * @return */public static int[] QuickSort(int[] array, int start, int end) {    if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;    int smallIndex = partition(array, start, end);    if (smallIndex > start)        QuickSort(array, start, smallIndex - 1);    if (smallIndex < end)        QuickSort(array, smallIndex + 1, end);    return array;}/** * 快速排序算法——partition * @param array * @param start * @param end * @return */public static int partition(int[] array, int start, int end) {    int pivot = (int) (start + Math.random() * (end - start + 1));    int smallIndex = start - 1;    swap(array, pivot, end);    for (int i = start; i <= end; i++)        if (array[i] <= array[end]) {            smallIndex++;            if (i > smallIndex)                swap(array, i, smallIndex);        }    return smallIndex;} /** * 交换数组内两个元素 * @param array * @param i * @param j */public static void swap(int[] array, int i, int j) {    int temp = array[i];    array[i] = array[j];    array[j] = temp;}
            • 三数取中
              • 取出第一个，中间和最后一个元素从小到大排序后，中间元素为基准并和倒数第二个元素交换
              • i和j分别从第一个元素和倒数第二个元素开始。i在j的左边时，将i右移，直到发现大于等于基准的元素，然后将j左移，直到发现小于等于基准的元素。i和j停止时，元素互换。这样就把大于等于基准的移到了右边，小于等于基准的移到了左边
              • 重复上面的步骤，直到i和j交错，将基准元素与i所指向的元素交换，使得基准元素将整个元素集合分割为小于基准和大于基准的元素子集
              • 最后再对子集进行上述的操作，直到子集数小于5，此时可用插入排序优化
          • 多个基准
            • JDK1.7 三个基准
            • JDK1.8 五个基准
          • 优化
            • 序列长度达到一定大小时，使用插入排序
            • 尾递归优化
            • 聚集元素
            • 多线程处理
          • JDK8中Arrays.sort底层原理
            • 阀值
              • 个数&lt;47
                • 插入排序
              • 47&lt;=个数&lt;=286
                • 五个基准的快排
              • 个数&gt;286
                • 不具备结构
                • 具备结构
                  • 归并排序
      • 插入排序
        • 直接插入排序
          • public static int[] insertionSort(int[] array) {        if (array.length == 0)            return array;        int current;        for (int i = 0; i < array.length - 1; i++) {            current = array[i + 1];            int preIndex = i;            while (preIndex >= 0 && current < array[preIndex]) {                array[preIndex + 1] = array[preIndex];                preIndex--;            }            array[preIndex + 1] = current;        }        return array;    }
        • 希尔排序
          •  public static int[] ShellSort(int[] array) {        int len = array.length;        int temp, gap = len / 2;        while (gap > 0) {            for (int i = gap; i < len; i++) {                temp = array[i];                int preIndex = i - gap;                while (preIndex >= 0 && array[preIndex] > temp) {                    array[preIndex + gap] = array[preIndex];                    preIndex -= gap;                }                array[preIndex + gap] = temp;            }            gap /= 2;        }        return array;    }
      • 选择排序
        • 简单选择排序
          • public static int[] selectionSort(int[] array) {        if (array.length == 0)             return array;        for (int i = 0; i < array.length; i++) {            int minIndex = i;            for (int j = i; j < array.length; j++) {                if (array[j] < array[minIndex]) //找到最小的数                    minIndex = j; //将最小数的索引保存            }            int temp = array[minIndex];            array[minIndex] = array[i];            array[i] = temp;        }        return array;    }
        • 堆排序
          • //声明全局变量，用于记录数组array的长度；static int len;    /**     * 堆排序算法     *     * @param array     * @return     */    public static int[] HeapSort(int[] array) {        len = array.length;        if (len < 1) return array;        //1.构建一个最大堆        buildMaxHeap(array);        //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆        while (len > 0) {            swap(array, 0, len - 1);            len--;            adjustHeap(array, 0);        }        return array;    }    /**     * 建立最大堆     *     * @param array     */    public static void buildMaxHeap(int[] array) {        //从最后一个非叶子节点开始向上构造最大堆        for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒，此处应该为 i = (len/2 - 1)             adjustHeap(array, i);        }    }    /**     * 调整使之成为最大堆     *     * @param array     * @param i     */    public static void adjustHeap(int[] array, int i) {        int maxIndex = i;        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树        if (i * 2 < len && array[i * 2] > array[maxIndex])            maxIndex = i * 2;        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树        if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])            maxIndex = i * 2 + 1;        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。        if (maxIndex != i) {            swap(array, maxIndex, i);            adjustHeap(array, maxIndex);        }    }
      • 归并排序
        • 二路归并排序
          •     /**     * 归并排序     *     * @param array     * @return     */    public static int[] MergeSort(int[] array) {        if (array.length < 2) return array;        int mid = array.length / 2;        int[] left = Arrays.copyOfRange(array, 0, mid);        int[] right = Arrays.copyOfRange(array, mid, array.length);        return merge(MergeSort(left), MergeSort(right));    }    /**     * 归并排序——将两段排序好的数组结合成一个排序数组     *     * @param left     * @param right     * @return     */    public static int[] merge(int[] left, int[] right) {        int[] result = new int[left.length + right.length];        for (int index = 0, i = 0, j = 0; index < result.length; index++) {            if (i >= left.length)                result[index] = right[j++];            else if (j >= right.length)                result[index] = left[i++];            else if (left[i] > right[j])                result[index] = right[j++];            else                result[index] = left[i++];        }        return result;    }
        • 多路归并排序
          • import java.io.*;import java.util.*;import org.apache.commons.io.*; public class MergeSort {  private static FastQSortAlgorithm<String> QQ = new FastQSortAlgorithm<String>();   private MergeSort() {  }   /**   * 得到指定文件的行数   * @param fileC String   * @return int   * @throws IOException   */  private static int getFileLineSize(String fileC) throws IOException {    Reader fC = null;    try {      fC = new FileReader(fileC);       LineIterator it = IOUtils.lineIterator(fC);      int lineSize = 0;      while(it.hasNext()) {        it.nextLine();        lineSize++;      }      return lineSize;    } finally {      IOUtils.closeQuietly(fC);    }  }   /**   * 得到下一行的内容,如果已到文件末尾返回NULL   * @param iterator LineIterator   * @return String   */  private static String nextLine(LineIterator iterator) {    if(iterator.hasNext()) {      return iterator.nextLine();    } else {      return null;    }  }   /**   * 读指定行数的字符串到缓冲区列表里   * @param iterator LineIterator   * @param bufList List   * @param lines int   */  private static void readLines(LineIterator iterator, List<String> bufList, int lines) {    for(int i = 0; i < lines; i++) {      if(!iterator.hasNext()) {        break;      }      bufList.add(iterator.nextLine());    }  }   /**   * 扫描fileC中的归并段并把它们交替分别送到文件fileA和fileB中,   * 本次归并段的大小为k*blockSize   * @param fileA String   * @param fileB String   * @param fileC String   * @param k int   * @param blockSize int   */  private static void split(String fileA, String fileB, String fileC, int k,                            int blockSize) throws FileNotFoundException, IOException {    boolean useA = true;    int i = 0;     List<String> bufList = new ArrayList<String>(blockSize); //大小为blockSize的缓冲区    Writer fA = null;    Writer fB = null;    Reader fC = null;    try {      fA = new BufferedWriter(new FileWriter(fileA));      fB = new BufferedWriter(new FileWriter(fileB));      fC = new FileReader(fileC);       LineIterator itC = IOUtils.lineIterator(fC);      while(itC.hasNext()) {        //->读入数据块        bufList.clear();        readLines(itC, bufList, blockSize);        //<-读入数据块         if(useA) {          IOUtils.writeLines(bufList, "\n", fA);        } else {          IOUtils.writeLines(bufList, "\n", fB);        }         if(++i == k) {          i = 0;          useA = !useA;        }      }    } finally {      bufList.clear();       IOUtils.closeQuietly(fA);      IOUtils.closeQuietly(fB);      IOUtils.closeQuietly(fC);    }  }   /**   * n为当前归并段大小(k*blockSize);将文件fX的后续归并段拷入到fY,变量currRunPos为当前归并段的索引   * @param fileX String   * @param fileY String   * @param currRunPos int   * @param n int   * @return int 当前归并段的索引   */  private static int copyTail(LineIterator fileX, Writer fileY, int currRunPos,                              int n) throws IOException {    //从当前位置到归并段结束,拷贝每个数据    while(currRunPos <= n) {      //若没有更多的数据项,则文件结束且归并段结束      if(!fileX.hasNext()) {        break;      }       //修改当前归并段位置并将数据项写入fY      currRunPos++;      IOUtils.write(fileX.nextLine() + "\n", fileY);    }     return currRunPos;  }   /**   * 将文件fA和fB中长度为n(k*blockSize)的归并段合并回fC中   * @param fileA String   * @param fileB String   * @param fileC String   * @param n int   * @throws IOException   */  private static void merge(String fileA, String fileB, String fileC, int n) throws      IOException {    //currA和currB表示在当前归并段中的位置    int currA = 1;    int currB = 1;     //分别从fA和fB中读出的数据项    String dataA, dataB;     Reader fA = null;    Reader fB = null;    Writer fC = null;    try {      fA = new FileReader(fileA);      fB = new FileReader(fileB);      fC = new BufferedWriter(new FileWriter(fileC));       LineIterator itA = IOUtils.lineIterator(fA);      LineIterator itB = IOUtils.lineIterator(fB);       dataA = nextLine(itA);      dataB = nextLine(itB);      for(; ; ) {        //若(dataA<=dataB),则将dataA拷贝到fC并修改当前归并段的位置        if(dataA.compareTo(dataB) <= 0) {          IOUtils.write(dataA + "\n", fC);           //从fA中取下一归并段,若不存在,则已到文件尾,应将fB的后续归并段拷入到fC;          //若当前位置>n,则已将所有fA的归并段拷完,应拷贝fB的后续归并段          dataA = nextLine(itA);          currA++;          if(dataA == null || currA > n) {            IOUtils.write(dataB + "\n", fC);            currB++;            currB = copyTail(itB, fC, currB, n);             //fA的大小>=fB的大小;若在fA的文件尾,则结束            if(dataA == null) {              break;            } else { //否则,应在新的归并段中,重置当前位置              currA = 1;            }             //取fB中的下一项.若不存在,则只有fA中剩余的部分要拷贝到fC,            //退出循环前将当前归并段写入fC            dataB = nextLine(itB);            if(dataB == null) {              IOUtils.write(dataA + "\n", fC);              currA = 2;              break;            } else { //否则,重置fB中当前归并段              currB = 1;            }          }        } else { //否则(dataA>dataB)          IOUtils.write(dataB + "\n", fC);           //从fB中取下一归并段,若不存在,则已到文件尾,应将fA的后续归并段拷入到fC;          //若当前位置>n,则已将所有fB的归并段拷完,应拷贝fA的后续归并段          dataB = nextLine(itB);          currB++;          if(dataB == null || currB > n) {            IOUtils.write(dataA + "\n", fC);            currA++;            currA = copyTail(itA, fC, currA, n);             //若fB中没有更多项,则置fA的当前位置,准备拷贝fA中的最后归并段到fC中            if(dataB == null) {              currA = 1;              break;            } else { //否则,置fB的当前位置,并从fA中读入数据              currB = 1;              if((dataA = nextLine(itA)) == null) {                break;              } else {                currA = 1;              }            }          }        }      } //<- end for(; ;)       //将fA中可能存在的剩余的归并段写入fC中(注:fA的长度时>=fB的)      if(dataA != null && dataB == null) {        currA = copyTail(itA, fC, currA, n);      }    } finally {      IOUtils.closeQuietly(fA);      IOUtils.closeQuietly(fB);      IOUtils.closeQuietly(fC);    }  }   /**   * 用指定的blockSize块大小,排序指定的文件fileC   * @param fileC String   * @param blockSize int   * @throws IOException   */   /**   * 用指定的blockSize块大小,排序指定的文件fileSource,排序后的文件是fileOut   * @param fileSource String   * @param fileOut String   * @param blockSize int   * @param removeDuple   * @throws IOException   */  public static void sort(String fileSource,String fileOut, int blockSize,boolean removeDuple) throws IOException {    String fileA = File.createTempFile("wjw", null).getAbsolutePath();    String fileB = File.createTempFile("wjw", null).getAbsolutePath();         int mergeIndex = 1;    int lineSize = getFileLineSize(fileSource);    int k = 1;    int n = k * blockSize;    boolean useA = true;    List<String> list = new ArrayList<String>(blockSize);     Writer fA = null;    Writer fB = null;    Reader fC = null;    try {      fA = new BufferedWriter(new FileWriter(fileA));      fB = new BufferedWriter(new FileWriter(fileB));      fC = new FileReader(fileSource);       LineIterator itC = IOUtils.lineIterator(fC);      if(lineSize <= blockSize) { //对于小文件,从fC读入数据,直接排序后写回文件中        readLines(itC, list, lineSize);        Collections.sort(list);        IOUtils.closeQuietly(fC);        FileUtils.writeLines(new File(fileOut), "GBK", list, "\n");         list.clear();                 if(removeDuple) {          removeDuple(fileOut);        }        return;      }       //->第一次分割,合并      System.out.println("第:"+mergeIndex+"分割,合并");      while(itC.hasNext()) {        list.clear();        readLines(itC, list, blockSize);         Collections.sort(list);        if(useA) {          IOUtils.writeLines(list, "\n", fA);        } else {          IOUtils.writeLines(list, "\n", fB);        }         useA = !useA;      }      list.clear();       IOUtils.closeQuietly(fA);      IOUtils.closeQuietly(fB);      IOUtils.closeQuietly(fC);      merge(fileA, fileB, fileOut, blockSize);      mergeIndex++;      //<-第一次分割,合并       //->将当前归并段大小加倍,循环进行      k = k * 2;      n = k * blockSize;      while(n < lineSize) { //当n>=文件大小时,fC仅剩一个已排好序的归并段        System.out.println("第:"+mergeIndex+"分割,合并");        split(fileA, fileB, fileOut, k, blockSize);        merge(fileA, fileB, fileOut, n);        mergeIndex++;        k = k * 2;        n = k * blockSize;      }      //->将当前归并段大小加倍,循环进行     } finally {      IOUtils.closeQuietly(fA);      IOUtils.closeQuietly(fB);      IOUtils.closeQuietly(fC);       (new File(fileA)).delete();      (new File(fileB)).delete();    }         if(removeDuple) {      removeDuple(fileOut);    }  }   /**   * 删除已经排好序的文件中重复的数据   * @param fileC String   * @throws IOException   */  private static void removeDuple(String fileC) throws IOException {    System.out.println("去重");    Reader fC = null;    Writer fTemp = null;    File tempFile = File.createTempFile("wjw", null);    try {      fC = new FileReader(fileC);      fTemp = new BufferedWriter(new FileWriter(tempFile));       String tmpA = "";      String tmpB = "";      LineIterator itC = IOUtils.lineIterator(fC);      while(itC.hasNext()) {        tmpB = itC.nextLine();        if(tmpB.compareTo(tmpA) != 0) {          IOUtils.write(tmpB + "\n", fTemp);          tmpA = tmpB;        }      }    } finally {      IOUtils.closeQuietly(fTemp);      IOUtils.closeQuietly(fC);    }     File cFile = new File(fileC);    if(cFile.delete()) {      if(tempFile.renameTo(cFile)) {        tempFile.delete();      }    }  }   public static String formatSecond(long seconds) {    long h = seconds /(60*60);    StringBuffer sb = new StringBuffer();         sb.append(h+"小时");         seconds = seconds%(60*60);     long c = seconds /60;    sb.append(c+"分");     sb.append(seconds %60+"秒");         return sb.toString();  }   public static void main(String args[]) {    try {      String fileName = "d:/ESort.txt";      int blockSize = 100000;       long c1 = System.currentTimeMillis();      MergeSort.sort(fileName,fileName + "_SORT", blockSize,true);      long c2 = (System.currentTimeMillis() - c1) / 1000;      System.out.println("耗时:"+formatSecond(c2));    } catch(IOException ex) {      ex.printStackTrace();    }  } }
    • 线性时间非比较类
      • 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
      • 计数排序
        • /**     * 计数排序     *     * @param array     * @return     */    public static int[] CountingSort(int[] array) {        if (array.length == 0) return array;        int bias, min = array[0], max = array[0];        for (int i = 1; i < array.length; i++) {            if (array[i] > max)                max = array[i];            if (array[i] < min)                min = array[i];        }        bias = 0 - min;        int[] bucket = new int[max - min + 1];        Arrays.fill(bucket, 0);        for (int i = 0; i < array.length; i++) {            bucket[array[i] + bias]++;        }        int index = 0, i = 0;        while (index < array.length) {            if (bucket[i] != 0) {                array[index] = i - bias;                bucket[i]--;                index++;            } else                i++;        }        return array;    }
      • 基数排序
        • /**     * 基数排序     * @param array     * @return     */    public static int[] RadixSort(int[] array) {        if (array == null || array.length < 2)            return array;        // 1.先算出最大数的位数；        int max = array[0];        for (int i = 1; i < array.length; i++) {            max = Math.max(max, array[i]);        }        int maxDigit = 0;        while (max != 0) {            max /= 10;            maxDigit++;        }        int mod = 10, div = 1;        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();        for (int i = 0; i < 10; i++)            bucketList.add(new ArrayList<Integer>());        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {            for (int j = 0; j < array.length; j++) {                int num = (array[j] % mod) / div;                bucketList.get(num).add(array[j]);            }            int index = 0;            for (int j = 0; j < bucketList.size(); j++) {                for (int k = 0; k < bucketList.get(j).size(); k++)                    array[index++] = bucketList.get(j).get(k);                bucketList.get(j).clear();            }        }        return array;    }
      • 桶排序
        • /**     * 桶排序     *      * @param array     * @param bucketSize     * @return     */    public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {        if (array == null || array.size() < 2)            return array;        int max = array.get(0), min = array.get(0);        // 找到最大值最小值        for (int i = 0; i < array.size(); i++) {            if (array.get(i) > max)                max = array.get(i);            if (array.get(i) < min)                min = array.get(i);        }        int bucketCount = (max - min) / bucketSize + 1;        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);        ArrayList<Integer> resultArr = new ArrayList<>();        for (int i = 0; i < bucketCount; i++) {            bucketArr.add(new ArrayList<Integer>());        }        for (int i = 0; i < array.size(); i++) {            bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));        }        for (int i = 0; i < bucketCount; i++) {            if (bucketSize == 1) { // 如果带排序数组中有重复数字时  感谢 @见风任然是风 朋友指出错误                for (int j = 0; j < bucketArr.get(i).size(); j++)                    resultArr.add(bucketArr.get(i).get(j));            } else {                if (bucketCount == 1)                    bucketSize--;                ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);                for (int j = 0; j < temp.size(); j++)                    resultArr.add(temp.get(j));            }        }        return resultArr;    }
  • 查找算法
    • 顺序查找/线性查找
      • /** * 有哨兵顺序查找 * @param a 数组(下标为0存放哨兵元素) * @param key 待查询关键字 * @return 关键字下标 返回0 则未找到 */public static int sequentialSearch2(int[] a, int key) { int index = a.length - 1; a[0] = key;// 将下标为0的数组元素设置为哨兵 while (a[index] != key) { index--; } return index;}
    • 二分查找/折半查找
      • /** * 折半查找 * @param a 数组 * @param key 待查找关键字 * @return 返回折半下标， -1表示不存在该关键字 */public static int binarySearch(int[] a, int key) { int low, mid, high; low = 0;// 最小下标 high = a.length - 1;// 最大小标 while (low <= high) { mid = (high + low) / 2;// 折半下标 if (key > a[mid]) { low = mid + 1; // 关键字比 折半值 大，则最小下标 调成 折半下标的下一位 } else if (key < a[mid]) { high = mid - 1;// 关键字比 折半值 小，则最大下标 调成 折半下标的前一位 } else { return mid; // 当 key == a[mid] 返回 折半下标 } } return -1;}
    • 插值查找
      • /** * 插值查找 * @param a  数组 * @param key 待查找关键字 * @return 返回折半下标， -1表示不存在该关键字 */public static int interpolationSearch(int[] a, int key) { int low, mid, high; low = 0;// 最小下标 high = a.length - 1;// 最大小标 while (low < high) { mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]); // mid = (high + low) / 2;// 折半下标 if (key > a[mid]) { low = mid + 1; // 关键字比 折半值 大，则最小下标 调成 折半下标的下一位 } else if (key < a[mid]) { high = mid - 1;// 关键字比 折半值 小，则最大下标 调成 折半下标的前一位 } else { return mid; // 当 key == a[mid] 返回 折半下标 } } return -1;}
    • 斐波那契查找
      • /** 斐波那契数列 */static int[] f = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 }; /** * 斐波那契查找(黄金分割原理) * @param a 待查询数组 * @param key 待查找关键字 * @return 返回关键字在a数组中的下标，返回-1表示数组中不存在此关键字 */public static int fibonaciSearch(int[] a, int key) { int low, mid, high, k; low = 0; high = a.length - 1; // 斐波那契数列下标 k = 0; // 获取斐波那契分割值下标 while (high > f[k] - 1) k++; // 利用Java工具类Arrays构造长度为f[k]的新数组并指向引用a a = Arrays.copyOf(a, f[k]); // 对新数组后面多余的元素赋值最大的元素 for (int i = high + 1; i < f[k]; i++) { a[i] = a[high];//当key是是最大值时候，防止角标越界异常 } while (low <= high) { // 前半部分有f[k-1]个元素，由于下标从0开始 // 减去 1 获取 分割位置元素的下标 mid = low + f[k - 1] - 1;  if (key < a[mid]) {// 关键字小于分割位置元素，则继续查找前半部分，高位指针移动 high = mid - 1; // (全部元素) = (前半部分)+(后半部分) // f[k] = f[k-1] + f[k-2] // 因为前半部分有f[k-1]个元素， 则继续拆分f[k-1] = f[k-2] + f[k-3]成立 // 即在f[k-1]个元素的前半部分f[k-2]中继续查找，所以k = k - 1, // 则下次循环mid = low + f[k - 1 - 1] - 1; k = k - 1; } else if (key > a[mid]) {// 关键字大于分割位置元素，则查找后半部分，低位指针移动 low = mid + 1; // (全部元素) = (前半部分)+(后半部分) // f[k] = f[k-1] + f[k-2] // 因为后半部分有f[k-2]个元素， 则继续拆分f[k-2] = f[k-3] + f[k-4]成立 // 即在f[k-2]个元素的前半部分f[k-3]继续查找，所以k = k - 2, // 则下次循环mid = low + f[k - 2 - 1] - 1; k = k - 2; } else { // 当条件成立的时候，则找到元素 if (mid <= high) return mid; else // 出现这种情况是查找到补充的元素 // 而补充的元素与high位置的元素一样 return high; } } return -1;}
  • 常用十大算法
    • 二分查找算法
    • 分治算法
      • 类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。适用情况1、一定是先找到最小问题规模时的求解方法2、然后考虑随着问题规模增大时的求解方法3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。1.该问题的规模缩小到一定的程度就可以容易地解决；2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3.利用该问题分解出的子问题的解可以合并为该问题的解；4.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。第一特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加。第二特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用。第三特征是关键，能否利用分治法完全取决于问题是否具有第三特征，如果具备了第一和第二特征，而不具备第三特征，则可以考虑用贪心法或动态规划法。第四特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
    • 动态规划算法
      • 1.动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法2.动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。3.与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )4.动态规划可以通过填表的方式来逐步推进，得到最优解。
    • 贪心算法
      • 贪心算法是指：在每一步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。 贪心算法每一步必须满足一下条件：1、可行的：即它必须满足问题的约束。2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。3、不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。
    • KMP算法
      • KMP算法的实质就是以空间换时间，在匹配之前将模式串的一些信息存储起来（next数组），在随后的匹配过程中利用这些信息减少不必要的匹配次数，以提高匹配效率。 public class KMP {     /**     * 求出一个字符数组的next数组     * @param t 字符数组     * @return next数组     */    public static int[] getNextArray(char[] t) {        int[] next = new int[t.length];        next[0] = -1;        next[1] = 0;        int k;        for (int j = 2; j < t.length; j++) {            k=next[j-1];            while (k!=-1) {                if (t[j - 1] == t[k]) {                    next[j] = k + 1;                    break;                }                else {                    k = next[k];                }                next[j] = 0;  //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值            }        }        return next;    }     /**     * 对主串s和模式串t进行KMP模式匹配     * @param s 主串     * @param t 模式串     * @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1     */    public static int kmpMatch(String s, String t){        char[] s_arr = s.toCharArray();        char[] t_arr = t.toCharArray();        int[] next = getNextArray(t_arr);        int i = 0, j = 0;        while (i<s_arr.length && j<t_arr.length){            if(j == -1 || s_arr[i]==t_arr[j]){                i++;                j++;            }            else                j = next[j];        }        if(j == t_arr.length)            return i-j;        else            return -1;    }     public static void main(String[] args) {        System.out.println(kmpMatch("abcabaabaabcacb", "abaabcac"));    } }
    • 普里姆算法
      • 从图中任意取出一个顶点，把它当成一棵树，然后从与这棵树相接的边中选取一条权值最小的边，并将这条边及其所连接的顶点一同并入这棵树中，重复以上操作，直到所有的顶点都被并入到这棵树中为止。
    • 克鲁斯卡尔算法
      • 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止
    • 迪杰斯塔拉算法/Dijkstra
      • 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
    • 弗洛伊德算法/Floyd
      • 弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。
    • 骑士周游问题/马踏棋盘算法
      • /*     * 马踏棋盘问题：(贪婪法求解)     * 棋盘有64个位置，“日”字走法，刚好走满整个棋盘     */     //下一个走法的方向类    class Direction{        int x;        int y;        int wayOutNum;    }     public class Hores_chessboard_1 {        static final int[] dx = { -2, -1, 1, 2, 2, 1, -1, -2 }; // x方向的增量          static final int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1 }; // y方向的增量          static final int N = 8;             static int[][] chessboard = new int[N][N]; // 棋盘      /**     *      * @param nami     * @param x,y为棋子的位置     * @return 如果棋子的位置不合法，则返回一个大于8的数。     * 否则返回棋子的下个出路的个数     */    static int wayOut(int x, int y){                int count = 0;        int tx, ty, i;        //判断是否超出棋盘边界，该位置是否已经下过        if(x<0 || x>7 || y<0 || y>7 || chessboard[x][y]!=0){            return 9;        }        for(i=0; i<N; i++){            tx = x+dx[i];            ty = y+dy[i];            //如果棋子的下个出路可行，则出路数自加一次            if(tx>-1 && tx<8 && ty>-1 && ty<8 && chessboard[tx][ty]==0)                count++;        }        return count;    }     /**     * 按照棋子的下个出路的个数从低到高排序     * @param next 棋子的八个位置的数组     */    static void sort(Direction[] next){        int i, j, index;        Direction temp = null;        //这里用的选择排序        for(i=0; i<N; i++){            index = i;            for(j=i+1; j<N; j++){                if(next[index].wayOutNum > next[j].wayOutNum)                    index = j;            }            if(i != index){                temp = next[i];                next[i] = next[index];                next[index] = temp;            }        }    }     static void Move(int x, int y, int step){        int i, j;        int tx, ty;        //如果step==64，则说明每个棋格都走到了，现在只需要打印结果就完了        if(step == N*N){            for(i=0; i<N; i++){                for(j=0; j<N; j++){                    System.out.printf("%3d", chessboard[i][j]);                }                System.out.println();            }            System.exit(0);        }         //下一个棋子的N个位置的数组        Direction[] next = new Direction[N];         for(i=0; i<N; i++){            Direction temp = new Direction();            temp.x = x+dx[i];            temp.y = y+dy[i];            next[i] = temp;            //循环得到下个棋子N处位置的下个出路的个数            next[i].wayOutNum = wayOut(temp.x, temp.y);        }         //配合贪婪算法，按下个棋子的下个出路数排序后，next[0]就是下个出路数最少的那个        sort(next);         for(i=0; i<N; i++){            tx = next[i].x;            ty = next[i].y;            chessboard[tx][ty] = step;            Move(tx, ty, step+1);            /*如果上面Move()往下一步走不通，则回溯到这里            重置chessboard[tx][ty]为0，接着i++,又循环...... */            chessboard[tx][ty] = 0;        }    }     public static void main(String[] args) {        int i, j;        //初始化棋盘        for(i=0; i<8; i++){            for(j=0; j<8; j++){                chessboard[i][j] = 0;            }        }        System.out.println("请输入棋子开始位置（0-7）：");        Scanner sc = new Scanner(System.in);        int x = sc.nextInt();        int y = sc.nextInt();        //第一步不用比较，赋值第一步        chessboard[x][y] = 1;        Move(x, y, 2);          }}
• 应用
  • 背包问题
    • 问题描述： 一个背包的总容量为V,现在有N类物品,第i类物品的重量为weight[i],价值为value[i] 那么往该背包里装东西,怎样装才能使得最终包内物品的总价值最大？
    • 0-1背包
      • /**     * 0-1背包问题：每类物品最多只能装一次      * @param V 背包容量     * @param N 物品种类     * @param weight 物品重量     * @param value 物品价值     * @return     */    public static String ZeroOnePack(int V,int N,int[] weight,int[] value){         //初始化动态规划数组        int[][] dp = new int[N+1][V+1];        //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算        for(int i=1;i<N+1;i++){            for(int j=1;j<V+1;j++){                //如果第i件物品的重量大于背包容量j,则不装入背包                //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]                if(weight[i-1] > j)                    dp[i][j] = dp[i-1][j];                else                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);            }        }        //则容量为V的背包能够装入物品的最大值为        int maxValue = dp[N][V];        //逆推找出装入背包的所有商品的编号        int j=V;        String numStr="";        for(int i=N;i>0;i--){            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的            if(dp[i][j]>dp[i-1][j]){                numStr = i+" "+numStr;                j=j-weight[i-1];            }            if(j==0)                break;        }        return numStr;      } /**     * 0-1背包的优化解法     * 思路：     * 只用一个一维数组记录状态，dp[i]表示容量为i的背包所能装入物品的最大价值     * 用逆序来实现     */    public static int ZeroOnePack2(int V,int N,int[] weight,int[] value){        //动态规划        int[] dp = new int[V+1];        for(int i=1;i<N+1;i++){            //逆序实现            for(int j=V;j>=weight[i-1];j--){                dp[j] = Math.max(dp[j-weight[i-1]]+value[i-1],dp[j]);            }        }        return dp[V];           }
    • 完全背包
      • /**     * 第二类背包：完全背包，每类物品可以无限次装进包内     * 思路分析：     * 01背包问题是在前一个子问题（i-1种物品）的基础上来解决当前问题（i种物品），     * 向i-1种物品时的背包添加第i种物品；而完全背包问题是在解决当前问题（i种物品）     * 向i种物品时的背包添加第i种物品。     * 推公式计算时，f[i][y] = max{f[i-1][y], (f[i][y-weight[i]]+value[i])}，     * 注意这里当考虑放入一个物品 i 时应当考虑还可能继续放入 i，     * 因此这里是f[i][y-weight[i]]+value[i], 而不是f[i-1][y-weight[i]]+value[i]。     * @param V     * @param N     * @param weight     * @param value     * @return     */    public static String completePack(int V,int N,int[] weight,int[] value){        //初始化动态规划数组        int[][] dp = new int[N+1][V+1];        //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算        for(int i=1;i<N+1;i++){            for(int j=1;j<V+1;j++){                //如果第i件物品的重量大于背包容量j,则不装入背包                //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]                if(weight[i-1] > j)                    dp[i][j] = dp[i-1][j];                else                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weight[i-1]]+value[i-1]);            }        }        //则容量为V的背包能够装入物品的最大值为        int maxValue = dp[N][V];        int j=V;        String numStr="";        for(int i=N;i>0;i--){            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的            while(dp[i][j]>dp[i-1][j]){                numStr = i+" "+numStr;                j=j-weight[i-1];            }            if(j==0)                break;        }        return numStr;    }    /**     * 完全背包的第二种解法     * 思路：     * 只用一个一维数组记录状态，dp[i]表示容量为i的背包所能装入物品的最大价值     * 用顺序来实现     */    public static int completePack2(int V,int N,int[] weight,int[] value){         //动态规划        int[] dp = new int[V+1];        for(int i=1;i<N+1;i++){            //顺序实现            for(int j=weight[i-1];j<V+1;j++){                dp[j] = Math.max(dp[j-weight[i-1]]+value[i-1],dp[j]);            }        }        return dp[V];    }
    • 多重背包
      • /**     * 第三类背包：多重背包     * 每类物品都有个数限制，第i类物品最多可以装num[i]次      * @param args     */    public static int manyPack(int V,int N,int[] weight,int[] value,int[] num){        //初始化动态规划数组        int[][] dp = new int[N+1][V+1];        //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算        for(int i=1;i<N+1;i++){            for(int j=1;j<V+1;j++){                //如果第i件物品的重量大于背包容量j,则不装入背包                //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]                if(weight[i-1] > j)                    dp[i][j] = dp[i-1][j];                else{                    //考虑物品的件数限制                    int maxV = Math.min(num[i-1],j/weight[i-1]);                    for(int k=0;k<maxV+1;k++){                        dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-k*weight[i-1]]+k*value[i-1]);                    }                }            }        }        /*//则容量为V的背包能够装入物品的最大值为        int maxValue = dp[N][V];        int j=V;        String numStr="";        for(int i=N;i>0;i--){            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的            while(dp[i][j]>dp[i-1][j]){                numStr = i+" "+numStr;                j=j-weight[i-1];            }            if(j==0)                break;        }*/        return dp[N][V];    }
  • 迷宫问题
    • import java.util.*; public class Maze { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 输入参数 测试：4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 int n = sc.nextInt(); int m = sc.nextInt(); int p = sc.nextInt(); int[][] mi = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { mi[i][j] = sc.nextInt(); } } flag = new boolean[n][m]; List result = new ArrayList<>(); List tempList = new ArrayList<>(); // 调用计算方法，传入参数。获得result. cc(0, 0, mi, result, tempList); // 比较消耗精力最少的 int shortestNum = 0; List temp = (List) result.get(0); int min = (int) temp.get(temp.size() - 1); if (result.size() > 1) { for (int i = 1; i < result.size(); i++) { temp = (List) result.get(i); int tempMin = (int) temp.get(temp.size() - 1); if (tempMin < min) { min = tempMin; shortestNum = i; } } } List r = (List) result.get(shortestNum); r.remove(r.size() - 1); for (int i = 0; i < r.size(); i++) { System.out.print(r.get(i) + ","); } System.out.println("[0,3]"); } // 辅助计算的静态变量 static boolean[][] flag; // 为数组每个元素设置标志，避免重复到达某点造成多次计算或死循环 static int pu; // pUsed 每个成功到达出口的序列计算消耗的体力值 /* * 计算迷宫路径方法，主要使用递归调用每个节点的上下左右。上下左右节点又可以调用它的上下左右。 按消耗体力的数量及出口位置，优先顺序为上、右、下、左 * 传入参数，形参，即引用变量，地址不变，但指向的地址的值可以变化. */ public static void cc(int i, int j, int[][] mi, List result, List tempList) { // flag[i][j] = true; // //本题是考察最短路径，不同路径之间可以有一段重复。应使用list.contains()判断是否已包含此节点。 // 不管从哪条路到了出口，新建list存入结果，并保存pu if (i == 0 && j == mi[0].length - 1) { tempList.add(pu); result.add(new ArrayList<>(tempList)); tempList.remove((Integer) pu); } /* * up，从当前节点，考虑向上。如果上个节点有且没有使用，将上个节点作为参数传入方法。其他同理。 * 将当前节点信息(x,y)存入list，调用完方法移除！！！非常重要！！核心！！ * 因为不管是否到达出口，都说明已经探索完从这个节点伸出的路径了，应当移除，则可以从此节点上个节点继续探索。 * 到达了出口，已经保存了，该移除；没到，此路不通，移除。 根据需求应当使用stack，我使用不多就用list代替了。 */ if (i > 0 && mi[i - 1][j] == 1 && !tempList.contains("[" + (i - 1) + "," + j + "]")) { tempList.add("[" + i + "," + j + "]"); pu += 3; cc(i - 1, j, mi, result, tempList); tempList.remove("[" + i + "," + j + "]"); pu -= 3; } // right if (j < mi[0].length - 1 && mi[i][j + 1] == 1 && !tempList.contains("[" + i + "," + (j + 1) + "]")) { tempList.add("[" + i + "," + j + "]"); pu += 1; cc(i, j + 1, mi, result, tempList); tempList.remove("[" + i + "," + j + "]"); pu -= 1; } // down if (i < mi.length - 1 && mi[i + 1][j] == 1 && !tempList.contains("[" + (i + 1) + "," + j + "]")) { tempList.add("[" + i + "," + j + "]"); cc(i + 1, j, mi, result, tempList); tempList.remove("[" + i + "," + j + "]"); } // left if (j > 0 && mi[i][j - 1] == 1 && !tempList.contains("[" + i + "," + (j - 1) + "]")) { tempList.add("[" + i + "," + j + "]"); pu += 1; cc(i, j - 1, mi, result, tempList); tempList.remove("[" + i + "," + j + "]"); pu -= 1; } }}
    • 染色
      • 一般的简单迷宫问题，类似于能否出去。可以使用“染色”的思路，一个节点被染红之后传给相邻的节点，最后如果出口节点也被染红，那么可以出去。从代码实现上看，传入当前节点的信息，每次方法开始，判断是否为出口。是就可以提前退出，不是则继续向下执行。建立迷宫大小的静态boolean数组，标识每个节点是否已被染色，避免死循环。将本节点染色，判断是否有上下左右节点，有且未被染色，则调用本方法并传入将该节点信息（即递归调用）。方法调用完毕，判断出口是否已经被染色。
  • 八皇后
    • 回溯法
      • 回溯法是一种不断试探且及时纠正错误的搜索方法，下面的求解过程采用回溯法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达一个新点，否则试探下一个方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。这里可以用一个栈来实现，每走一步，将该位置压入栈中，若该点无路可走，则出栈返回上一位置。
  • 五子棋程序
    • import java.awt.Color;import java.awt.Font;import java.awt.Graphics;import java.awt.Toolkit;import java.awt.event.MouseEvent;import java.awt.event.MouseListener;import java.awt.image.BufferedImage;import java.io.File;import java.io.IOException; import javax.imageio.ImageIO;import javax.swing.JFrame;import javax.swing.JOptionPane; public class FiveChessFrame extends JFrame implements MouseListener, Runnable { private static final long serialVersionUID = 1L; int width = Toolkit.getDefaultToolkit().getScreenSize().width; int hight = Toolkit.getDefaultToolkit().getScreenSize().height; // 背景图片 BufferedImage bjImage = null; // 保存棋子坐标 int x = 0; int y = 0; // 保存之前下过的棋子坐标 // 其中数据：0:表示这个点没有棋子 1：表示黑子 2：表示白子 int[][] allChess = new int[19][19]; // 标识当前是黑棋还是白旗下下一步 boolean isBlack = true; // 标识当前游戏是否可以继续 boolean canPlay = true; // 保存显示的提示信息 String message = "黑方先行"; // 保存最多拥有多少时间(秒) int maxTime = 0; // 做倒计时的线程类 Thread t = new Thread(this); // 保存黑方与白方的剩余时间 int blackTime = 0; int whiteTime = 0; // 保存双方剩余时间的显示信息 String blackMessage = "无限制"; String whiteMessage = "无限制"; @SuppressWarnings("deprecation") public FiveChessFrame() { this.setTitle("五子棋"); this.setSize(500, 500); this.setLocation((width - 500) / 2, (hight - 500) / 2); this.addMouseListener(this); // this.setResizable(false); this.setVisible(true); t.start(); t.suspend();// 线程挂起 // 刚打开的时候刷新屏幕,防止开始游戏时无法显示的问题 this.repaint(); this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); try { bjImage = ImageIO.read(new File("src/main/webapp/static/images/background.jpg")); } catch (IOException e) { e.printStackTrace(); } } @Override public void paint(Graphics g) { // 双缓存技术 防止屏幕闪烁 但不知道为什么，使用双缓存技术以后，效果特不好，所以没用，如果使用的话，下面的 g 改为 g2 就可以了 // BufferedImage bi=new // BufferedImage(500,500,BufferedImage.TYPE_INT_ARGB); // Graphics g2=bi.createGraphics(); g.drawImage(bjImage, 0, 20, this); g.setFont(new Font("黑体", Font.BOLD, 20)); g.drawString("游戏信息：" + message, 120, 60); g.setFont(new Font("宋体", 0, 14)); g.drawString("黑方时间：" + blackMessage, 30, 470); g.drawString("白方时间：" + whiteMessage, 260, 470); // 绘制棋盘 for (int i = 0; i < 19; i++) { g.drawLine(10, 70 + 20 * i, 370, 70 + 20 * i); g.drawLine(10 + 20 * i, 70, 10 + 20 * i, 430); } // 标注小圆点位 g.fillOval(68, 128, 4, 4); g.fillOval(308, 128, 4, 4); g.fillOval(308, 368, 4, 4); g.fillOval(68, 368, 4, 4); g.fillOval(188, 128, 4, 4); g.fillOval(68, 248, 4, 4); g.fillOval(188, 368, 4, 4); g.fillOval(188, 248, 4, 4); g.fillOval(308, 248, 4, 4); // //绘制棋子 // x=(x-10)/20*20+10; //是为了取得交叉点的坐标 // y=(y-70)/20*20+70; // //黑子 // g.fillOval(x-7, y-7, 14, 14); // //白子 // g.setColor(Color.BLACK); // g.fillOval(x-7, y-7, 14, 14); // g.setColor(Color.BLACK); // g.drawOval(x-7, y-7, 14, 14); // 输出数组中所有数值 // 绘制全部棋子 for (int i = 0; i < 19; i++) { for (int j = 0; j < 19; j++) { if (allChess[i][j] == 1) { // 黑子 int tempX = i * 20 + 10; int tempY = j * 20 + 70; g.fillOval(tempX - 7, tempY - 7, 14, 14); } if (allChess[i][j] == 2) { // 白子 int tempX = i * 20 + 10; int tempY = j * 20 + 70; g.setColor(Color.WHITE); g.fillOval(tempX - 7, tempY - 7, 14, 14); g.setColor(Color.BLACK); g.drawOval(tempX - 7, tempY - 7, 14, 14); } } } } @Override public void mouseClicked(MouseEvent e) { } private boolean checkWin() { boolean flag = false; // 保存共有多少相同颜色棋子相连 int count = 1; // 判断横向 特点：allChess[x][y]中y值相同 int color = allChess[x][y]; // 判断横向 count = this.checkCount(1, 0, color); if (count >= 5) { flag = true; } else { // 判断纵向 count = this.checkCount(0, 1, color); if (count >= 5) { flag = true; } else { // 判断右上左下 count = this.checkCount(1, -1, color); if (count >= 5) { flag = true; } else { // 判断左下右上 count = this.checkCount(1, 1, color); if (count >= 5) { flag = true; } } } } return flag; } // 判断棋子连接数量 private int checkCount(int xChange, int yChange, int color) { int count = 1; int tempX = xChange; int tempY = yChange; while (x + xChange >= 0 && x + xChange <= 18 && y + yChange >= 0 && y + yChange <= 18 && color == allChess[x + xChange][y + yChange]) { count++; if (xChange != 0) { xChange++; } if (yChange != 0) { if (yChange > 0) { yChange++; } else { yChange--; } } } xChange = tempX; yChange = tempY; while (x - xChange >= 0 && x - xChange <= 18 && y - yChange >= 0 && y - yChange <= 18 && color == allChess[x - xChange][y - yChange]) { count++; if (xChange != 0) { xChange++; } if (yChange != 0) { if (yChange > 0) { yChange++; } else { yChange--; } } } return count; } @Override public void mouseEntered(MouseEvent arg0) { } @Override public void mouseExited(MouseEvent arg0) { } @SuppressWarnings("deprecation") @Override public void mousePressed(MouseEvent e) { if (canPlay == true) { x = e.getX(); y = e.getY(); if (x >= 10 && x <= 370 && y >= 70 && y <= 430) { // System.out.println("在棋盘范围内："+x+"--"+y); x = (x - 10) / 20; // 是为了取得交叉点的坐标 y = (y - 70) / 20; if (allChess[x][y] == 0) { // 判断当前要下的是什么棋子 if (isBlack == true) { allChess[x][y] = 1; isBlack = false; message = "轮到白方"; } else { allChess[x][y] = 2; isBlack = true; message = "轮到黑方"; } // 判断这个棋子是否和其他棋子连成5个 boolean winFlag = this.checkWin(); if (winFlag == true) { JOptionPane.showMessageDialog(this, "游戏结束," + (allChess[x][y] == 1 ? "黑方" : "白方") + "获胜!"); canPlay = false; } } else { JOptionPane.showMessageDialog(this, "当前位子已经有棋子，请重新落子！！！"); } this.repaint(); } } // 点击 开始游戏 按钮 if (e.getX() >= 400 && e.getX() <= 470 && e.getY() >= 70 && e.getY() <= 100) { int result = JOptionPane.showConfirmDialog(this, "是否重新开始游戏？"); if (result == 0) { // 现在重新开始游戏 // 重新开始所要做的操作：1)把棋盘清空,allChess数组中全部数据归0； // 2)游戏相关信息显示初始化 // 3)将下一步下棋改为黑方 for (int i = 0; i < 19; i++) { for (int j = 0; j < 19; j++) { allChess[i][j] = 0; } } // 另一种方式 allChess=new int[19][19] message = "黑方先行"; isBlack = true; blackTime = maxTime; whiteTime = maxTime; if (maxTime > 0) { blackMessage = maxTime / 3600 + ":" + (maxTime / 60 - maxTime / 3600 * 60) + ":" + (maxTime - maxTime / 60 * 60); whiteMessage = maxTime / 3600 + ":" + (maxTime / 60 - maxTime / 3600 * 60) + ":" + (maxTime - maxTime / 60 * 60); t.resume(); } else { blackMessage = "无限制"; whiteMessage = "无限制"; } this.repaint();// 如果不重新调用，则界面不会刷新 } } // 点击 游戏设置 按钮 if (e.getX() >= 400 && e.getX() <= 470 && e.getY() >= 120 && e.getY() <= 150) { String input = JOptionPane.showInputDialog("请输入游戏的最多时间(单位：分钟)，如果输入0 ，表示没有时间限制"); try { maxTime = Integer.parseInt(input) * 60; if (maxTime < 0) { JOptionPane.showMessageDialog(this, "请正确提示信息，不允许输入负数"); } if (maxTime == 0) { int result = JOptionPane.showConfirmDialog(this, "设置完成，是否重新开始游戏？"); if (result == 0) { // 现在重新开始游戏 // 重新开始所要做的操作：1)把棋盘清空,allChess数组中全部数据归0； // 2)游戏相关信息显示初始化 // 3)将下一步下棋改为黑方 for (int i = 0; i < 19; i++) { for (int j = 0; j < 19; j++) { allChess[i][j] = 0; } } // 另一种方式 allChess=new int[19][19] message = "黑方先行"; isBlack = true; blackTime = maxTime; whiteTime = maxTime; blackMessage = "无限制"; whiteMessage = "无限制"; this.repaint();// 如果不重新调用，则界面不会刷新 } } if (maxTime > 0) { int result = JOptionPane.showConfirmDialog(this, "设置完成，是否重新开始游戏？"); if (result == 0) { // 现在重新开始游戏 // 重新开始所要做的操作：1)把棋盘清空,allChess数组中全部数据归0； // 2)游戏相关信息显示初始化 // 3)将下一步下棋改为黑方 for (int i = 0; i < 19; i++) { for (int j = 0; j < 19; j++) { allChess[i][j] = 0; } } // 另一种方式 allChess=new int[19][19] message = "黑方先行"; isBlack = true; blackTime = maxTime; whiteTime = maxTime; blackMessage = maxTime / 3600 + ":" + (maxTime / 60 - maxTime / 3600 * 60) + ":" + (maxTime - maxTime / 60 * 60); whiteMessage = maxTime / 3600 + ":" + (maxTime / 60 - maxTime / 3600 * 60) + ":" + (maxTime - maxTime / 60 * 60); t.resume(); this.repaint();// 如果不重新调用，则界面不会刷新 } } } catch (NumberFormatException e1) { JOptionPane.showMessageDialog(this, "请正确提示信息"); } } // 点击 游戏说明 按钮 if (e.getX() >= 400 && e.getX() <= 470 && e.getY() >= 170 && e.getY() <= 200) { JOptionPane.showMessageDialog(this, "这是一个五子棋游戏程序，黑白双方轮流下棋，当某一方连到五子时，游戏结束。"); } // 点击 认输 按钮 if (e.getX() >= 400 && e.getX() <= 470 && e.getY() >= 270 && e.getY() <= 300) { int result = JOptionPane.showConfirmDialog(this, "是否确定认输？"); if (result == 0) { if (isBlack) { JOptionPane.showMessageDialog(this, "黑方方已经认输，游戏结束!!!"); } else { JOptionPane.showMessageDialog(this, "白方方已经认输，游戏结束!!!"); } canPlay = false; } } // 点击 关于 按钮 if (e.getX() >= 400 && e.getX() <= 470 && e.getY() >= 320 && e.getY() <= 350) { JOptionPane.showMessageDialog(this, "本游戏由菜鸟阿洁制作，有相关问题，可以联系本人QQ：474280917。"); } // 点击 退出 按钮 if (e.getX() >= 400 && e.getX() <= 470 && e.getY() >= 370 && e.getY() <= 400) { JOptionPane.showMessageDialog(this, "游戏退出"); System.exit(0); } } @Override public void mouseReleased(MouseEvent arg0) { } @Override public void run() { // 判断是否有时间限制 if (maxTime > 0) { while (true) { if (isBlack) { blackTime--; if (blackTime == 0) { JOptionPane.showMessageDialog(this, "黑方超时，游戏结束!"); } } else { whiteTime--; if (whiteTime == 0) { JOptionPane.showMessageDialog(this, "白方超时，游戏结束!"); } } blackMessage = blackTime / 3600 + ":" + (blackTime / 60 - blackTime / 3600 * 60) + ":" + (blackTime - blackTime / 60 * 60); whiteMessage = whiteTime / 3600 + ":" + (whiteTime / 60 - whiteTime / 3600 * 60) + ":" + (whiteTime - whiteTime / 60 * 60); this.repaint(); try { Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } } } } public static void main(String[] args) { @SuppressWarnings("unused") FiveChessFrame mf = new FiveChessFrame(); } }
    • 二维数组+算法
    • 二维数组+稀疏数组+算法
  • 约瑟夫问题
    • 模拟法
      • 单向环形链表
        • /** * 环链表，每次删除第m个元素 */ public static int lastRemaining(int n, int m) { if (n < 1 || m < 1) { return -1; } List<Integer> tmp = new LinkedList<>(); for (int i = 0; i < n; i++) { tmp.add(i+1); } int idx = -1; while (tmp.size() > 1) { idx = (idx + m) % tmp.size(); tmp.remove(idx); idx--; } return tmp.get(0); }
    • 递归法
      • /** * 递归方式 */ private static StringBuffer numbers = new StringBuffer(); private static void cycleCal(List<Integer> list, int num, int m) { int len = list.size(); if (len > 1) { //i仅代表索引，每一次循环就是list从1开始报数，报数为m的人出列 for (int i = 0; i < len; i++) { if (num == m) { numbers.append(list.get(i) + ","); list.remove(i); //注意集合的大小的改变，所以要改变索引 i--; len = list.size(); //count和i要同步 num = 0; } num++; } cycleCal(list, num, m); } else { numbers.append(list.get(0)); } }
    • 迭代法
      • 数组
        • /** * 数组解决约瑟夫环问题 * @param personNumber 人数 * @param number 数的数 */ public static void ysfcount(int personNumber, int number) { // 1.把人放到数组中,数据结构 int[] persons = new int[personNumber]; for (int i = 0; i < personNumber; i++) { persons[i] = i + 1; } // 2.算法  int index = 0; int dunNumbers = 0;// 记录蹲下人数的数 int duns = 0;// 记录蹲下人的个数 while (duns != personNumber) { // 有人没有蹲下 // 1.判读当前位置是否是蹲下 if (persons[index % persons.length] == 0) { // 蹲下,继续数数 dunNumbers++; index++; } else { // 2.没有蹲下,判读数的数是否是number的数 if ((index + 1 - dunNumbers) % number == 0) { // 是 // 打印该位置 System.out.println(persons[index % persons.length]); // 用0标识蹲下 persons[index % persons.length] = 0; // 蹲下的人数++ duns++; // 继续数数 index++; } else { // 否 // 继续数数 index++; } } } }
      • 队列
        • /** * 队列解决约瑟夫环问题 * @param personNumber 人数 * @param number 数的数 * @param m 从第几个开始数 */ public static void countQueue(int personNumber,  int m, int number) { // 1.把人放到队列中 Queue<Integer> persons = new LinkedList<Integer>(); for (int i = 0; i < personNumber; i++) { persons.add(i + 1); } // 2.算法 int counts = m-1;// 计数器 while (!persons.isEmpty()) { // 1.出队列 Integer person = persons.poll(); // 2.计数器++ counts++; // 3.判断 if (counts % number == 0) { // 是,打印 System.out.println(person); } else { // 不是,继续入队列 persons.add(person); } } }
    • 公式法
      • /* * 令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]。 递推公式： *  f[1]=0;  *  f[i]=(f[i-1]+m)%i;(i>1) */ public static int lastRemainingIII(int n, int m) { if (n < 1 || m < 1) { return -1; } int last = 0; for (int i = 2; i <= n; i++) { last = (last + m) % i; } return last+1; }
  • 修路问题
    • 加权值最小生成树+普里姆算法
      • public class SpanningTree { int[][] matrix;// 矩阵 int MAX_WEIGHT = Integer.MAX_VALUE; int size;// 顶点个数 /** * 普里姆算法实现最小生成树：先初始化拿到第一个顶点相关联的权值元素放到数组中－》找到其中权值最小的顶点下标－》再根据该下标，将该下标顶点相关联的权值加入到数组中－》循环遍历处理 */ public void prim() { int[] tempWeight = new int[size];// 临时存放顶点权值的数组，每次循环都要从中获取到最小权值和顶点下标 int minWeight;// 最小权值 int minId;// 最小权值顶点 int sum = 0;// 权值总和 //先初始化将第一行的顶点权值存放到临时权值数组中 for (int i = 0; i < size; i++) { tempWeight[i] = matrix[0][i]; } System.out.print("从顶点0开始查找"); for (int i = 1; i < size; i++) { //每次循环都找出临时顶点权值的最小的权值 minWeight = MAX_WEIGHT; minId = 0; for (int j = 1; j < size; j++) { if (tempWeight[j] > 0 && tempWeight[j] < minWeight) { minWeight = tempWeight[j]; minId = j; } } //找到目标顶点minId,他的权值为minweight。 System.out.print("找到顶点:" + minId + " 权值为：" + minWeight); sum += minWeight; //根据找到的顶点minid，将这一行的所有相关联的顶点权值添加到临时权值数组中 tempWeight[minId] = 0; for (int j = 1; j < size; j++) { if (tempWeight[j] != 0 && matrix[minId][j] < tempWeight[j]) { tempWeight[j] = matrix[minId][j]; } } } System.out.print("最小权值总和为：" + sum); } private void createGraph(int index) { size = index; matrix = new int[index][index]; int[] a0 = { 0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT }; int[] a1 = { 10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12 }; int[] a2 = { MAX_WEIGHT, MAX_WEIGHT, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8 }; int[] a3 = { MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, 24, 16, 21 }; int[] a4 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT }; int[] a5 = { 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT }; int[] a6 = { MAX_WEIGHT, 16, MAX_WEIGHT, 24, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT }; int[] a7 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT }; int[] a8 = { MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0 }; matrix[0] = a0; matrix[1] = a1; matrix[2] = a2; matrix[3] = a3; matrix[4] = a4; matrix[5] = a5; matrix[6] = a6; matrix[7] = a7; matrix[8] = a8; } public static void main(String[] args) { SpanningTree graph = new SpanningTree(); graph.createGraph(9); graph.prim(); }}
  • 最短路径问题
    • 图+弗洛伊德算法
    • 图+迪杰斯塔拉算法
  • 汉诺塔
    • 分治算法/递归
      • public class FZSFProblem {     public static void main(String[] args) {        solve(3);    }     public static void solve(int n) {        // 已知条件n个圆盘和A、B、C三根石柱        hanoi(n, "A", "B", "C");    }     /**     * 若要让第n个圆盘成功从A移动到C，需要让前n-1个圆盘先从A移动到B，然后让第n个圆盘从A移动到C，     * 最后让第n-1个圆盘从B移动到C，至于如何将前n-1个圆盘从A移动到B或者从A移动到C，仅仅是和父问     * 题相同的子问题，采用父问题的解决方案即可。     */    private static void hanoi(int n, String a, String b, String c) {        if (n == 1) {            // 只有一个圆盘时直接从A石柱移动到C石柱            move(n, a, c);        } else {            // 将前n-1个圆盘从石柱A移动到石柱B            hanoi(n - 1, a, c, b);            // 将第n号圆盘从石柱A移动到石柱C            move(n, a, c);            // 将前n-1个圆盘从石柱B移动到石柱C            hanoi(n - 1, b, a, c);        }    }     private static void move(int n, String i, String j) {        System.out.println("第" + n + "个圆盘，" + "从" + i + "移动到" + j);    } }
    • 迭代
      • package com.liuzhen.ex2; import java.util.Scanner; public class Hanoi { //迭代法，找规律，盘子的具体移动路径与盘子的总个数的奇偶性以及盘子标号的奇偶性有关，而且移动的路径是固定又循环的。    public static void noRecursionHanoi(int n){        if(n<=0){            throw new IllegalArgumentException("n must be >=1");        }        char[] hanoiPlate = new char[n];   //记录n个盘子所在的汉诺塔(hanoiPlate[1]='A'意味着第二个盘子现在在A上)        char[][] next = new char [2][3];   //盘子下次会移动到的盘子的可能性分类        int[] index = new int[n];         //根据奇偶性将盘子分为两类        for(int i=0;i<n;i=i+2){            index[i]=0;        }        for(int i=1;i<n;i=i+2){            index[i]=1;        }         //一开始所有盘子都在A上        for(int i=0;i<n;i++){            hanoiPlate[i]='A';        }         //n的奇偶性对移动方式的影响        if(n%2==0){            //数组下标为偶数的盘子移动目的塔，注意上面示例的标号为（1），其数组下标为0            next[0][0]='B';            next[0][1]='C';            next[0][2]='A';            //数组下标为奇数的盘子移动目的塔            next[1][0]='C';            next[1][1]='A';            next[1][2]='B';        }        else        {            //数组下标为偶数的盘子移动目的塔，注意上面示例的标号为（1），其数组下标为0            next[0][0]='C';            next[0][1]='A';            next[0][2]='B';            //数组下标为奇数的盘子移动目的塔            next[1][0]='B';            next[1][1]='C';            next[1][2]='A';        }         //开始移动        for(int i=1;i<(1<<n);i++){                  //总共要执行2^n-1(1<<n-1)步移动            int m=0;                                //m代表第m块盘子hanoiPlate[m]             //根据步骤数i来判断移动哪块盘子以及如何移动            for(int j=i;j>0;j=j/2){                if(j%2!=0){    //此步骤光看代码代码有点抽象，建议手动写一下n = 2时的具体移动路径的j、m值变化                    System.out.println("("+(m+1)+")"+hanoiPlate[m]+"->"+next[index[m]][hanoiPlate[m]-'A']);                    hanoiPlate[m]=next[index[m]][hanoiPlate[m]-'A'];                    break;                           //移动盘子后则退出这层循环                }                m++;            }        }    }         //使用递归法求解含有n个不同大小盘子的汉诺塔移动路径，参数n为盘子数，把A塔上盘子全部移动到C塔上，B为过渡塔    public static void recursionHanoi(int n,char A,char B,char C){        if(n == 1){            System.out.print(A+"——>"+C+"\n");            }        else{            recursionHanoi(n-1,A,C,B);         //使用递归先把A塔最上面的n-1个盘子移动到B塔上，C为过渡塔            System.out.print(A+"——>"+C+"\n");       //把A塔中底下最大的圆盘，移动到C塔上            recursionHanoi(n-1,B,A,C);         //使用递归把B塔上n-1个盘子移动到C塔上，A为过渡塔        }    }         public static void main(String[] args){        System.out.println("请输入盘子总数n:");        Scanner in = new Scanner(System.in);        int n = in.nextInt();            recursionHanoi(n,'A','B','C');            System.out.println("非递归法结果：");        noRecursionHanoi(n);            System.out.println();        }}