Java数据结构和算法

赫夫曼编码

赫夫曼编码是一种编码方式，是赫夫曼树在通信中的经典应用之一。广泛用于数据文件压缩，压缩率通常在20%~90%之间。赫夫曼编码是可变字长编码的一种，称之为最佳编码。

编码原理：举例传输的字符串为：i like like like java do you like a java

1）统计各个字符出现的次数：d : 1，y : 1，u : 1，j : 2，v : 2，o : 2，l : 4，k : 4，e : 4，i : 5，a : 5，空格 : 9

2）按照上面字符出现的次数构建一棵赫夫曼树。次数作为权值。

3）根据赫夫曼树，给各个字符规定编码（前缀编码），向左的路径为0，向右的为1；则编码为：

o：1000，u：10010，d：100110，y：100111，i：101，a：110，k：1110，e：1111，j：0000，v：0001

l：001，空格：01；并且不会出现多义性。

4）于是原字符串经过编码后变为：

101 01 001 101 1110 1111 01 001 101 1110 1111 01 001 101 1110 1111 01 0000 110 0001 110 01

100110 1000 100111 10010 01 001 101 1110 1111 01 110 0000 110 0001 110

5）原来使用定长编码长度为359，而使用赫夫曼编码为133，压缩率为62.9%。此编码满足前缀编码，即字符的编码都不能是其他字符编码的前缀，不会造成匹配的多义性。

6）注意：如果有相同权值的数据，进行排序（不同的排序方法）时，会造成赫夫曼树的不同，但WPL都一致。

/
 * 编码节点
 *
 * @author lzlg
 * 2020/1/11 20:58
 */
public class CodeNode<E> implements Comparable<CodeNode<E>> {
    E data;         // 数据
    int weight;     // 权值
    CodeNode<E> left;
    CodeNode<E> right;

    public CodeNode(E data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    public CodeNode(CodeNode<E> left, E data, int weight, CodeNode<E> right) {
        this.data = data;
        this.weight = weight;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "CodeNode{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    // 前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    @Override
    public int compareTo(CodeNode<E> o) {
        return this.weight - o.weight;
    }
}

import java.util.*;
import java.util.stream.Collectors;

/
 * 赫夫曼编码
 *
 * @author lzlg
 * 2020/1/11 20:58
 */
public class HuffmanCode {
    /
     * 编码方法
     */
    public static byte[] code(String content) {
        // 获取字符串的byte数组
        byte[] bytes = content.getBytes();
        // 转成集合
        List<CodeNode<Byte>> nodes = toNodes(bytes);
        // 转换成赫夫曼树
        CodeNode<Byte> huffmanTree = toTree(nodes);
        // 生成赫夫曼编码规则map
        Map<Byte, String> codeRuleMap = RuleMapData.codeRuleMap(huffmanTree);
        // 按照编码规则将原来byte数组转成新的二进制字符串
        StringBuilder huffmanStr = toHuffmanString(bytes, codeRuleMap);
        System.out.println("编码后的二进制字符串为：" + huffmanStr);
        // 将新的二进制字符串转换为byte数组，每8位一个
        return toCodeBytes(huffmanStr);
    }

    /
     * 转成node集合
     */
    private static List<CodeNode<Byte>> toNodes(byte[] bytes) {
        // 获取字符的出现次数，然后构建node集合
        Map<Byte, Integer> map = new HashMap<>();
        for (byte b : bytes) {
            map.merge(b, map.getOrDefault(b, 1), (k, v) -> v + 1);
        }

        // 转成集合
        return map.entrySet().stream()
                .map(v -> new CodeNode<>(v.getKey(), v.getValue()))
                .collect(Collectors.toList());
    }

    /
     * 将新的二进制字符串转换为byte数组，每8位一个
     */
    private static byte[] toCodeBytes(StringBuilder sb) {
        int strLen = sb.length();
        int len = (strLen + 7) / 8;
        byte[] codeBytes = new byte[len];
        int index = 0;
        for (int i = 0; i < strLen; i += 8) {// 每8位截取一个
            String str;// 要截取的字符串
            if (i + 8 > strLen) {// 不足8位，则直接截取到最后
                str = sb.substring(i);
            } else {
                str = sb.substring(i, i + 8);
            }
            codeBytes[index] = (byte) Integer.parseInt(str, 2);// 转成byte
            index++;// 新数组的下标后移
        }
        return codeBytes;
    }

    /
     * 按照编码规则将原来byte数组转成新的二进制字符串
     */
    private static StringBuilder toHuffmanString(byte[] bytes, Map<Byte, String> codeRuleMap) {
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            sb.append(codeRuleMap.get(b));
        }
        return sb;
    }

    /
     * 将list转换成赫夫曼树
     */
    private static CodeNode<Byte> toTree(List<CodeNode<Byte>> nodes) {
        while (nodes.size() > 1) {
            // 排序
            Collections.sort(nodes);
            // 取出两个节点
            CodeNode<Byte> left = nodes.remove(0);
            CodeNode<Byte> right = nodes.remove(0);
            // 组成父节点
            CodeNode<Byte> parent = new CodeNode<>(left, null,
                    left.weight + right.weight, right);
            // 将父节点添加到集合中
            nodes.add(parent);
        }
        return nodes.get(0);
    }
}

import java.util.HashMap;
import java.util.Map;
/
 * 编码，解码规则map数据
 *
 * @author lzlg
 * 2020/1/11 23:46
 */
public class RuleMapData {

    private static Map<Byte, String> codeRuleMap;

