package work.rexhao.graph;


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

/**
 * 图的基础及dfs、bfs遍历
 * @Date 2022/7/11 22:26
 */
public class Graph {
    int[][] edges;      // 邻接矩阵
    int n;              // 节点个数
    List<String> vertex;// 顶点名称
    boolean[] flag;     // 记录是否被访问过

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        String[] strs = {"a", "b", "c", "d", "e"};
        graph.addVertex(strs);

        graph.addEdges(0, 1, 1);  // a -- b
        graph.addEdges(0, 2, 1);  // a -- c
        graph.addEdges(2, 3, 1);  // c -- d
        graph.addEdges(0, 4, 1);  // a -- e

        graph.showGraph();
        System.out.println("-----------");

        graph.dfs();
        graph.bfs();
    }

    /**
     * 广度优先遍历
     */
    private void bfs() {
        flag = new boolean[n];
        System.out.print("bfs:");
        ArrayQueue queue = new ArrayQueue(n);

        queue.addQueue(0);
        while (!queue.isEmpty()) {
            // 出队列
            int i = queue.getQueue();
            System.out.print(getValueByIndex(i));
            // 标记
            flag[i] = true;
            // 把该节点连接的节点加入队列
            for (int j = 0; j < n; j++) {
                if (!flag[j] && edges[i][j] != 0) {
                    queue.addQueue(j);
                }
            }
        }

        System.out.println();
    }


    /**
     * 深度优先遍历
     */
    public void dfs() {
        flag = new boolean[n];
        System.out.print("dfs:");
        for (int i = 0; i < n; i++) {
            dfs(i);
        }
        System.out.println();
    }

    public void dfs(int i) {
        // 标记过 -> return
        if (flag[i]) {
            return;
        }
        // 没被标记 -> 输出该节点 -> 标记
        System.out.print(getValueByIndex(i));
        flag[i] = true;
        // 找到该节点的后续节点
        for (int j = 0; j < n; j++) {
            if (edges[i][j] != 0) {
                dfs(j);
            }
        }
    }

    /**
     * 构造器
     *
     * @param n 节点个数
     */
    Graph(int n) {
        this.n = n;
        edges = new int[n][n];
        vertex = new ArrayList<>(n);
    }

    /**
     * 添加节点名称
     *
     * @param strs 节点名称数组
     */
    public void addVertex(String[] strs) {
        vertex.addAll(Arrays.asList(strs));
    }

    /**
     * 添加边
     *
     * @param v1     节点1
     * @param v2     节点2
     * @param weight 权重
     */
    public void addEdges(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
    }

    /**
     * 打印邻接矩阵
     */
    public void showGraph() {
        for (int[] edge : edges) {
            for (int i : edge) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }


    /**
     * 根据下标获取节点数据
     *
     * @param i 节点下标
     * @return 节点数据
     */
    public String getValueByIndex(int i) {
        return vertex.get(i);
    }
}

class ArrayQueue {
    private int maxSize; // 数组最大容量
    private int front; // 队列头
    private int rear; // 队列尾
    private int[] arr; // 队列的数据

    /**
     * 创建队列的构造器
     */
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[arrMaxSize];
        front = -1;// 指向队列头的前一个位置
        rear = -1;// 指向队列尾
    }

    /**
     * 判断队列是否满
     */
    public boolean isFull() {
        return rear == maxSize - 1;
    }

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty() {
        return rear == front;
    }

    /**
     * 添加队列数据
     */
    public void addQueue(int n) {
        if (isFull()) {
            System.out.println("队列满，添加失败！");
            return;
        }
        arr[++rear] = n;
    }

    /**
     * 出队列
     */
    public int getQueue() {
        if (isEmpty()) {
            // 抛出异常 -- 不需要写return
            throw new RuntimeException("队列空");
        }
        return arr[++front];
    }

    /**
     * 遍历
     */
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列空！");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d] = %d\n", i, arr[i]);
        }
    }

    /**
     * 显示头数据（不取出）
     */
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列空");
        }
        return arr[front + 1];
    }
}

package work.rexhao.tree;

import java.util.Arrays;

