/**
 * @Author: 郜宇博
 * @Date: 2021/11/27 20:47
 */
public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(getFibonacci1(20));
        System.out.println(getFibonacci2(20));
    }

    public static int getFibonacci1(int N) {
        if (N == 1) {
            return 1;
        }
        if (N == 2) {
            return 1;
        }
        return getFibonacci1(N - 1) + getFibonacci1(N - 2);
    }

    /**
     * 斐波那契公式
     * 使用线性代数方法进行计算
     */
    public static int getFibonacci2(int N) {
        if (N < 0) {
            return -1;
        }
        if (N == 1 || N == 2) {
            return 1;
        }
        //获取fibonacci的base矩阵
        int[][] base = {{1, 1}, {1, 0}};
        //计算base的n-2次幂
        int[][] res = matrixPower(base, N - 2);
        return res[0][0] + res[1][0];
    }

    //矩阵次幂
    public static int[][] matrixPower(int[][] base, int p) {
        //单位矩阵
        int[][] resMatrix = new int[base.length][base[0].length];
        for (int i = 0; i < base.length; i++) {
            resMatrix[i][i] = 1;
        }
        int[][] temp = base;
        //快速幂
        for (; p != 0; p >>= 1) {
            if ((p & 1) != 0) {
                resMatrix = muliMatrix(resMatrix, temp);
            }
            temp = muliMatrix(temp, temp);
        }
        return resMatrix;
    }
    //计算矩阵乘法
    public static int[][] muliMatrix(int[][] temp, int[][] temp1) {
        int [][] res = new int[temp.length][temp1[0].length];
        for (int i = 0 ; i < temp.length; i++){
            for (int j = 0 ; j < temp1[0].length; j++){
                for (int k = 0; k < temp1.length; k++){
                    res[i][j] += temp[i][k] * temp1[k][j];
                }
            }
        }
        return res;
    }
}

/**
 * @Author: 郜宇博
 * @Date: 2021/11/27 21:58
 */
public class DeleteWood {
    //保证剩下的都是斐波那契数就拼不出三角形
    public static int minDelete(int m) {
        int fiboCount = getFiboCount(m);
        return m-fiboCount;
    }
    /**
     * 计算[1-N]数字内有多少个斐波那契数
     */
    public static int getFiboCount(int N){
        int index1 = 1;
        int index2 = 2;
        int res = 2;
        while (index1 + index2 <= N){
            index1 += index2;
            index2 = index1 - index2;
            res++;
        }
        return res;
    }

    public static void main(String[] args) {
        int test = 8;
        System.out.println(minDelete(test));
    }
}

/**
 * @Author: 郜宇博
 * @Date: 2021/11/27 22:12
 */
public class Bag01Problem {
    public static void main(String[] args) {
        int[] arr = { 4, 3, 2,5,3,5,8,2,3,4,58};
        int w = 8;
        int[][] ints = new int[arr.length][9];
        for (int i = 0 ; i < ints.length ; i++){
            Arrays.fill(ints[i],-1);
        }
        System.out.println(func4(arr, w,0));
        System.out.println(func5(arr, w));
    }
    public static int func4(int[] v,int weight,int index){
        if (weight < 0){
            return 0;
        }
        if (weight == 0){
            return 1;
        }
        if (index == v.length-1){
            return weight - v[index] >=0?2:1;
        }
        int s = func4(v,weight-v[index],index+1);
        int u = func4(v,weight,index+1);
        return s + u;
    }
    public static int func5(int[]v,int weight){
        int[][] dp  = new int[v.length][weight + 1];
        for (int i = 0; i < v.length; i++){
            dp[i][0] = 1;
        }
        for (int i = 0; i <= weight; i++){
            dp[v.length-1][i] = i - v[v.length-1] >=0?2:1;
        }
        for (int i = v.length-2; i >=0; i--){
            for (int j = 0; j <= weight; j++){
                dp[i][j] = j-v[i] < 0?dp[i+1][j]:dp[i+1][j-v[i]]+dp[i+1][j];
            }
        }
        return dp[0][weight];
    }
}

/**
 * @Author: 郜宇博
 * @Date: 2021/11/28 22:17
 * 给你一个字符串类型的数组arr，譬如： String[] arr = { "b\\cst", "d\\", "a\\d\\e", "a\\b\\c" };
 * 你把这些路径中蕴含的目录结构给画出来，子目录直接列在父目录下面，并比父目录 向右进两格
 */
public class PrintCatalogue {
    public static void main(String[] args) {
        String[] arr = { "b\\cst", "d\\", "a\\d\\e", "a\\b\\c" };
        print(arr);
    }
    static class Node{
        public String name;
        //使用顺序map，可以实现打印的时候按顺序
        public TreeMap<String ,Node> nextMap;
        public Node(String name){
            this.name = name;
            nextMap = new TreeMap<>();
        }
    }
    /**
     * 前缀树方式
     * 将每个字母对应一个node，如果要加入的在当前字母的next中，那么放在next中，没有就新建
     */
    public static void print(String[] strings){
        Node head = generateFolderTree(strings);
        printTree(head,0);
    }