    /
     * 生成赫夫曼编码规则map
     * 规定，左边路径为0，右边路径为1
     */
    public static Map<Byte, String> codeRuleMap(CodeNode<Byte> huffmanTree) {
        if (huffmanTree == null) {
            return null;
        } else {
            codeRuleMap = new HashMap<>();
            codeRuleMap(huffmanTree.left, "0", new StringBuilder(), codeRuleMap);
            codeRuleMap(huffmanTree.right, "1", new StringBuilder(), codeRuleMap);
            return codeRuleMap;
        }
    }

    private static void codeRuleMap(CodeNode<Byte> node, String code, StringBuilder sb, Map<Byte, String> ruleMap) {
        StringBuilder newBuilder = new StringBuilder(sb);
        newBuilder.append(code);
        if (node != null) {
            if (node.data == null) { // 没有数据的节点不是叶子节点
                codeRuleMap(node.left, "0", newBuilder, ruleMap);
                codeRuleMap(node.right, "1", newBuilder, ruleMap);
            } else {
                ruleMap.put(node.data, newBuilder.toString());
            }
        }
    }

    /
     * 获取解码规则数据
     */
    public static Map<String, Byte> decodeRuleMap() {
        if (codeRuleMap == null) {
            return null;
        } else {
            Map<String, Byte> decodeRuleMap = new HashMap<>();
            for (Map.Entry<Byte, String> entry : codeRuleMap.entrySet()) {
                decodeRuleMap.put(entry.getValue(), entry.getKey());
            }
            return decodeRuleMap;
        }
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
/
 * 赫夫曼解码
 *
 * @author lzlg
 * 2020/1/11 21:28
 */
public class HuffmanDecode {
    /
     * 解码方法
     */
    public static byte[] decode(byte[] codeBytes) {
        // 把编码后的byte数组转换成二进制字符串
        String binaryString = toBinaryString(codeBytes);
        System.out.println("解码后的二进制字符串为：" + binaryString);
        // 将二进制字符串根据解码规则map进行解码
        return decode(binaryString);
    }

    private static byte[] decode(String binaryString) {
        // 获取解码规则map
        Map<String, Byte> decodeRuleMap = RuleMapData.decodeRuleMap();
        // 记录byte数据list
        List<Byte> list = new ArrayList<>();
        int len = binaryString.length();
        for (int i = 0; i < len; ) {
            int count = 1;
            Byte b;
            while (true) { // 每次从string中取出字符，看是否能从解码规则中找到对应的byte
                String s = binaryString.substring(i, i + count);
                b = decodeRuleMap.get(s);
                if (b == null) {
                    count++;
                } else {
                    break;
                }
            }
            list.add(b);
            i += count;
        }
        return listToArray(list);
    }

    /
     * list转换成byte数组
     */
    private static byte[] listToArray(List<Byte> list) {
        byte[] sourceBytes = new byte[list.size()];
        for (int i = 0; i < sourceBytes.length; i++) {
            sourceBytes[i] = list.get(i);
        }
        return sourceBytes;
    }

    /
     * 把编码后的byte数组转换成二进制字符串
     */
    private static String toBinaryString(byte[] bytes) {
        int len = bytes.length;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < bytes.length; i++) {
            sb.append(toBinaryString(i < len - 1, bytes[i]));
        }
        return sb.toString();
    }

    /
     * 将byte转成字符串，flag表示是否补高位
     */
    private static String toBinaryString(boolean flag, byte b) {
        int temp = b;
        if (flag) {// 编码后的byte数组最后一位是直接截取的，不需要补高位
            temp |= 256;// 不补高位 b = 1 时，str = 1
        }
        String str = Integer.toBinaryString(temp);// int 4字节会转换成32位字符串
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }
}

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectOutputStream;
import java.util.Map;
/
 * 压缩文件
 *
 * @author lzlg
 * 2020/1/12 1:04
 */
public class ZipFile {
    /
     * 压缩文件
     */
    public static void zip(String filePath, String destPath) {
        // 读取文件到byte数组
        try (FileInputStream fis = new FileInputStream(filePath);
             ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(destPath))) {
            byte[] bytes = new byte[fis.available()];
            fis.read(bytes);
            // 进行赫夫曼编码
            byte[] codeBytes = HuffmanCode.code(bytes);
            Map<String, Byte> decodeRuleMap = RuleMapData.getDecodeRuleMap();
            oos.writeObject(codeBytes);
            oos.writeObject(decodeRuleMap);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        String filePath = "D:\\test_zip.png";
        String destPath = "D:\\test.zip";
        zip(filePath, destPath);
    }
}

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.util.Map;
/
 * 解压文件
 *
 * @author lzlg
 * 2020/1/12 1:04
 */
public class UnZipFile {
    public static void main(String[] args) {
        String filePath = "D:\\test.zip";
        String destPath = "D:\\test_hhah.png";
        unzip(filePath, destPath);
    }