/**
 * 堆排序
 * @Date 2022/7/5 21:36
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] num = new int[]{3, 2, 4, 1, 5};
        System.out.println(Arrays.toString(num));
        heapSort(num, num.length);
        System.out.println(Arrays.toString(num));
    }

    /**
     * 维护大顶堆
     *
     * @param num   数组
     * @param len   数组长度
     * @param index 待维护元素的下表
     */
    public static void heapify(int[] num, int len, int index) {
        int max = index;
        // 找到最大值
        int leftSon = index * 2 + 1;
        int rightSon = index * 2 + 2;
        if (leftSon < len && num[max] < num[leftSon]) {
            max = leftSon;
        }
        if (rightSon < len && num[max] < num[rightSon]) {
            max = rightSon;
        }
        // 最大的不是父节点 => 交换
        if (max != index) {
            // 1.交换
            int temp = num[max];
            num[max] = num[index];
            num[index] = temp;
            // 2.继续维护下面的子堆
            heapify(num, len, max);
        }

    }


    /**
     * 堆排序入口
     *
     * @param num 待排序数组
     * @param len 数组长度
     */
    public static void heapSort(int[] num, int len) {
        // 建堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(num, len, i);
        }
        // 交换首尾元素
        for (int i = len - 1; i > 0; i--) {
            int temp = num[i];
            num[i] = num[0];
            num[0] = temp;
            heapify(num, i, 0);
        }
    }
}

package work.rexhao.huffmantree;

import org.jetbrains.annotations.NotNull;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 哈夫曼树的生成
 * @Date 2022/7/6 12:49
 */
public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int num[] = {13, 7, 8, 3, 29, 6, 1};
        initHuffmanTree(num);

    }

    public static void initHuffmanTree(int[] num) {
        ArrayList<TreeNode> tnodes = new ArrayList<>();
        for (int i : num) {
            tnodes.add(new TreeNode(i));
        }
        while (tnodes.size() != 1) {
            Collections.sort(tnodes);
            TreeNode leftNode = tnodes.get(0);
            TreeNode rightNode = tnodes.get(1);
            tnodes.add(new TreeNode(leftNode.getData() + rightNode.getData(), leftNode, rightNode));
            tnodes.remove(leftNode);
            tnodes.remove(rightNode);
            Collections.sort(tnodes);
        }
        preOrder(tnodes.get(0));


    }

    /**
     * 先序遍历
     */
    public static void preOrder(TreeNode tn) {
        if (tn != null) {
            System.out.print(tn.getData() + " ");
            preOrder(tn.leftNode);
            preOrder(tn.rightNode);
        }
    }


}

/**
 * 二叉树的节点
 */
class TreeNode implements Comparable<TreeNode> {
    private int data;
    TreeNode leftNode;
    TreeNode rightNode;

    TreeNode(int data) {
        this.data = data;
    }

    public TreeNode(int data, TreeNode leftNode, TreeNode rightNode) {
        this.data = data;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    @Override
    public int compareTo(@NotNull TreeNode o) {
        return this.data - o.data;
    }
}

package work.rexhao.huffmantree;

import org.jetbrains.annotations.NotNull;

import java.util.*;

/**
 * 哈夫曼编码与解码
 * @Date 2022/7/10 16:08
 */
public class HuffmanCode {
    // 存储哈夫曼编码表
    static Map<Byte, String> HuffmanCodes = new HashMap<>();

    public static void main(String[] args) {
        String str1 = "i like java java java do you like java?";
        System.out.println("str1:" + str1);
        byte[] huffmanBytes = huffmanZip(str1.getBytes());
        System.out.println("huffmanBytes:" + Arrays.toString(huffmanBytes));
        String str2 = huffmanUnzip(huffmanBytes);
        System.out.println("str2:" + str2);
    }

