数据结构与算法 - 程序员常用的 10 中算法

public class BinarySearchNoRecur {

    public static void main(String[] args) {

        int[] arr = {1,2,3,4,5};

        int i = searchErFen(arr,3);

        System.out.println(i);

    }

    /**

     * 二分查找的非递归实现

     * @param arr 目标数组，数组有序且升序排序

     * @param value 要查找的目标值

     * @return 返回目标值的下表

     */

    public static int searchErFen(int[] arr,int value){

        // 起始指针

        int left = 0;

        // 末尾指针

        int last = arr.length;

        // 循环

        while(left <= last){

            // 每次执行折半处理 计算出 数列的中间位置进行查找目标值

            int mid = (left + last) / 2;

            // 判断中间的值是否小于目标值

            if(arr[mid] < value)

                // 如果中间值小于目标值则将指针向前移动

                last = mid - 1;

            // 判断中间值是否大于目标值

            else if(arr[mid] > value)

                // 如果中间值大于了目标值则将指针向后移动

                left = mid + 1;

            else

                // 两者都没有执行则说明找到了目标值直接返回

                return mid;

        }

        // 如果没有找到则返回 - 1

        return -1;

    }

}

@SuppressWarnings("all")

public class Hanoitower {

    public static void main(String[] args) {

        hanoiTower(5,'A','B','C');

    }

    // 汉诺塔移动的方法

    public static void hanoiTower(int num, char a, char b, char c) {

        // 如果只有一个盘

        if (num == 1)

            System.out.println("第1个盘从 " + a + " -->> " + c);

        else {

            // 如果我们有 n >= 2 情况，我们总是可以看做是两个盘

            //1. 最下边的一个盘

            //2. 上面的所有盘

            // 一，先吧，最上面的所有盘 A->B, 移动过程中会使用到 c

            hanoiTower(num - 1, a, c, b);

            // 二，吧最下面的盘 A -> C

            System.out.println("第" + num + "个盘从 " + a + " -->> " + c);

            // 三，吧 B 塔的所有盘 从 B -> C, 移动过程使用到 A 塔

            hanoiTower(num - 1, b, a, c);

        }

    }

}

@SuppressWarnings("all")

public class KnapsackProblem {

    public static void main(String[] args) {

        int[] w = {1, 4, 3};// 物品的重量

        int[] val = {1500, 3000, 2000};// 物品的价格

        int m = 4;// 背包的容量

        int n = val.length;// 物品的个数

        //n+1 因为第一行中都是 0 不算第一行，m+1 因为第一列都是 0 不算第一列

        //v [i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值

        int[][] v = new int[n + 1][m + 1];

        // 为了记录放入商品的 情况，我们定义一个二维数组

        int[][] path = new int[n + 1][m + 1];

        // 初始化第一行和第一列，这里在本程序中，可以不去处理，因为默认是 0

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

            v[i][0] = 0;// 将第一列设置为 0

        for (int i = 0; i < v[0].length; i++)

            v[0][i] = 0;// 将第一行设置 0

        // 根据前面得到的公式来动态规划处理 i, 从 1 开始因为第一行不做处理

        for (int i = 1; i < v.length; i++)//i +1 第一行不做处理

            for (int j = 1; j < v[0].length; j++) {//j +1 第一列不做处理

                // 公式

                if (w[i - 1] > j)// 因为程序是 i, 是从 1 开始的，因此原来公式中的 w [i] 修改成 w [i - 1]

                    v[i][j] = v[i - 1][j];

                else {

                    // 说明：

                    // 因为 i 从 1 开始的，因此公式需要调整成

                    //v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);

                    // 为了记录商品存放到背包的情况，不能直接的使用上面的公式，需要使用 if-else 来体现公式

                    if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {

                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];

                        // 吧当前的情况记录到 path 数组中

                        path[i][j] = 1;

                    } else

                        v[i][j] = v[i - 1][j];

                }

            }

        // 输出查看情况

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

            for (int j = 0; j < v[i].length; j++)

                System.out.print(v[i][j] + " ");