    public static void unzip(String filePath, String destPath) {
        try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream(filePath));
             FileOutputStream fos = new FileOutputStream(destPath)) {
            byte[] codeBytes = (byte[]) ois.readObject();
            Map<String, Byte> decodeRuleMap = (Map<String, Byte>) ois.readObject();
            RuleMapData.setDecodeRuleMap(decodeRuleMap);
            byte[] bytes = HuffmanDecode.decode(codeBytes);
            fos.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

/
 * 二叉排序树
 *
 * @author lzlg
 * 2020/1/13 14:02
 */
public class BinarySortTree {

    private Node root;

    /
     * 二叉排序树的添加
     */
    public void add(int value) {
        if (root == null) {
            root = new Node(value);
        } else {
            root.add(new Node(value));
        }
    }

    /
     * 二叉排序树的中序遍历
     */
    public void infixList() {
        if (root == null) {
            System.out.println("二叉排序树为空，不能遍历");
        } else {
            root.infixOrder();
        }
    }

    /
     * 二叉排序树删除节点
     */
    public void delete(int value) {
        if (root == null) {
            System.out.println("二叉树为空，不能删除");
        } else {
            // 查找value的节点
            Node node = root.node(value);
            if (node == null) {
                System.out.println("没有查找到指定的节点，无法删除");
                return;
            }
            // 查找value节点的父节点
            Node parent = root.parent(value);

            // 情况有三种，1：当前节点是叶子节点，直接删除
            if (node.left == null && node.right == null) {
                if (parent == null) {// 如果只剩一个根节点
                    root = null;
                } else {
                    if (parent.left.value == value) {
                        parent.left = null;
                    } else {
                        parent.right = null;
                    }
                }
            } else if (node.left != null && node.right != null) {
                // 2.当前节点有左右子节点
                // 从左子树找到最大的值或从右子树查找最小的值（同时删除该值对应的节点）
                node.value = min(node.right);
            } else { // 3.当前节点只有一个子节点
                if (node.left != null) {
                    if (parent == null) { //防止只剩一个根节点和一个子节点的情况
                        root = node.left;
                    } else {
                        if (parent.left.value == value) {
                            parent.left = node.left;
                        } else {
                            parent.right = node.left;
                        }
                    }
                } else {
                    if (parent == null) {
                        root = node.right;
                    } else {
                        if (parent.left.value == value) {
                            parent.left = node.right;
                        } else {
                            parent.right = node.right;
                        }
                    }
                }
            }
        }
    }

    // 找到从当前节点下的最小节点的值，并删除
    private int min(Node node) {
        Node temp = node;
        while (temp.left != null) {
            temp = temp.left;
        }
        int value = temp.value;// 找到该节点的值
        delete(value);// 删除最小节点的值
        return value;
    }

    private static class Node {
        int value;
        Node left;
        Node right;

        private Node(int value) {
            this.value = value;
        }

        // 添加新节点
        private void add(Node node) {
            if (node == null) return;
            if (node.value < this.value) { // 新添加的节点值小于当前节点
                if (this.left == null) {// 添加到左子节点上
                    this.left = node;
                } else {
                    this.left.add(node);
                }
            } else {
                if (this.right == null) {
                    this.right = node;
                } else {
                    this.right.add(node);
                }
            }
        }

        // 中序遍历
        private void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right != null) {
                this.right.infixOrder();
            }
        }

        // 查找节点值是value的节点
        private Node node(int value) {
            if (this.value == value) {
                return this;
            }
            Node node = null;
            if (this.left != null && value < this.value) {
                // value小于当前节点，从左子节点查找
                node = this.left.node(value);
            }
            if (node != null) {// 如果查找到，直接返回，否则从右子节点查找
                return node;
            }
            if (this.right != null) {
                node = this.right.node(value);
            }
            return node;
        }

        // 查找节点的父节点
        private Node parent(int value) {
            if ((this.left != null && this.left.value == value) ||
                    (this.right != null && this.right.value == value)) {
                return this;
            }
            Node parent = null;
            if (this.left != null) {
                parent = this.left.parent(value);
            }
            if (parent != null) {
                return parent;
            }
            if (this.right != null) {
                parent = this.right.parent(value);
            }
            return parent;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("Node = ");
            if (this.left == null) {
                sb.append("null");
            } else {
                sb.append(this.left.value);
            }
            sb.append("_").append(this.value).append("_");
            if (this.right == null) {
                sb.append("null");
            } else {
                sb.append(this.right.value);
            }
            return sb.toString();
        }
    }
}

// 左子树的高度
private int leftHeight() {
    return left == null ? 0 : left.height();
}

// 右子树的高度
private int rightHeight() {
    return right == null ? 0 : right.height();
}

// 计算树的高度
private int height() {
    return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}

// 左旋转
private void leftRotate() {
    // 1.创建和当前节点值一样的新节点
    Node newNode = new Node(value);
    // 2.新节点的左子节点指向当前节点的左子节点
    newNode.left = left;
    // 3.新节点的右子节点指向当前节点的右子节点的左子节点
    newNode.right = right.left;
    // 4.将当前节点的右子节点的值赋值给当前节点
    value = right.value;
    // 5.当前节点的右子节点指向当前节点的右子节点的右子节点
    right = right.right;
    // 6.当前节点的左子节点指向新节点
    left = newNode;
}

// 右旋转
private void rightRotate() {
    // 1.创建和当前节点值一样的新节点
    Node newNode = new Node(value);
    // 2.新节点的右子节点指向当前节点的右子节点
    newNode.right = right;
    // 3.新节点的左子节点指向当前节点的左子节点的右子节点
    newNode.left = left.right;
    // 4.将当前节点的左子节点的值赋值给当前节点
    value = left.value;
    // 5.当前节点的左子节点指向当前节点的左子节点的左子节点
    left = left.left;
    // 6.当前节点的右子节点指向新节点
    right = newNode;
}

// 添加新节点
private void add(Node node) {
    if (node == null) return;
    if (node.value < this.value) { // 新添加的节点值小于当前节点
        if (this.left == null) {// 添加到左子节点上
            this.left = node;
        } else {
            this.left.add(node);
        }
    } else {
        if (this.right == null) {
            this.right = node;
        } else {
            this.right.add(node);
        }
    }

    // 添加时进行选择
    int leftHeight = leftHeight();
    int rightHeight = rightHeight();
    if (leftHeight + 1 < rightHeight) {// 如果左子树的高度 + 1 小于右子树的高度，进行左旋
        // 如果右子树的左子树高度大于右子树的高度，则先进行右旋
        if (right != null && right.leftHeight() > right.rightHeight()) {
            right.rightRotate();
        }
        leftRotate();
        return;
    }

    if (rightHeight + 1 < leftHeight) {// 如果右子树的高度 + 1 小于左子树的高度，进行右旋
        // 如果左子树的右子树高度大于左子树的高度，则先进行右旋
        if (left != null && left.rightHeight() > left.leftHeight()) {
            left.leftRotate();
        }
        rightRotate();
    }
}
// 测试方法
public static void main(String[] args) {
    BalanceBinaryTree tree = new BalanceBinaryTree();
    // 测试左旋
    //        int[] array = {4, 3, 6, 5, 7, 8};
    // 测试右旋
    //        int[] array = {10, 5, 11, 4, 6, 3};
    // 测试双旋转
    int[] array = {10, 5, 11, 4, 6, 7};
    for (int i = 0; i < array.length; i++) {
        tree.add(array[i]);
    }
    System.out.println("进行旋转的二叉树为：");
    tree.infixList();
    System.out.println("根节点为：" + tree.getRoot());
}

import java.util.ArrayList;
import java.util.List;

/
 * 图的简单实现
 *
 * @author lzlg
 * 2020/1/17 16:24
 */
public class SimpleGraph {
    // 存放顶点
    private List<String> vertexList;
    // 存放边
    private int[][] edges;
    // 边的数目
    private int edgeCount;