    /**
     * 哈夫曼解码
     *
     * @param huffmanBytes 哈夫曼编码
     * @return 解码后字符串
     */
    private static String huffmanUnzip(byte[] huffmanBytes) {
        StringBuilder code = new StringBuilder();
        for (byte b : huffmanBytes) {
            code.append(Integer.toBinaryString(b | 256).substring(
                    Integer.toBinaryString(b | 256).length() - 8));
        }
        Map<String, Byte> unzipCodes = new HashMap<>();
        for (Map.Entry<Byte, String> entry : HuffmanCodes.entrySet()) {
            unzipCodes.put(entry.getValue(), entry.getKey());
        }
        List<Byte> bytesList = new ArrayList<>();
        for (int i = 0; i < code.length(); ) {
            int count = 1;
            while (true) {
                if (i + count >= code.length()) {
                    i = code.length();
                    break;
                }
                String key = code.substring(i, i + count);
                Byte value = unzipCodes.get(key);
                if (value == null) {
                    count++;
                } else {
                    bytesList.add(value);
                    i += count;
                    break;
                }
            }
        }
        byte[] bytes = new byte[bytesList.size()];
        for (int i = 0; i < bytesList.size(); i++) {
            bytes[i] = bytesList.get(i);
        }
        return new String(bytes);
    }

    /**
     * 哈夫曼编码
     *
     * @param bytes 编码前
     * @return 编码后
     */
    public static byte[] huffmanZip(byte[] bytes) {
        // 1.创建哈夫曼树
        Map<Byte, Integer> huffmanMap = byteCounter(bytes);
        HuffmanCodeNode root = initHuffmanTree(huffmanMap);
        // 2.获得哈夫曼编码表
        toHuffmanCodes(root);
        // 3.进行转码
        return toHuffmanBytes(bytes, HuffmanCodes);
    }

    /**
     * 通过哈夫曼编码表转化成哈弗曼编码
     *
     * @param bytes        原字符数组
     * @param huffmanCodes 哈夫曼编码表
     * @return 编码后的哈夫曼编码
     */
    private static byte[] toHuffmanBytes(byte[] bytes, Map<Byte, String> huffmanCodes) {
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            sb.append(huffmanCodes.get(b));
        }
        byte[] code = new byte[(sb.length() + 7) / 8];
        int index = 0;
        for (int i = 0; i < sb.length(); i += 8) {
            if (i + 8 < sb.length()) {
                code[index++] = (byte) Integer.parseInt(sb.substring(i, i + 8), 2);
            } else {
                StringBuilder temp = new StringBuilder(sb.substring(i));
                for (int j = temp.length(); j < 8; j++) {
                    temp.append("0");
                }
                code[index++] = (byte) Integer.parseInt(temp.toString(), 2);
            }
        }
        return code;
    }

    /**
     * 将哈夫曼树转换为哈夫曼编码表（重载）
     *
     * @param root 根节点
     */
    private static void toHuffmanCodes(HuffmanCodeNode root) {
        toHuffmanCodes(root, "");
    }

    /**
     * 将哈夫曼树转换为哈夫曼编码表
     *
     * @param node 节点
     * @param s    代拼接编码
     */
    private static void toHuffmanCodes(HuffmanCodeNode node, String s) {
        if (node == null) {
            return;
        }
        // node有值的话 -> 将b放进去
        if (node.b != null) {
            HuffmanCodes.put(node.b, s);
        }
        toHuffmanCodes(node.leftNode, s + "0");
        toHuffmanCodes(node.rightNode, s + "1");
    }

    /**
     * 创建哈夫曼树
     *
     * @param huffmanMap 字符权重
     * @return 根节点
     */
    private static HuffmanCodeNode initHuffmanTree(Map<Byte, Integer> huffmanMap) {
        List<HuffmanCodeNode> list = new ArrayList<>();
        for (Byte b : huffmanMap.keySet()) {
            list.add(new HuffmanCodeNode(b, huffmanMap.get(b)));
        }
        while (list.size() != 1) {
            Collections.sort(list);
            HuffmanCodeNode hcn1 = list.get(0);
            HuffmanCodeNode hcn2 = list.get(1);
            list.remove(0);
            list.remove(0);
            list.add(new HuffmanCodeNode(null, hcn1.weight + hcn2.weight, hcn1, hcn2));
        }
        return list.get(0);
    }

    /**
     * 统计字符出现的次数
     *
     * @param bytes 待统计字符
     * @return 字符权重map
     */
    public static Map<Byte, Integer> byteCounter(byte[] bytes) {
        Map<Byte, Integer> map = new HashMap<>();
        for (byte b : bytes) {
            map.merge(b, 1, Integer::sum);
        }
        return map;
    }
}