            System.out.println();

        }

        System.out.println("================================");

        // 输出最后我们是放入的哪些商品

        //

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

//            for (int j = 0; j < path[i].length; j++)

//                if (path[i][j] == 1)

//                    System.out.printf ("第 % d 个商品放入到背包", i);

//            System.out.println();

//        }

        int i = path.length - 1;// 行的最大下标

        int j = path[0].length - 1;// 列的最大小标

        while(i > 0 && j > 0){// 从 path 的最后开始找

            if(path[i][j] == 1){

                System.out.printf("第>> %d <<个商品放入到背包\n", i);

                j -= w[i - 1];

            }

            i --;

        }

    }

}

@SuppressWarnings("all")

public class ViolenceMath {

    public static void main(String[] args) {

        String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";

        String str2 = "尚硅谷你尚硅你";

        int index = violenceMath(str1,str2);

        System.out.println("index = "+index);

    }

    // 暴力匹配算法实现

    public static int violenceMath(String str1, String str2) {

        char[] s1 = str1.toCharArray();

        char[] s2 = str2.toCharArray();

        int s1Len = s1.length;

        int s2Len = s2.length;

        int i = 0;//i 索引指向 s1

        int j = 0;//j 索引指向 s2

        while (i < s1Len && j < s2Len) {// 保证匹配时，不越界

            if (s1[i] == s2[j]) {// 匹配成功

                i++;

                j++;

            } else {// 没有匹配成功

                i = i - (j - 1);

                j = 0;

            }

        }

        // 判断是否匹配成功

        if(j == s2Len)

            return i - j;

        else

            return -1;

    }

}

@SuppressWarnings("all")

public class KMPAlgorithm {

    public static void main(String[] args) {

        String str1 = "BBC ABCDAB ABCDABCDABDE";

        String str2 = "ABCDABCD";

        int[] next = kmpNext(str2);//[0, 0, 0, 0, 1, 2, 0]

        System.out.println(Arrays.toString(next));

        int index = kmpSearch(str1, str2, next);

        System.out.println("index = " + index);//index = 15

    }

    /**

     * kmp 搜索算法

     *

     * @param str1 原字符串

     * @param str2 子串

     * @param next 部分匹配表，子串对应的部分匹配表

     * @return 如果是 -1 说明没有匹配到，否则返回第一个匹配到的位置

     */

    public static int kmpSearch(String str1, String str2, int[] next) {

        // 遍历

        for (int i = 0, j = 0; i < str1.length(); i++) {

            // 需要处理 str1.charAt (i) != str2.charAt (j)，去调整 j 的大小

            //Kmp 算法核心点

            while (j > 0 && str1.charAt(i) != str2.charAt(j))

                j = next[j - 1];

            if (str1.charAt(i) == str2.charAt(j))

                j++;

            if (j == str2.length())

                return i - j + 1;

        }

        return -1;

    }

    /**

     * 获取到一个字符串 (子串) 的部分匹配值表

     *

     * @param dest

     * @return

     */

    public static int[] kmpNext(String dest) {

        // 创建一个 next 数组保存部分匹配值

        int[] next = new int[dest.length()];

        next[0] = 0; // 如果字符串长度为 1, 部分匹配值就是 0

        for (int i = 1, j = 0; i < dest.length(); i++) {

            // 当 dest.charAt (i) == dest.charAt (j) 我们需要从 next [j - 1] 获取新的 j

            // 直到我们发现有 dest.charAt (i) == dest.charAt (j) 成立才退出

            // 这是 kmp 算法的核心点

            while (j > 0 && dest.charAt(i) != dest.charAt(j))

                // 回溯

                j = next[j - 1];

            // 当 dest.charAt (i) == dest.charAt (j) 满足时，部分匹配值就是 +1

            if (dest.charAt(i) == dest.charAt(j))

                j++;

            next[i] = j;

        }

        return next;

    }

}

@SuppressWarnings("all")

public class GreedyAlgorithm {