    public SimpleGraph(int n) {
        vertexList = new ArrayList<>(n);
        edges = new int[n][n];
    }

    // 添加顶点
    public void addVertex(String vertex) {
        if (vertexList.size() == edges.length) {
            throw new IllegalArgumentException("can not add more vertex, is full");
        }
        vertexList.add(vertex);
    }

    // 添加一条边，v1是第一个顶点的下标，v2是第二个顶点的下标，weight是边的权值
    public void addEdge(int v1, int v2, int weight) {
        outOfBoundCheck(v1, v2);
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        edgeCount++;
    }

    // 返回顶点的数量
    public int vertexCount() {
        return vertexList.size();
    }

    // 返回边的数量
    public int edgeCount() {
        return edgeCount;
    }

    // 根据下标获取顶点信息
    public String getVertex(int index) {
        return vertexList.get(index);
    }

    // 获取边的权值，v1是第一个顶点的下标，v2是第二个顶点的下标
    public int getWeight(int v1, int v2) {
        outOfBoundCheck(v1, v2);
        return edges[v1][v2];
    }

    private void outOfBoundCheck(int v1, int v2) {
        if (v1 < 0 || v1 > edges.length || v2 < 0 || v2 > edges.length) {
            throw new IndexOutOfBoundsException("out of max length");
        }
    }

    // 展示图的信息
    public void show() {
        int len = edges.length;
        for (String v : vertexList) {
            System.out.print("\t" + v);
        }
        System.out.println();
        for (int i = 0; i < len; i++) {
            System.out.print(vertexList.get(i));
            for (int j = 0; j < edges[i].length; j++) {
                System.out.print("\t" + edges[i][j]);
            }
            System.out.println();
        }
    }
}

/
 * @author lzlg
 * 2020/1/17 16:25
 */
public class Test {
    public static void main(String[] args) {
        SimpleGraph graph = createGraph();
    }

    private static SimpleGraph createGraph() {
        int n = 5;
        String[] vertexArray = {"A", "B", "C", "D", "E"};
        // 创建图
        SimpleGraph graph = new SimpleGraph(n);
        // 添加顶点信息
        for (String v : vertexArray) {
            graph.addVertex(v);
        }
        // 添加边信息
        // A
        graph.addEdge(0, 1, 1);
        graph.addEdge(0, 2, 1);
        // B
        graph.addEdge(1, 0, 1);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 1);
        graph.addEdge(1, 4, 1);
        // C
        graph.addEdge(2, 0, 1);
        graph.addEdge(2, 1, 1);
        // D
        graph.addEdge(3, 1, 1);
        // E
        graph.addEdge(4, 1, 1);

        graph.show();
        return graph;
    }
}

/
 * 获取下一个未访问过的节点
 * preVisited上一个已经访问过的节点下标
 * lastVisited最后一个已经访问过的节点下标
 */
private int getNext(int preVisited, int lastVisited) {
    int count = edges.length;
    for (int j = lastVisited + 1; j < count; j++) {
        if (edges[preVisited][j] > 0) {
            return j;
        }
    }
    return -1;
}

// 深度优先遍历
public void dfs() {
    int count = edges.length;
    // 用来标记顶点是否已访问过
    boolean[] visited = new boolean[count];
    for (int i = 0; i < count; i++) {
        int next = i;
        while (next != -1) {
            if (!visited[next]) {// 如果没有访问过
                System.out.print("-->" + getVertex(next));// 则进行访问
                visited[next] = true;// 标记已经访问过
                // 则寻找next节点后的第一个节点，深度优先遍历
                next = getNext(next, next);
            } else {// 如果已经访问过，则next为节点i对应的第二个节点
                next = getNext(i, next);
            }
        }
    }
}