/**
 * 哈夫曼编码的哈夫曼树节点
 */
class HuffmanCodeNode implements Comparable<HuffmanCodeNode> {
    Byte b;
    int weight;
    HuffmanCodeNode rightNode;
    HuffmanCodeNode leftNode;

    public HuffmanCodeNode(Byte b, int weight) {
        this.b = b;
        this.weight = weight;
    }

    public HuffmanCodeNode(Byte b, int weight, HuffmanCodeNode rightNode, HuffmanCodeNode leftNode) {
        this.b = b;
        this.weight = weight;
        this.rightNode = rightNode;
        this.leftNode = leftNode;
    }

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

    @Override
    public String toString() {
        return "HuffmanCodeNode{" + "b=" + b + ", weight=" + weight + ", rightNode=" + rightNode + ", leftNode=" + leftNode + '}';
    }
}

package work.rexhao.binarySortTree;

/**
 * 二叉排序树BST
 * @Date 2022/7/11 10:05
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        BinarySortTree bst = new BinarySortTree();
        int[] num = {7, 3, 10, 1, 6, 9, 12, 2};
        for (int i : num) {
            bst.add(new Node(i));
        }
        BinarySortTree.infixOrder(bst.root);
        System.out.println();

        bst.delete(10);
        BinarySortTree.infixOrder(bst.root);
        System.out.println();

    }
}

/**
 * 二叉排序树
 */
class BinarySortTree {
    Node root;

    /**
     * 添加节点
     *
     * @param next 待添加节点
     */
    public void add(Node next) {
        if (root == null) {
            root = next;
        } else {
            root.add(next);
        }
    }

    /**
     * 前序遍历
     *
     * @param node 根节点
     */
    public static void infixOrder(Node node) {
        if (node == null) {
            return;
        }
        infixOrder(node.left);
        System.out.print(node.data + " ");
        infixOrder(node.right);
    }

    /**
     * 删除节点
     *
     * @param target 待删除节点的值
     */
    public void delete(int target) {
        Node node = search(root, target);
        Node nodeParent = searchParent(root, node);
        // 经典判空
        if (node == null || nodeParent == null) {
            System.out.println("节点不存在或节点无父节点!");
            return;
        }
        // 判断待删除节点的形式
        if (node.left == null && node.right == null) {
            // 叶子节点
            if (nodeParent.right == node) {
                // 右节点
                nodeParent.right = null;
            } else {
                // 左节点
                nodeParent.left = null;
            }
        } else if (node.left != null && node.right != null) {
            // 两个子树的节点
            // 1. 找右子树的最小值(右子树的左子树的叶子结点)
            Node min = searchRightMinNode(node.right);
            // 2. 记录最小值
            int temp = min.data;
            // 3. 删除原来的最小值节点
            delete(min.data);
            // 4. 将最小值提到(覆盖)节点位置
            node.data = temp;
        } else {
            // 一个子树的节点
            if (node.left == null) {
                // 存在右子树
                if (nodeParent.right == node) {
                    // 右节点
                    nodeParent.right = node.right;
                } else {
                    // 左节点
                    nodeParent.left = node.right;
                }
            } else {
                // 存在左子树
                if (nodeParent.right == node) {
                    // 右节点
                    nodeParent.right = node.left;
                } else {
                    // 左节点
                    nodeParent.left = node.left;
                }
            }
        }


    }

    /**
     * 找 node 节点右子树的最小节点
     *
     * @param node 开始寻找的节点
     * @return 右子树的最小节点
     */
    private Node searchRightMinNode(Node node) {
        // 找到叶子结点(最小的点)
        return node.left == null ? node : searchRightMinNode(node.left);
    }

    /**
     * 找 data 为 i 的节点
     *
     * @param root 根节点
     * @param i    待查找数据
     * @return 查找到的节点，不存在返回null
     */
    public static Node search(Node root, int i) {
        // 1.经典判空
        if (root == null) {
            return null;
        }
        // 2.找节点
        if (i == root.data) {
            return root;
        } else if (i < root.data) {
            return search(root.left, i);
        } else {
            return search(root.right, i);
        }
    }

