数据结构面试题和常用算法（3）

分治算法

1. 汉诺塔问题

看下面的分析

• 刚开始的时候是图一（这里以三个盘子为例子，这种就是看透本质，和把大象放冰箱分几步一样）
• 图二是中间状态
• 图三是最终状态
  其实就是看把一号柱子的a b 盘子移动到二号柱子。之后把一号柱子的c移动到到三号柱子，再把二号柱子的a b 盘子移动到三号柱子就好
  
  图一
  
  图二
  
  图三
  一次类推 如果有n个盘子 就有下面的三个步骤

1. 一号柱子 上的前n-1个盘子移动到二号柱子，。借助三号柱子
2. 将一号柱子上的第n个盘子移动到三号柱子
3. 将二号柱子的n-1个盘子移动到三号柱子。借助一号柱子
   分治大法好。分治大法秒。分治大法棒的呱呱叫，看到这个之后，在想想把大象放到冰箱的步骤。差不多

package fenzhi;

/**
 * @program: jdk8Test
 * @description: 汉诺塔
 * @author: liuchen
 * @create: 2020-03-27 13:55
 **/
public class HanNoTail {
    public static void main(String[] args) {
        demo1(5, 'A', 'B', 'C');
    }

    /**
     *
     * @param num   表示一共有多少盘子
     * @param a     起点
     * @param b     过渡盘子
     * @param c     终点
     */
    public static void demo1(int num, char a, char b, char c) {
        //如果是第一个盘子， 直接从a ----->  c
        if (num == 1) {
            System.out.println("第" + num + "盘子: " + a + " -----> " + c);

        } else {
            //将n-1个盘子从a 到 b  借助与c    a起点 b终点  c过渡
            demo1(num - 1, a, c, b);

            //将第n个盘子从a 到 c
            System.out.println("第" + num + "盘子: " + a + " -----> " + c);

            //将n-1盘子从b移动到c  借助与a   b起点 c终点 a过渡
            demo1(num - 1, b, a, c);

        }


    }
}

字符串匹配算法

1. 暴力匹配

package fenzhi;

/**
 * @program: jdk8Test
 * @description: 汉诺塔
 * @author: liuchen
 * @create: 2020-03-27 13:55
 **/
public class HanNoTail {
    public static void main(String[] args) {
        int i = baoliString("zaqwsxcde", "wsx");
        System.out.println(i);


    }
   public static int baoliString(String str1, String str2) {
       char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int i = 0; // s1的下标
        int j = 0; // s2的下标
        while (i < s1.length && j < s2.length) {
            //匹配到
            if (s1[i] == s2[j]) {
                //匹配到之后 i和j都往后移动
                i++;
                j++;
            } else {
                //没有匹配到。j为0。i回到i的下一个位置
                i = i - j + 1;
                j = 0;
            }
            //s2字符串是不是已经找完
            if (j == s2.length) {
                //返回下标 s2字符串相对于s1的下标
                return i - j;
            }

        }
        return -1;
    }
}

2.kmp算法

大牛的博客
尚硅谷 韩顺平老师 – b站
相比暴力算法 这个算法能求出一个最优的子串，有一个字符对照表(部分匹配表)，这就就能避免重复比较

package fenzhi;

import java.util.Arrays;

/**
 * @program: jdk8Test
 * @description: 汉诺塔
 * @author: liuchen
 * @create: 2020-03-27 13:55
 **/
public class HanNoTail {
    public static void main(String[] args) {
        String str1 = "ZAQWSXCDE";
        String str2 = "CDE";
        int[] table = buFenTable(str2);
        int i = kmpSearch(str1, str2, table);
        System.out.println(i);


    }
	   //KMP算法
    public static int kmpSearch(String str, String str2, int[] table) {

        int j = 0;//表示子串的指针
        for (int i = 0; i < str.length(); i++) {

            //KMP算法核心
            while (j > 0 && str.charAt(i) != str2.charAt(j)) {
                j = table[j - 1];
            }

            //如果相等还是一样的++；
            if (str.charAt(i) == str2.charAt(j)) {
                j++;
            }

            if (j == str2.length()) {
                //表示已经找到了，返回i对应的下标
                return i - j + 1;
            }
        }

        return -1;
    }

    //计算部分匹配表
    public static int[] buFenTable(String str) {
        //定义一个数组 next 也就是部分匹配表
        int[] next = new int[str.length()];
        next[0] = 0; //上来的第一个字符前面肯定是没有匹配的.
        int j = 0; //表示相对于i的前一个位置
        for (int i = 1; i < str.length(); i++) {//这里从1开始表示第一个不比较，因为没有必要

            //KMP算法的核心
            //下面的if显示的能匹配到的情况这里的while就是匹配不到的情况
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                //两个不相等 应该怎么做?
                j = next[j - 1];//回溯
            }

            //每次能匹配到，就给j++；
            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            next[i] = j;
        }

        return next;
    }
}