public void bfs() {
    int count = edges.length;
    // 用来标记顶点是否已访问过
    boolean[] visited = new boolean[count];
    // 使用队列保存上一次遍历的节点信息
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < count; i++) {
        queue.offer(i);// 将当前节点的下标添加到队列中
        while (!queue.isEmpty()) {// 队列不为空，进行遍历
            int p = queue.poll(); // 取出要遍历的当前节点
            int next = p; // 记录要遍历的下个节点
            while (next != -1) {
                if (!visited[next]) {// 如果没有访问过，则进行访问
                    System.out.print("==>" + getVertex(next));
                    visited[next] = true;// 标记已访问过
                }
                // 获取下一个要访问的节点，广度优先遍历
                next = getNext(p, next);
                if (next != -1) {// 将把要访问的节点加入到队列中
                    queue.offer(next);
                }
            }
        }
    }
}

/
 * 二分查找算法
 *
 * @author lzlg
 * 2020/1/17 19:41
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {1, 3, 8, 9, 11, 16};
        int index = search(array, 10);
        System.out.println("index = " + index);
    }

    private static int search(int[] array, int target) {
        int l = 0;
        int r = array.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (target > array[mid]) {
                l = mid + 1;
            } else if (target < array[mid]) {
                r = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

/
 * 动态规划算法，背包问题
 *
 * @author lzlg
 * 2020/1/17 21:04
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] weight = {0, 1, 4, 3};// 物品的重量
        int[] value = {0, 1500, 3000, 2000};// 物品的价值
        int maxWeight = 4; // 背包的最大容量
        // 最大价值记录
        int[][] maxValue = new int[weight.length][maxWeight + 1];
        // 记录商品存放情况
        int[][] path = new int[weight.length][maxWeight + 1];

        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j < maxWeight + 1; j++) {
                if (weight[i] > j) {// 如果物品的重量大于当前容量
                    // 直接照搬上次的情况
                    maxValue[i][j] = maxValue[i - 1][j];
                } else {// 如果物品的重量不大于当前容量
                    // 上次的容量 和 最新的容量(物品当前的价值 + 减去当前物品重量的上一次最优)进行比较
                    int preValue = maxValue[i - 1][j];
                    int newValue = value[i] + maxValue[i - 1][j - weight[i]];
                    if (preValue > newValue) {
                        maxValue[i][j] = preValue;
                    } else {
                        path[i][j] = 1; // 记录最优解
                        maxValue[i][j] = newValue;
                    }
                }
            }
        }
        print(maxValue);
        System.out.println("++++++++++++++++++++++");
        System.out.println("找出最优解：");
        int i = path.length - 1;
        int j = path[0].length - 1;
        while (i > 0 && j > 0) {
            if (path[i][j] == 1) {
                System.out.printf("第%d的物品放入背包\n", i);
                j -= weight[i];
            }
            i--;
        }
    }

    private static void print(int[][] array) {
        for (int[] ints : array) {
            for (int i : ints) {
                System.out.printf("%10d", i);
            }
            System.out.println();
        }
    }
}

import java.util.Arrays;

/
 * 字符串匹配算法：KMP算法
 *
 * @author lzlg
 * 2020/1/28 14:08
 */