    /**
     * 找到 target 的父节点
     *
     * @param root   根节点
     * @param target 待寻找节点
     * @return 待寻找节点的父节点，不存在返回null
     */
    public static Node searchParent(Node root, Node target) {
        // 经典判空
        if (root == null || target == null) {
            return null;
        }
        // 判左右的节点
        if ((root.right != null && root.right.data == target.data) || (root.left != null && root.left.data == target.data)) {
            return root;
        }
        // 没找到 -> 递归往下找
        if (root.data > target.data) {
            return searchParent(root.left, target);
        } else {
            return searchParent(root.right, target);
        }
    }
}

/**
 * 节点
 */
class Node {
    int data;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
    }

    /**
     * 添加节点
     *
     * @param next 待添加节点
     */
    public void add(Node next) {
        if (next == null) {
            return;
        }
        if (this.data > next.data) {
            if (this.left == null) {
                this.left = next;
            } else {
                this.left.add(next);
            }
        } else {
            if (this.right == null) {
                this.right = next;
            } else {
                this.right.add(next);
            }
        }
    }

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

package work.rexhao.AVLTree;

import java.util.Arrays;

/**
 * 平衡二叉树
 */
public class AVLDemo {
    public static void main(String[] args) {
        // 案例1：左旋转
        int[] num0 = {4, 3, 6, 5, 7, 8};
        System.out.println(Arrays.toString(num0));
        AVLTree avl0 = new AVLTree();
        for (int i : num0) {
            avl0.add(new Node(i));
        }
        avl0.infixOrder();
        System.out.println("left = " + avl0.findLeftHeight());
        System.out.println("right = " + avl0.findRightHeight());
        System.out.println("是否为AVL树:" + avl0.isAVL());
        avl0.leftRotate();
        avl0.infixOrder();
        System.out.println("left = " + avl0.findLeftHeight());
        System.out.println("right = " + avl0.findRightHeight());
        System.out.println("是否为AVL树:" + avl0.isAVL());

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

        // 案例2：右旋转
        int[] num1 = {7, 5, 8, 4, 6, 3};
        System.out.println(Arrays.toString(num1));
        AVLTree avl1 = new AVLTree();
        for (int i : num1) {
            avl1.add(new Node(i));
        }
        avl1.infixOrder();
        System.out.println("left = " + avl1.findLeftHeight());
        System.out.println("right = " + avl1.findRightHeight());
        System.out.println("是否为AVL树:" + avl1.isAVL());
        avl1.rightRotate();
        avl1.infixOrder();
        System.out.println("left = " + avl1.findLeftHeight());
        System.out.println("right = " + avl1.findRightHeight());
        System.out.println("是否为AVL树:" + avl1.isAVL());

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

        // 案例3：双旋转
        int[] num2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(Arrays.toString(num2));
        AVLTree avl2 = new AVLTree();
        for (int i : num2) {
            avl2.add(new Node(i));
        }
        avl2.infixOrder();
        System.out.println("left = " + avl2.findLeftHeight());
        System.out.println("right = " + avl2.findRightHeight());
        System.out.println("是否为AVL树:" + avl2.isAVL());
        avl2.rotate();
        avl2.infixOrder();
        System.out.println("left = " + avl2.findLeftHeight());
        System.out.println("right = " + avl2.findRightHeight());
        System.out.println("是否为AVL树:" + avl2.isAVL());

        System.out.println("-------------");
    }
}

/**
 * 二叉排序树
 */
class AVLTree {
    Node root;

    /**
     * 双旋转
     */
    public void rotate() {
        while (true) {
            if (isAVL()) {
                break;
            } else {
                if (findLeftHeight() > findRightHeight()) {
                    rightRotate();
                } else {
                    leftRotate();
                }
            }
        }
    }

    /**
     * 左旋转
     */
    public void leftRotate() {
        // 0. 经典判空
        if (root == null) return;
        // 1. 取右子节点
        Node newRoot = new Node(root.right.data);
        // 2. 将根节点的值挂在 newRoot 上
        newRoot.left = new Node(root.data);
        // 3. 将 root 的左子节点挂在 newRoot.left.left
        newRoot.left.left = root.left;
        // 4. 将原 newRoot 的左子节点挂在 newRoot.left.right
        newRoot.left.right = root.right.left;
        // 5. 将原 newRoot 的右子节点挂在 newRoot.right
        newRoot.right = root.right.right;
        // 6. 用 newRoot 替换 root
        this.root = newRoot;
    }