    public static void main(String[] args) {

        // 创建广播电台，放入到 HashMap

        HashMap<String, HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();

        // 将各个电台放入到 broadcasts

        HashSet<String> hashSet1 = new HashSet<>();

        hashSet1.add("北京");

        hashSet1.add("上海");

        hashSet1.add("天津");

        HashSet<String> hashSet2 = new HashSet<>();

        hashSet2.add("广州");

        hashSet2.add("上海");

        hashSet2.add("深圳");

        HashSet<String> hashSet3 = new HashSet<>();

        hashSet3.add("成都");

        hashSet3.add("上海");

        hashSet3.add("杭州");

        HashSet<String> hashSet4 = new HashSet<>();

        hashSet4.add("上海");

        hashSet4.add("天津");

        HashSet<String> hashSet5 = new HashSet<>();

        hashSet5.add("杭州");

        hashSet5.add("大连");

        // 将所有电台加入到 Map 集合中

        broadcasts.put("K1", hashSet1);

        broadcasts.put("K2", hashSet2);

        broadcasts.put("K3", hashSet3);

        broadcasts.put("K4", hashSet4);

        broadcasts.put("K5", hashSet5);

        HashSet<String> allAreas = new HashSet<>();

        Collections.addAll(allAreas, "北京", "上海", "天津", "广州", "深圳", "成都", "杭州", "大连");

        // 创建一个 ArrayList 存放选择的电台集合

        ArrayList<String> selects = new ArrayList<>();

        // 定义临时集合保存在遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集

        HashSet<String> tempSet = new HashSet<>();

        // 定义 maxKey 保存在一次遍历过程中，能够覆盖的最多位覆盖的地区对应的电台的 Key

        String maxKey = null;

        // 如果 maxKey 不为 null 则加入到 selects 中

        while (allAreas.size() != 0) {// 如果 allAreas 不为 0, 则表示还没有覆盖到所有的地区

            maxKey = null;

            for (String key : broadcasts.keySet()) {

                tempSet.clear();

                HashSet<String> areas = broadcasts.get(key);

                tempSet.addAll(areas);

                // 求出 tempSet 和 allAreas 集合的交集，交集会赋给 tempSet

                tempSet.retainAll(allAreas);

                // 如果当前集合包含的未覆盖地区的数量比 maxKey 指向的集合未覆盖的地区还要多

                // 就需要重置 maxKey

                if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size()))

                    maxKey = key;

            }

            //maxKey != null，就应该将 maxKey 加入 selects

            if (maxKey != null) {

                selects.add(maxKey);

                // 将 maxKey 指向的广播电台覆盖的地区，从 allAreas 去掉

                allAreas.removeAll(broadcasts.get(maxKey));

            }

        }

        System.out.println("得到的选择结果是: " + selects);//[k1,k2,k3,k5]

    }

}

@SuppressWarnings("all")

public class PrimAlgorithm {

    public static void main(String[] args) {

        // 测试图是否创建成功

        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

        int vertx = data.length;

        // 邻接矩阵的关系使用二维数组表示，10000 这个大数，表示两个点不连通

        int[][] weight = <!--swig0-->;

        // 创建 MGraph 对象

        MGraph mGraph = new MGraph(vertx);

        // 创建一个 MiniTree 对象

        MiniTree minTree = new MiniTree();

        minTree.createGraph(mGraph, vertx, data, weight);

        // 输出

        minTree.showGraph(mGraph);

        // 测试普利姆算法

        minTree.prim(mGraph,0);

    }

}

// 创建最小生成树

@SuppressWarnings("all")

class MiniTree {

    /**

     * 创建图的邻接矩阵

     *

     * @param graph  图对象

     * @param vertx  图对应的顶点个数

     * @param data   图的各个顶点的值

     * @param weight 图的邻接矩阵

     */

    public void createGraph(MGraph graph, int vertx, char[] data, int[][] weight) {

        int i, j;

        for (i = 0; i < vertx; i++) {// 顶点

            graph.data[i] = data[i];

            for (j = 0; j < vertx; j++)

                graph.weight[i][j] = weight[i][j];

        }

    }

    /**

     * 显示图的邻接矩阵

     *

     * @param graph

     */