public class KMPMatch {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int[] next = next(str2);
        System.out.println(Arrays.toString(next));
        System.out.println(match(str1, str2));
    }

    /
     * kmp算法
     */
    private static int match(String str1, String str2) {
        // 获取模式串的部分匹配表
        int[] next = next(str2);
        int str1Len = str1.length();
        int str2Len = str2.length();
        int i = 0, j = 0;
        while (i < str1Len && j < str2Len) {
            if (j == -1 || str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        return j == str2Len ? i - j : -1;
    }

    /
     * 获取模式串的next数组
     */
    private static int[] next(String str) {
        char[] chars = str.toCharArray();
        int[] next = new int[chars.length];
        next[0] = -1;
        int i = 0, j = -1;
        int len = chars.length - 1;
        while (i < len) {
            if (j == -1 || chars[i] == chars[j]) {
                j++;
                i++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }
}

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/
 * 贪心算法：集合覆盖问题
 *
 * @author lzlg
 * 2020/1/28 17:30
 */
public class GreedyAlgorithm {
    public static void main(String[] args) {
        // 创建广播电台，放入到Map中
        Map<String, Set<String>> map = new HashMap<>();
        map.put("K1", Stream.of("北京", "上海", "天津").collect(Collectors.toSet()));
        map.put("K2", Stream.of("广州", "北京", "深圳").collect(Collectors.toSet()));
        map.put("K3", Stream.of("成都", "上海", "杭州").collect(Collectors.toSet()));
        map.put("K4", Stream.of("上海", "天津").collect(Collectors.toSet()));
        map.put("K5", Stream.of("杭州", "大连").collect(Collectors.toSet()));

        Set<String> allAreas = map.values().stream()
                .flatMap(Collection::stream).collect(Collectors.toSet());
        System.out.println("所有要覆盖的区域有：");
        System.out.println(allAreas);

        // selected存储选择的电台结果
        List<String> selected = new ArrayList<>();
        // 存储当前要覆盖的电台区域
        Set<String> temp = new HashSet<>();
        while (!allAreas.isEmpty()) {
            String maxKey = null; // 要存储的最大未覆盖区域的电台key
            for (Map.Entry<String, Set<String>> entry : map.entrySet()) {
                temp.clear();
                temp.addAll(entry.getValue());
                temp.retainAll(allAreas);
                if (temp.size() > 0 && (maxKey == null || temp.size() > map.get(maxKey).size())) {
                    maxKey = entry.getKey();
                }
            }
            // maxKey不为空，则证明找到了，则添加到selected中，并删除maxKey对应的电台覆盖区域（此时已经覆盖）
            if (maxKey != null) {
                selected.add(maxKey);
                allAreas.removeAll(map.get(maxKey));
            }
        }

        System.out.println("被选择的电台有：");
        System.out.println(selected);
    }
}

/
 * 普利姆算法
 *
 * @author lzlg
 * 2020/2/11 14:59
 */
public class PrimAlgorithm {

    private static final int MAX = 10000;

    public static void main(String[] args) {
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = {{MAX, 5, 7, MAX, MAX, MAX, 2},
                {5, MAX, MAX, 9, MAX, MAX, 3},
                {7, MAX, MAX, MAX, 8, MAX, MAX},
                {MAX, 9, MAX, MAX, MAX, 4, MAX},
                {MAX, MAX, 8, MAX, MAX, 5, 4},
                {MAX, MAX, MAX, 4, 5, MAX, 6},
                {2, 3, MAX, MAX, 4, 6, MAX}};
        Graph graph = new Graph(data, weight);
        graph.show();
        prim(graph);
    }

    /
     * 普利姆算法
     */
    private static void prim(Graph graph) {
        // 记录顶点 是否访问过
        boolean[] visited = new boolean[graph.nums];
        // 从第一个顶点开始访问，可从任意一个节点访问
        visited[0] = true;
        // v1，v2用来记录访问的两个顶点
        int v1 = -1;
        int v2 = -1;

        int max = MAX;

        for (int i = 1; i < graph.nums; i++) { // 循环次数为图的顶点数-1
            // j用来标记已访问的顶点信息
            for (int j = 0; j < graph.nums; j++) {
                // k用来标记未访问的顶点信息
                for (int k = 0; k < graph.nums; k++) {
                    if (visited[j] && !visited[k] && graph.weight[j][k] < max) {
                        max = graph.weight[j][k];
                        v1 = j;
                        v2 = k;
                    }
                }
            }
            System.out.println("边<" + graph.data[v1] + ", " + graph.data[v2]
                    + ">，权值：" + graph.weight[v1][v2]);
            // 下次循环重置max的值
            max = MAX;
            // 顶点v2标记已访问过
            visited[v2] = true;
        }
    }

    private static class Graph {
        int nums; // 顶点数量
        char[] data; // 顶点数据
        int[][] weight; // 邻接矩阵

        public Graph(char[] data, int[][] weight) {
            nums = data.length;
            this.data = new char[nums];
            for (int i = 0; i < nums; i++) {
                this.data[i] = data[i];
            }
            this.weight = new int[nums][nums];
            for (int i = 0; i < nums; i++) {
                for (int j = 0; j < nums; j++) {
                    this.weight[i][j] = weight[i][j];
                }
            }
        }

        public void show() {
            for (char v : data) {
                System.out.printf("%10s", v);
            }
            System.out.println();
            for (int i = 0; i < nums; i++) {
                System.out.print(data[i]);
                for (int j = 0; j < nums; j++) {
                    System.out.printf("%10d", weight[i][j]);
                }
                System.out.println();
            }
        }
    }
}

import java.util.Arrays;
/
 * 克鲁斯卡尔算法
 *
 * @author lzlg
 * 2020/2/11 15:42
 */
public class KruskalAlgorithm {
    // 表示顶点不能连通
    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = {{INF, 12, INF, INF, INF, 16, 14},
                {12, INF, 10, INF, INF, 7, INF},
                {INF, 10, INF, 3, 5, 6, INF},
                {INF, INF, 3, INF, 4, INF, INF},
                {INF, INF, 5, 4, INF, 2, 8},
                {16, 7, 6, INF, 2, INF, 9},
                {14, INF, INF, INF, 8, 9, INF}};

        Graph graph = new Graph(data, weight);
        graph.show();
        kruskal(graph);
    }

    /
     * 克鲁斯卡尔算法
     */
    private static void kruskal(Graph graph) {
        Edge[] result = new Edge[graph.nums - 1]; // 结果数组
        int index = 0; // 结果数组下标

        int[] ends = new int[graph.nums]; // 记录下标为i的顶点的终点下标

        Edge[] edges = graph.getEdges();
        Arrays.sort(edges); // 对边进行排序

        for (int i = 0; i < graph.edgeNums; i++) {
            Edge edge = edges[i];
            // 取出当前边的两个顶点的下标
            int p1 = graph.index(edge.v1);
            int p2 = graph.index(edge.v2);
            // 查询这两个顶点的终点
            int m = end(ends, p1);
            int n = end(ends, p2);
            // m != n 则不构成回路
            if (m != n) {
                result[index++] = edge;
                // 此时更新ends数组，让下标为m顶点的终点指向n
                ends[m] = n;
            }
        }

        System.out.println("最小生成树为：");
        for (Edge edge : result) {
            System.out.println(edge);
        }
    }

    /
     * 返回下标为i的顶点的终点的下标
     *
     * @param ends 记录顶点的终点的下标
     * @param i    下标为i的顶点
     */
    private static int end(int[] ends, int i) {
        while (ends[i] != 0) {
            i = ends[i];
        }
        return i;
    }

    /
     * 边对象，并按照权值排序
     */
    private static class Edge implements Comparable<Edge> {
        char v1; // 边的一个顶点
        char v2; // 边的另一个顶点
        int weight; // 权值

        public Edge(char v1, char v2, int weight) {
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "v1=" + v1 +
                    ", v2=" + v2 +
                    ", weight=" + weight +
                    '}';
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    private static class Graph {
        int nums; // 顶点数量
        int edgeNums; // 边的数量
        char[] data; // 顶点数据
        int[][] weight; // 邻接矩阵

        public Graph(char[] data, int[][] weight) {
            nums = data.length;
            this.data = new char[nums];
            for (int i = 0; i < nums; i++) {
                this.data[i] = data[i];
            }
            this.weight = new int[nums][nums];
            for (int i = 0; i < nums; i++) {
                for (int j = 0; j < nums; j++) {
                    this.weight[i][j] = weight[i][j];
                }
            }
            // 统计边的数量
            for (int i = 0; i < nums; i++) {
                for (int j = i + 1; j < nums; j++) {
                    if (weight[i][j] != INF) {
                        edgeNums++;
                    }
                }
            }
        }

        // 顶点对应的下标
        public int index(char c) {
            for (int i = 0; i < nums; i++) {
                if (c == data[i]) return i;
            }
            return -1;
        }

        // 获取图对应的边的数组
        public Edge[] getEdges() {
            Edge[] edges = new Edge[edgeNums];
            int index = 0;
            for (int i = 0; i < nums; i++) {
                for (int j = i + 1; j < nums; j++) {
                    if (weight[i][j] != INF) {
                        edges[index++] = new Edge(data[i], data[j], weight[i][j]);
                    }
                }
            }
            return edges;
        }

        public void show() {
            for (char v : data) {
                System.out.printf("%15s", v);
            }
            System.out.println();
            for (int i = 0; i < nums; i++) {
                System.out.print(data[i]);
                for (int j = 0; j < nums; j++) {
                    System.out.printf("%15d", weight[i][j]);
                }
                System.out.println();
            }
        }
    }
}

import java.util.Arrays;
/
 * 迪杰斯特拉算法--最短路径算法
 *
 * @author lzlg
 * 2020/2/11 17:26
 */
public class DijkstraAlgorithm {

    private static final int MAX = 65535;

    public static void main(String[] args) {
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = {{MAX, 5, 7, MAX, MAX, MAX, 2},
                {5, MAX, MAX, 9, MAX, MAX, 3},
                {7, MAX, MAX, MAX, 8, MAX, MAX},
                {MAX, 9, MAX, MAX, MAX, 4, MAX},
                {MAX, MAX, 8, MAX, MAX, 5, 4},
                {MAX, MAX, MAX, 4, 5, MAX, 6},
                {2, 3, MAX, MAX, 4, 6, MAX}};
        Graph graph = new Graph(data, weight);
        graph.show();
        graph.dijkstra(6);
    }

    private static class Graph {
        int nums;
        char[] data;
        int[][] weight;
        // 记录顶点是否访问过
        boolean[] visited;
        // 记录起始顶点到其他顶点的距离
        int[] dis;
        // 记录顶点的前驱节点
        int[] pre;

        public Graph(char[] data, int[][] weight) {
            this.nums = data.length;
            this.data = data;
            this.weight = weight;

            this.visited = new boolean[nums];
            this.dis = new int[nums];
            Arrays.fill(dis, MAX);
            this.pre = new int[nums];
        }

        /
         * 迪杰斯特拉算法
         *
         * @param index 出发顶点的下标
         */
        public void dijkstra(int index) {
            if (index < 0 || index >= nums) {
                throw new IndexOutOfBoundsException();
            }
            // 初始化起始顶点的数据
            visited[index] = true;
            dis[index] = 0;
            update(index);

            for (int i = 1; i < nums; i++) {
                index = next();
                update(index);
            }
            // 显示结果
            showResult();
        }

        // 更新下标为index的节点访问后的数据
        public void update(int index) {
            for (int i = 0; i < nums; i++) {
                // 从起始顶点到出发顶点的权值和出发顶点到新节点的权值之和
                // 是否大于从起始顶点到新节点的权值之和，且没访问过
                int len = dis[index] + weight[index][i];
                if (!visited[i] && len < dis[i]) {
                    dis[i] = len;
                    pre[i] = index;
                }
            }
        }

        // 获取下一个可访问路径最短的顶点
        public int next() {
            int min = MAX, index = 0;
            for (int i = 0; i < nums; i++) {
                if (!visited[i] && dis[i] < min) {
                    min = dis[i];
                    index = i;
                }
            }
            // 注意更新该节点已经被访问过
            visited[index] = true;
            return index;
        }

        private void showResult() {
            for (int i = 0; i < nums; i++) {
                System.out.print(data[i] + "[visited=" + visited[i] + "] ");
            }
            System.out.println();
            for (int i = 0; i < nums; i++) {
                System.out.print(data[i] + "[pre=" + pre[i] + "] ");
            }
            System.out.println();
            for (int i = 0; i < nums; i++) {
                System.out.print(data[i] + "[dis=" + dis[i] + "] ");
            }
        }

        public void show() {
            for (char v : data) {
                System.out.printf("%10s", v);
            }
            System.out.println();
            for (int i = 0; i < nums; i++) {
                System.out.print(data[i]);
                for (int j = 0; j < nums; j++) {
                    System.out.printf("%10d", weight[i][j]);
                }
                System.out.println();
            }
        }
    }
}

/
 * 弗洛伊德算法--求出所有顶点最短距离
 *
 * @author lzlg
 * 2020/2/11 19:38
 */
public class FloydAlgorithm {
    private static final int MAX = 65535;

    public static void main(String[] args) {
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = {{0, 5, 7, MAX, MAX, MAX, 2},
                {5, 0, MAX, 9, MAX, MAX, 3},
                {7, MAX, 0, MAX, 8, MAX, MAX},
                {MAX, 9, MAX, 0, MAX, 4, MAX},
                {MAX, MAX, 8, MAX, 0, 5, 4},
                {MAX, MAX, MAX, 4, 5, 0, 6},
                {2, 3, MAX, MAX, 4, 6, 0}};
        Graph graph = new Graph(data, weight);
        graph.floyd();
        graph.show();

    }

    private static class Graph {
        int nums;
        char[] data;
        int[][] weight;
        // 前驱节点信息
        char[][] preChar;

        public Graph(char[] data, int[][] weight) {
            this.nums = data.length;
            this.data = data;
            this.weight = weight;
            this.preChar = new char[nums][nums];
            for (int i = 0; i < nums; i++) {
                for (int j = 0; j < nums; j++) {
                    preChar[i][j] = data[i];
                }
            }
        }

        public void floyd() {
            // k：中间节点
            for (int k = 0; k < nums; k++) {
                // i：出发节点
                for (int i = 0; i < nums; i++) {
                    // j：终点节点
                    for (int j = 0; j < nums; j++) {
                        int len = weight[i][k] + weight[k][j];
                        if (len < weight[i][j]) {
                            weight[i][j] = len;
                            preChar[i][j] = preChar[k][j];
                        }
                    }
                }
            }
        }

        public void show() {
            for (int i = 0; i < nums; i++) {
                for (int j = 0; j < nums; j++) {
                    System.out.print(preChar[i][j] + " ");
                }
                System.out.println();
                for (int j = 0; j < nums; j++) {
                    System.out.print(data[i] + "到" + data[j] + "的最短距离为：" + weight[i][j] + "  ");
                }
                System.out.println();
                System.out.println();
            }
        }
    }
}

import java.awt.*;
import java.util.ArrayList;
import java.util.List;

/
 * 马踏棋盘算法--骑士周游问题
 *
 * @author lzlg
 * 2020/2/11 20:22
 */
public class HorseChessboard {
    private static final int X = 8;// 棋盘的列数
    private static final int Y = 8;// 棋盘的行数
    private static boolean[] visited = new boolean[X * Y]; // 记录棋盘的各个位置是否已经访问过
    private static boolean finished = false; // 记录是否已经完成

    public static void main(String[] args) {
        horseTread(new Point(0, 0));
    }

    public static void horseTread(Point point) {
        System.out.println("start~~~~~~~~~~~~");
        int[][] checkerboard = new int[X][Y];
        long start = System.currentTimeMillis();
        horseTread(checkerboard, point.y, point.x, 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时：" + (end - start) + "毫秒");
        showCheckerboard(checkerboard);
    }

    private static void showCheckerboard(int[][] checkerboard) {
        for (int i = 0; i < X; i++) {
            for (int j = 0; j < Y; j++) {
                System.out.printf("%5d", checkerboard[i][j]);
            }
            System.out.println();
        }
    }

    /
     * 马踏棋盘
     *
     * @param checkerboard
     * @param step
     */
    private static void horseTread(int[][] checkerboard, int row, int col, int step) {
        // 记录棋盘的步数
        checkerboard[row][col] = step;
        // 该棋盘的位置已经访问过
        visited[row * X + col] = true;

        List<Point> nextPoints = getNextSteps(new Point(col, row));
        sortNextSteps(nextPoints);

        while (!nextPoints.isEmpty()) {
            Point p = nextPoints.remove(0);
            if (!visited[p.y * X + p.x]) {// 如果没有访问过，则递归调用该方法
                horseTread(checkerboard, p.y, p.x, step + 1);
            }
        }
        // 如果没有走通，则重置棋盘，和已访问数组信息
        if (step < X * Y && !finished) {
            checkerboard[row][col] = 0;
            visited[row * X + col] = false;
        } else {
            finished = true;
        }

    }

    /
     * 根据当前马的位置，计算出马能走的位置的集合
     *
     * @param point 注意 此时x 的表示列 y表示行
     * @return
     */
    private static List<Point> getNextSteps(Point point) {
        List<Point> list = new ArrayList<>();
        if ((point.x - 2) >= 0 && (point.y - 1) >= 0) {
            list.add(new Point(point.x - 2, point.y - 1));
        }

        if ((point.x - 1) >= 0 && (point.y - 2) >= 0) {
            list.add(new Point(point.x - 1, point.y - 2));
        }

        if ((point.x + 1) < X && (point.y - 2) >= 0) {
            list.add(new Point(point.x + 1, point.y - 2));
        }

        if ((point.x + 2) < X && (point.y - 1) >= 0) {
            list.add(new Point(point.x + 2, point.y - 1));
        }

        if ((point.x - 1) >= 0 && (point.y + 2) < Y) {
            list.add(new Point(point.x - 1, point.y + 2));
        }

        if ((point.x - 2) >= 0 && (point.y + 1) < Y) {
            list.add(new Point(point.x - 2, point.y + 1));
        }

        if ((point.x + 1) < X && (point.y + 2) < Y) {
            list.add(new Point(point.x + 1, point.y + 2));
        }

        if ((point.x + 2) < X && (point.y + 1) < Y) {
            list.add(new Point(point.x + 2, point.y + 1));
        }

        return list;
    }

    /
     * 将下一次要遍历的棋盘位置排序
     * 规则是：让他们按照下一次的能走的位置的数量 递增排序
     * 这样能使回溯的次数减少
     *
     * @param list
     */
    private static void sortNextSteps(List<Point> list) {
        list.sort((p1, p2) -> {
            int next1 = getNextSteps(p1).size();
            int next2 = getNextSteps(p2).size();
            if (next1 < next2) {
                return -1;
            } else if (next1 == next2) {
                return 0;
            } else {
                return 1;
            }
        });
    }
}