    /**
     * 右旋转
     */
    public void rightRotate() {
        // 0. 经典判空
        if (root == null) return;
        // 1. 取左子节点
        Node newRoot = new Node(root.left.data);
        // 2. 将根节点的值挂在 newRoot 上
        newRoot.right = new Node(root.data);
        // 3. 将 root 的右子节点挂在 newRoot.right.right
        newRoot.right.right = root.right;
        // 4. 将原 newRoot 的右子节点挂在 newRoot.right.left
        newRoot.right.left = root.left.right;
        // 5. 将原 newRoot 的左子节点挂在 newRoot.left
        newRoot.left = root.left.left;
        // 6. 用 newRoot 替换 root
        this.root = newRoot;
    }

    /**
     * 判断是否为平衡二叉树
     */
    public boolean isAVL() {
        return Math.abs(findLeftHeight() - findRightHeight()) <= 1;
    }

    /**
     * 找右子树深度
     *
     * @return 右子树深度
     */
    public int findRightHeight() {
        if (root == null) {
            return 0;
        }
        int[] r = {1};
        int[] l = {1};
        findHeight(root.right, r, l);
        return Math.max(r[0], l[0]);
    }

    /**
     * 找左子树深度
     *
     * @return 左子树深度
     */
    public int findLeftHeight() {
        if (root == null) {
            return 0;
        }
        int[] r = {1};
        int[] l = {1};
        findHeight(root.left, r, l);
        return Math.max(r[0], l[0]);
    }

    /**
     * 求深度
     */
    private void findHeight(Node node, int[] r, int[] l) {
        // 经典判空
        if (node == null) {
            return;
        }
        // 判叶子节点
        if (node.left == null && node.right == null) {
            return;
        }
        if (node.left != null) {
            r[0]++;
            findHeight(node.left, r, l);
        }
        if (node.right != null) {
            l[0]++;
            findHeight(node.right, r, l);
        }
    }


    /**
     * 添加节点
     *
     * @param next 待添加节点
     */
    public void add(Node next) {
        if (root == null) {
            root = next;
        } else {
            root.add(next);
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        Node.infixOrder(root);
        System.out.println();
    }

}

/**
 * 节点
 */
class Node {
    int data;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
    }

    /**
     * 添加节点
     *
     * @param next 待添加节点
     */
    public void add(Node next) {
        if (next == null) {
            return;
        }
        if (this.data > next.data) {
            if (this.left == null) {
                this.left = next;
            } else {
                this.left.add(next);
            }
        } else {
            if (this.right == null) {
                this.right = next;
            } else {
                this.right.add(next);
            }
        }
    }

    /**
     * 中序遍历
     *
     * @param node 根节点
     */
    public static void infixOrder(Node node) {
        if (node == null) {
            return;
        }
        infixOrder(node.left);
        System.out.print(node.data + " ");
        infixOrder(node.right);
    }

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

package work.rexhao.search;

/**
 * 非递归二分查找
 * @Date 2022/7/14 11:05
 */
public class BinarySearchNoRecursion {
    public static void main(String[] args) {
        int[] num = new int[]{10, 12, 23, 32, 45, 64, 65, 69, 83};
        System.out.println(binarySearchNoRecursion(10, num));
        System.out.println(binarySearchNoRecursion(65, num));
        System.out.println(binarySearchNoRecursion(99, num));
    }

    public static int binarySearchNoRecursion(int target, int[] num) {
        int left = 0;
        int right = num.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (target == num[mid]) {
                return mid;
            } else if (target > num[mid]) {
                // 目标值比中间值大 --> 向右找
                left = mid + 1;
            } else {
                // 目标值比中间值小 --> 向左找
                right = mid - 1;
            }
        }
        return -1;
    }
}

package work.rexhao.search;

import java.util.Arrays;