    public void showGraph(MGraph graph) {

        for (int[] itemp : graph.weight)

            System.out.println(Arrays.toString(itemp));

    }

    /**

     * 编写 prim 算法，得到最小生成树

     *

     * @param graph 图

     * @param v     表示从图的第几个顶点开始生成 'A' -> 0 , 'B' -> 1 ...

     */

    public void prim(MGraph graph, int v) {

        // 标记节点 (顶点) 是否被访问过

        int[] visited = new int[graph.vertx];

        //visited [] 默认元素的值都是 0，表示没有访问过，Java 中默认为 0 所以不能特意进行次操作

        //for(int i = 0;i < graph.vertx;i ++)

        //visited[i] = 0;

        // 把当前节点标记为已访问

        visited[v] = 1;

        //h1,h2 记录两个顶点的下标

        int h1 = -1;

        int h2 = -1;

        // 将 miniweight 初始成一个大数，后面在遍历过程中，会被替换

        int miniWeight = 10000;

        // 因为有 graph.vertx 顶点，普利姆算法结束后，有 graph.vertx - 1 边

        for (int k = 1; k < graph.vertx; k++) {

            // 遍历当前顶点可连通的所有的顶点

            // 确定每一次生成的子图，和哪个节点的距离最近

            for (int i = 0; i < graph.vertx; i++)//i 节点表示被访问过的节点

                for (int j = 0; j < graph.vertx; j++)//j 节点表示没有被访问过的节点

                    if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < miniWeight) {

                        // 替换 miniweight (寻找已经访问过的节点和为访问过的节点间的权值最小的边)

                        miniWeight = graph.weight[i][j];

                        h1 = i;

                        h2 = j;

                    }

            // 找到一条边是最小

            System.out.println("边 <" + graph.data[h1] + "," + graph.data[h2] + "> 权值: " + miniWeight);

            // 将当前这个节点标记为已访问过

            visited[h2] = 1;

            // 将 miniWeight 重新设置为 最大值

            miniWeight = 10000;

        }

    }

}

@SuppressWarnings("all")

class MGraph {

    int vertx;// 表示图的节点个数

    char[] data;// 存放节点数据

    int[][] weight;// 存放边，就是邻接矩阵

    public MGraph(int vertx) {

        this.vertx = vertx;

        data = new char[vertx];

        weight = new int[vertx][vertx];

    }

}

@SuppressWarnings("all")

public class Kruskal {

    private int edgeNum;// 边的个数

    private char[] vertexs;// 顶点数目

    private int[][] matrix;// 邻接矩阵

    private static int INF = Integer.MAX_VALUE;// 使用 INF 表示两个顶点不能连通

    // 构造器

    public Kruskal(char[] vertexs, int[][] matrix) {

        // 初始化定点数和边的个数

        int vlen = vertexs.length;

        // 初始化顶点

        this.vertexs = new char[vlen];

        // 拷贝的方式，使得构造函数中的 vertexs 和成员字段 vertexs 互不影响

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

            this.vertexs[i] = vertexs[i];

        // 初始化边

        this.matrix = new int[vlen][vlen];

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

            for (int j = 0; j < vertexs.length; j++)

                this.matrix[i][j] = matrix[i][j];

        // 统计边的条数

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

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

                if (this.matrix[i][j] != INF)

                    edgeNum++;

    }

    public void kruskal() {

        int index = 0;// 表示最后结果数组的索引

        int[] ends = new int[edgeNum];// 用于保存 "已有最小生成树" 中的每个顶点在最小生成树中的终点

        // 创建结果数组，保存最后的最小生成树

        EData[] rets = new EData[edgeNum];

        // 获取图中 所有的边的集合，一共有 12 边

        EData[] edges = getEdges();

        System.out.println("图的边的集合= " + Arrays.toString(edges) + " 共 " + edges.length);//12

        // 按照边的权值大小进行排序 (从小到大)

        sortEdges(edges);

        // 遍历 edges 数组，将边添加到最小生成树中时，判断是准备加入的边是否形成了回路，如果没有，就加入 rets，否则不能加入

        for (int i = 0; i < edgeNum; i++) {

            // 获取到第 i 条边的第一个顶点

            int p1 = getPosition(edges[i].start);

            // 获取到第 i 条边的第二个顶点

            int p2 = getPosition(edges[i].end);

            // 获取 p1 这个顶点在已有最小生成树中的终点

            int m = getEnd(ends, p1);

            // 获取 p2 这个顶点在已有最小生成树中的终点

            int n = getEnd(ends, p2);

            // 是否构成回路

            if (m != n){

                // 设置 m 在 "已有最小生成树" 中的终点

                ends[m] = n;

                // 有一条边加入到 rets 数组中

                rets[index ++] = edges[i];

            }

        }

        System.out.println("----------------最小生成树为----------------");

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

            System.out.println(rets[i]);

    }