    private static Node getPrefixTree(String[] strings) {
        Node head = new Node("");
        Node cur = head;
        for (String str: strings){
            String[] letters = getLetters(str);
            //更新cur回到head
            cur = head;
            for (String letter: letters){
                if (!cur.nextMap.containsKey(letter)) {
                    cur.nextMap.put(letter,new Node(letter));
                }
                cur = cur.nextMap.get(letter);
            }
        }
        return head;
    }
    public static Node generateFolderTree(String[] folderPaths) {
        Node head = new Node("");
        for (String foldPath : folderPaths) {
            String[] paths = foldPath.split("\\\\");
            Node cur = head;
            for (int i = 0; i < paths.length; i++) {
                if (!cur.nextMap.containsKey(paths[i])) {
                    cur.nextMap.put(paths[i], new Node(paths[i]));
                }
                cur = cur.nextMap.get(paths[i]);
            }
        }
        return head;
    }
    public static void printTree(Node head, int level) {
        if (level != 0){
            System.out.println(getSpace(level)+head.name);
        }
        for (Node node: head.nextMap.values()){
            printTree(node,level+1);
        }
    }
    //按照树的层数获取不同数量的空格1层没有，2层2个
    public static String getSpace(int level){
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 1; i < level;i++){
            stringBuilder.append("  ");
        }
        return stringBuilder.toString();
    }
    //将 "a\\b\\c" => [a,b,c]
    public static String[] getLetters(String str){
        return str.split("\\\\");
    }
}

/**
 * @Author: 郜宇博
 * @Date: 2021/11/28 22:55
 * 双向链表节点结构和二叉树节点结构是一样的，如果你把last认为是left， next认为是next的话。
 * 给定一个搜索二叉树的头节点head，请转化成一条有序的双向链表，并返回链
 * 表的头节点。
 */
public class ConvertDoubleList {
    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(2);
        head.right = new Node(9);
        head.left.left = new Node(1);
        head.left.right = new Node(3);
        head.left.right.right = new Node(4);
        head.right.left = new Node(7);
        head.right.right = new Node(10);
        head.left.left = new Node(1);
        head.right.left.left = new Node(6);
        head.right.left.right = new Node(8);
        Node newHead = getDoubleLinkedList(head);
        printDoubleLinkedList(newHead);
    }
    public static void printDoubleLinkedList(Node head) {
        System.out.print("Double Linked List: ");
        Node end = null;
        while (head != null) {
            System.out.print(head.value + " ");
            end = head;
            head = head.right;
        }
        System.out.print("| ");
        while (end != null) {
            System.out.print(end.value + " ");
            end = end.left;
        }
        System.out.println();
    }
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }
    static class Info{
        public Node head;
        public Node last;

        public Info(Node head, Node last) {
            this.head = head;
            this.last = last;
        }
    }
    public static Node getDoubleLinkedList(Node searchHead){
        Info info = f(searchHead);
        return info.head;
    }
    public static Info f(Node node){
        if (node == null){
            return new Info(null,null);
        }
        Info leftInfo = f(node.left);
        Info rightInfo = f(node.right);
        //连接
        if (leftInfo.last != null){
            leftInfo.last.right = node;
            node.left = leftInfo.last;
        }
        if (rightInfo.head != null){
            rightInfo.head.left = node;
            node.right = rightInfo.head;
        }
        Node head = leftInfo.head==null?node:leftInfo.head;
        Node last = rightInfo.last==null?node:rightInfo.last;
        return new Info(head,last);
    }
}

/**
 * @Author: 郜宇博
 * @Date: 2021/11/28 23:37
 * 子矩阵最大和
 */
public class MaxChildMatrixSum {
    public static void main(String[] args) {
        int[][] matrix = { { -90, 48, 78 }, { 64, -40, 64 }, { -81, -7, 66 } };
        System.out.println(getMaxMatrixSum(matrix));
    }
    /**
     * 将矩阵的下面一行对应累加到上面，在求子数组的累加和
     */
    public static int getMaxMatrixSum(int[][] matrix){
        if(matrix == null || matrix.length == 0){
            return 0;
        }
        //将矩阵的上面层累加在一起方便求子数组和，---》将矩阵求和变为一维数组求和
        int[] sumMatrixArray = null;
        int cur = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0 ; i < matrix.length; i++){
            sumMatrixArray = new int[matrix[0].length];
            for (int j = i; j < matrix.length; j++){
                //使用最大子数组和
                cur = 0;
                for (int k = 0 ; k < matrix[0].length;k++){
                    //累加
                    sumMatrixArray[k] += matrix[j][k];
                    cur += sumMatrixArray[k];
                    max = Math.max(max,cur);
                    cur = Math.max(0,cur);
                }
            }
        }
        return max;
    }
}