/**
 * 二分查找
 * @Date 2022/7/3 22:54
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] num = new int[]{10, 12, 23, 32, 45, 64, 65, 69, 83};
        System.out.println(Arrays.toString(num));
        System.out.println(binarySearch(num, 69, 0, num.length - 1));
        System.out.println(binarySearch(num, 99, 0, num.length - 1));
    }

    public static int binarySearch(int[] num, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        if (num[(left + right) / 2] == target) {
            return (left + right) / 2;
        } else if (num[(left + right) / 2] > target) {
            return binarySearch(num, target, left, (left + right) / 2);
        } else {
            return binarySearch(num, target, (left + right) / 2 + 1, right);
        }
    }
}

if |p| <= n0
	then return(ADHOC(P))
// 将p分解为较小的子问题p1,P2,…,Pk
for if <- 1 to k
do yi <-  DC递归解决pi
T <- MERGE(y1,x2,…,vk) 合并子问题
return(T)

package work.rexhao.algorithm.dc;

import java.util.Collections;

/**
 * 汉诺塔
 * @Date 2022/7/14 10:10
 */
public class hanoiDemo {
    static int count = 0;

    public static void main(String[] args) {
        hanoiTower(5, 'A', 'B', 'C');
    }

    private static void hanoiTower(int num, char a, char b, char c) {
        // 如果只有一个盘
        if (num == 1) {
            System.out.println(++count + " : 第 1 个盘从 " + a + "->" + c);
        } else {
            // 如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的一个盘 2. 上面的所有盘

            // 1. 先把 最上面的所有盘 A->B， 移动过程会使用到 c
            hanoiTower(num - 1, a, c, b);

            // 2. 把最下边的盘 A->C
            System.out.println(++count + " : 第 " + num + " 个盘从 " + a + "->" + c);

            // 3. 把 B 塔的所有盘 从 B->C , 移动过程使用到 a 塔
            hanoiTower(num - 1, b, a, c);
        }
    }
}

package work.rexhao.algorithm.dynamic;

/**
 * 01背包问题
 * @Date 2022/7/14 10:07
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        // 1. 定义二维数组
        int knapsackSize = 4;    // 背包容量
        int goodsType = 3;  // 物品种类
        int[][] value = new int[knapsackSize + 1][goodsType + 1];   // dp价值表
        int[] goodsSize = {0, 1, 4, 3};    // 每个物品的大小
        int[] goodsValue = {0, 15, 30, 20};  // 每个物品的价值

        // 2. 第一行为空（空背包）且第一列为空（背包容量为0）

        // 3. 遍历表
        for (int i = 1; i < knapsackSize + 1; i++) {
            // i:背包容量
            for (int j = 1; j < goodsType + 1; j++) {
                // j:物品类型
                knapsackProblem(knapsackSize, i, j, value, goodsSize, goodsValue);
            }
        }

        // 3.1 打印表
        for (int i = 0; i < goodsType + 1; i++) {
            for (int j = 0; j < knapsackSize + 1; j++) {
                System.out.print(value[j][i] + "\t");
            }
            System.out.println();
        }
        System.out.println("--------------------");

        // 4. 输出答案
        int ans = 0;
        for (int[] ints : value) {
            for (int i : ints) {
                ans = Math.max(ans, i);
            }
        }
        System.out.println("总价值最大为: " + ans);
    }

    private static void knapsackProblem(int knapsackSize, int i, int j, int[][] value, int[] goodsSize, int[] goodsValue) {
        if (goodsSize[j] == i) {
            // 放一个正好放满 --> 放(这个或上一个品种)中价值更高的
            value[i][j] = Math.max(goodsValue[j], value[i][j - 1]);
        } else if (goodsSize[j] > i) {
            // 这个放不下 --> 放上一品种的
            value[i][j] = value[i][j - 1];
        } else {
            // 放下了，但是剩下位置了 --> 剩下位置找本行相应的那个 --> 放(这个或上一个品种)中价值更高的
            value[i][j] = Math.max(goodsValue[j] + value[i - goodsSize[j]][j], value[i][j - 1]);
        }
    }

}

/*
    问题：有一个背包，容量为 4kg， 现有如下物品
         要求达到的目标为装入的背包的总价值最大，并且重量不超出
    G   1kg     15
    S   4kg     30
    L   3Kg     20
 */