    // 打印邻接矩阵

    public void print() {

        System.out.println("邻接矩阵为\n");

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

            for (int j = 0; j < vertexs.length; j++)

                System.out.printf("%12d", matrix[i][j]);

            System.out.println();

        }

    }

    // 对边进行排序处理，冒泡排序处理

    private void sortEdges(EData[] edges) {

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

            for (int j = 0; j < edges.length - 1 - i; j++)

                if (edges[j].weight > edges[j + 1].weight) {

                    EData temp = edges[j];

                    edges[j] = edges[j + 1];

                    edges[j + 1] = temp;

                }

    }

    /**

     * @param ch 顶点的值，比如 'A','B'

     * @return 返回 ch 顶点对应的下标，如果找不到返回 - 1

     */

    private int getPosition(char ch) {

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

            if (vertexs[i] == ch)

                return i;

        return -1;

    }

    /**

     * comment: 获取图中边，放到 EData [] 数组中，后面我们需要遍历该数组

     * 是通过 matrix 邻接矩阵来获取

     * EData 形式 [['A','B',12],['B','F',7],...]

     *

     * @return

     */

    private EData[] getEdges() {

        int index = 0;

        EData[] edges = new EData[edgeNum];

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

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

                if (matrix[i][j] != INF)

                    edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);

        return edges;

    }

    /**

     * comment: 获取下标为 i 的顶点的终点，用于后面判断两个顶点的终点是否相同

     *

     * @param ends 数组就是记录了各个顶点对应的终点是哪个，ends 数组是在遍历过程中，逐步形成的 (不是一次形成的)

     * @param i    表示传入的顶点对应的下标

     * @return 返回的就是 下标为 i 的这个顶点对应的终点的下标

     */

    private int getEnd(int[] ends, int i) {

        while (ends[i] != 0)

            i = ends[i];

        return i;

    }

    public static void main(String[] args) {

        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

        // 克鲁斯卡尔算法的邻接矩阵

        int matrix[][] = {

                /*A*//*B*//*C*//*D*//*E*//*F*//*G*/

                /*A*/ {0, 12, INF, INF, INF, 16, 14},

                /*B*/ {12, 0, 10, INF, INF, 7, INF},

                /*C*/ {INF, 10, 0, 3, 5, 6, INF},

                /*D*/ {INF, INF, 3, 0, 4, INF, INF},

                /*E*/ {INF, INF, 5, 4, 0, 2, 8},

                /*F*/ {16, 7, 6, INF, 2, 0, 9},

                /*G*/ {14, INF, INF, INF, 8, 9, 0}};

        // 大家可以在去测试其它的邻接矩阵，结果都可以得到最小生成树.

        // 创建对象

        Kruskal krusKal = new Kruskal(vertexs, matrix);

        krusKal.print();

        krusKal.kruskal();

    }

}

@SuppressWarnings("all")

// 创建一个类 EData, 它的对象实力就表示一条边

class EData {

    char start;// 边的一个点

    char end;// 边的另外一个点

    int weight;// 边的权值

    public EData(char start, char end, int weight) {

        this.start = start;

        this.end = end;

        this.weight = weight;

    }

    @Override

    public String toString() {

        return "EData{" +

                 "<" + start +

                " , " + end + ">" +

                " , weight=" + weight +

                '}';

    }

}