/**
 * @Author: 郜宇博

 * @Date: 2021/12/9 15:06
 * 一个 char 类型的数组 chs，其中所有的字符都不同。

 * 例如，chs=['A', 'B', 'C', ... 'Z']，

 * 则字符串与整数的对应关系如下:
 * A, B... Z, AA,AB...AZ,BA,BB...ZZ,AAA... ZZZ, AAAA...
 * 1, 2...26,27, 28... 52,53,54...702,703...18278, 18279...
 * 实现根据对应关系完成字符串与整数相互转换的两个函数。

 */
public class CharToNum {
    //number->char
    public static String numberToChar(char[] charsMap,int number){
        //1.获取转后的字符串长度
        int strLength = 0;
        int curPowNumber = 1;
        int base = charsMap.length;
        while (number >= curPowNumber){
            number -= curPowNumber;
            curPowNumber *= base;
            strLength++;
        }
        //2.获取各位上的字符
        char[] resultChars = new char[strLength];
        int index = 0;
        int nCur = 0;
        do {
            curPowNumber /= base;
            nCur = number / curPowNumber;
            number %= curPowNumber;
            //计算出的当前位置的个数 加上 之前的1个
            resultChars[index++] = getKthString(charsMap,nCur+1);
        }while (index != strLength);
        return String.valueOf(resultChars);
    }
    public static char getKthString(char[] charsMap, int i) {
        if (i == 0 || i > charsMap.length){
            return 0;
        }
        return charsMap[i-1];
    }

    //char->number
    public static int getNum(char[] chs, String str) {
        if (chs == null || chs.length == 0) {
            return 0;
        }
        char[] strc = str.toCharArray();
        int base = chs.length;
        int cur = 1;
        int res = 0;
        for (int i = strc.length - 1; i != -1; i--) {
            res += getNthFromChar(chs, strc[i]) * cur;
            cur *= base;
        }
        return res;
    }
    public static int getNthFromChar(char[] chs, char ch) {
        return (ch-'A')+1;
    }
    public static void main(String[] args) {
        char[] chs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K',
                'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',
                'X', 'Y', 'Z' };
        System.out.println(numberToChar(chs, 18278));
        System.out.println(getNum(chs, "AB"));
    }
}

/**
 * @Author: 郜宇博

 * @Date: 2021/12/9 16:13
 * 给定一个二维数组matrix，每个单元都是一个整数，有正有负。

 * 最开始的时候小Q操纵 一条长度为0的蛇蛇从矩阵最左侧任选一个单元格进入地图，

 * 蛇每次只能够到达当前位置的右上相邻，右侧相邻和右下相邻的单元格。

 * 蛇蛇到达一个单元格后，自身的长度会 瞬间加上该单元格的数值，任何情况下长度为负则游戏结束。

 * 小Q是个天才，他拥有一 个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为其相反数

 * （注：最多只能改变一个节点）。

 * 问在小Q游戏过程中，他的蛇蛇最长长度可以到多少？

 */
public class SnakeMaxLength {
    public static void main(String[] args) {
        int[][] matrix = { { 1, -4, 10 }, { 3, -2, -1 }, { 2, -1, 0 }, { 0, 5, -2 } };
        System.out.println(getMacLengthWithCatch(matrix));
    }

    /**
     * 递归返回结果，两个。

     * 1.目前位置使用能力的获得的长度
     * 2.不使用能力获取的长度
     */
    public static class Info{
        public int withAbilityLength;
        public int withoutAbilityLength;
        public Info(int withAbilityLength, int withoutAbilityLength) {
            this.withAbilityLength = withAbilityLength;
            this.withoutAbilityLength = withoutAbilityLength;
        }
    }
    public static int getMaxLength(int[][] matrix){
        int result = Integer.MIN_VALUE;
        for (int i = 0 ; i < matrix.length;i++){
            for (int j = 0; j < matrix[0].length;j++){
                Info info = getLength(matrix, i, j);
                result =  Math.max(result,Math.max(info.withAbilityLength, info.withoutAbilityLength)) ;
            }
        }
        return result;
    }
    public static Info getLength(int[][] matrix,int row,int col){
        //base case->刚进去矩阵
        if (col == 0){
            return new Info(-(matrix[row][col]),matrix[row][col]);
        }
        //之前是否使用过能力到达的最大长度
        int preUseAbilityMaxLength = -1;
        int preNoAbilityMaxLength = -1;
        //此时有之前最多有三种情况可以到达当前位置 左，左上，左下
        //不在第一行
        //1.左上
        if (row >0){
            Info leftUpInfo = getLength(matrix, row - 1, col - 1);
            preNoAbilityMaxLength = leftUpInfo.withoutAbilityLength>=0?leftUpInfo.withoutAbilityLength:-1;
            preUseAbilityMaxLength = leftUpInfo.withAbilityLength>=0?leftUpInfo.withAbilityLength:-1;
        }
        //2左
        Info leftInfo = getLength(matrix,row,col-1);
        preNoAbilityMaxLength = Math.max(leftInfo.withoutAbilityLength,preNoAbilityMaxLength);
        preUseAbilityMaxLength = Math.max(leftInfo.withAbilityLength,preUseAbilityMaxLength);
        //3.左下
        if (row < matrix.length-1){
            Info leftDownInfo = getLength(matrix,row+1,col-1);
            preNoAbilityMaxLength = Math.max(leftDownInfo.withoutAbilityLength,preNoAbilityMaxLength);
            preUseAbilityMaxLength = Math.max(leftDownInfo.withAbilityLength,preUseAbilityMaxLength);
        }
        //封装自己的Info
        int curUseMaxLength = -1;
        int curNoMaxLength = -1;
        //之前没用，现在可以用可以不用
        if (preNoAbilityMaxLength > 0){
            curNoMaxLength = preNoAbilityMaxLength + matrix[row][col];
            curUseMaxLength = preNoAbilityMaxLength - matrix[row][col];
        }
        //现在只能不用
        if (preUseAbilityMaxLength > 0){
            //更新用过的长度
            curUseMaxLength = Math.max(curUseMaxLength,preUseAbilityMaxLength + matrix[row][col]);
        }
        return new Info(curUseMaxLength,curNoMaxLength);
    }
    /**
     * 加入缓存机制
     */
    public static int getMacLengthWithCatch(int[][]matrix){
        int result = Integer.MIN_VALUE;
        Info[][] dp = new Info[matrix.length][matrix[0].length];
        for (int i = 0 ; i < matrix.length;i++){
            for (int j = 0; j < matrix[0].length;j++){
                Info info = getLengthWithCatch(matrix, i, j,dp);
                result =  Math.max(result,Math.max(info.withAbilityLength, info.withoutAbilityLength)) ;
            }
        }
        return result;
    }
    public static Info getLengthWithCatch(int[][] matrix,int row,int col,Info[][]dp){
        if (dp[row][col] != null){
            return dp[row][col];
        }
        //base case->刚进去矩阵
        if (col == 0){
            dp[row][col] = new Info(-(matrix[row][col]),matrix[row][col]);
            return dp[row][col];
        }
        //之前是否使用过能力到达的最大长度
        int preUseAbilityMaxLength = -1;
        int preNoAbilityMaxLength = -1;
        //此时有之前最多有三种情况可以到达当前位置 左，左上，左下
        //不在第一行
        //1.左上
        if (row >0){
            Info leftUpInfo = getLengthWithCatch(matrix, row - 1, col - 1,dp);
            preNoAbilityMaxLength = leftUpInfo.withoutAbilityLength>=0?leftUpInfo.withoutAbilityLength:-1;
            preUseAbilityMaxLength = leftUpInfo.withAbilityLength>=0?leftUpInfo.withAbilityLength:-1;
        }
        //2左
        Info leftInfo = getLengthWithCatch(matrix,row,col-1,dp);
        preNoAbilityMaxLength = Math.max(leftInfo.withoutAbilityLength,preNoAbilityMaxLength);
        preUseAbilityMaxLength = Math.max(leftInfo.withAbilityLength,preUseAbilityMaxLength);
        //3.左下
        if (row < matrix.length-1){
            Info leftDownInfo = getLengthWithCatch(matrix,row+1,col-1,dp);
            preNoAbilityMaxLength = Math.max(leftDownInfo.withoutAbilityLength,preNoAbilityMaxLength);
            preUseAbilityMaxLength = Math.max(leftDownInfo.withAbilityLength,preUseAbilityMaxLength);
        }
        //封装自己的Info
        int curUseMaxLength = -1;
        int curNoMaxLength = -1;
        //之前没用，现在可以用可以不用
        if (preNoAbilityMaxLength > 0){
            curNoMaxLength = preNoAbilityMaxLength + matrix[row][col];
            curUseMaxLength = preNoAbilityMaxLength - matrix[row][col];
        }
        //现在只能不用
        if (preUseAbilityMaxLength > 0){
            //更新用过的长度
            curUseMaxLength = Math.max(curUseMaxLength,preUseAbilityMaxLength + matrix[row][col]);
        }
        dp[row][col] =new Info(curUseMaxLength,curNoMaxLength);
        return dp[row][col];
    }
}

/**
 * @Author: 郜宇博

 * @Date: 2021/12/9 19:45
 * 给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右 括号，返回公式的计算结果。

 * str="48*((70-65)-43)+8*1"，返回-1816。

 */
public class Computer {
    public static void main(String[] args) {
        String expression = "48*((70-615)-43)+8*1";
        System.out.println(getComputeResult(expression));
    }
    /**
     * 递归，利用系统压栈特性存储 括号 内结果

     * @param expression
     * @return
     */
    public static int getComputeResult(String expression){
        char[] chars = expression.toCharArray();
        int[] partResult = getPartResult(chars, 0);
        return partResult[0];
    }
    //返回两个结果，【0】为计算结果，【1】为到达的位置，上一层递归从下一个位置开始
    public static int[] getPartResult(char[] chars,int cur){
        LinkedList<String> queue = new LinkedList<String>();
        int num = 0;
        while (cur < chars.length && chars[cur] != ')'){
            //是数字
            if (chars[cur] >= '0' && chars[cur] <= '9'){
                num = num * 10 + (chars[cur++] - '0');
            }else if (chars[cur] != '('){
                //运算符
                compute(queue,num);
                //压入运算符
                queue.addLast(String.valueOf(chars[cur++]));
                num = 0;
            }else {
                //左括号
                int[] partResult = getPartResult(chars, cur + 1);
                num = partResult[0];
                cur = partResult[1]+1;
            }
        }
        compute(queue,num);
        return new int[]{getQueueResult(queue),cur};
    }
    private static int getQueueResult(LinkedList<String> queue){
        int result = 0;
        boolean add = true;
        int num = 0;
        while (! queue.isEmpty()){
            String cur = queue.pollFirst();
            if ("+".equals(cur)){
                add = true;
            }else if ("-".equals(cur)){
                add = false;
            }else {
                num = Integer.parseInt(cur);
                result += add? num:(-num);
            }
        }
        return result;
    }
    private static void compute(LinkedList<String> queue, int num) {
        if (! queue.isEmpty()){
            String top = queue.pollLast();
            //如果是+，-就压入
            if ("+".equals(top) || "-".equals(top)){
                queue.addLast(top);
            }else {
                //乘除，就
                int cur = Integer.parseInt(queue.pollLast());
                num = "*".equals(top)? (num*cur):(cur/num);
            }
        }
        queue.addLast(String.valueOf(num));
    }
}

/**
 * @Author: 郜宇博

 * @Date: 2021/12/9 21:09
 * 请注意区分子串和子序列的不同，给定两个字符串str1和str2，求两个字符串的最长公共子串。

 * 动态规划空间压缩的技巧讲解

 */
public class LongestPublicChildArray {
    public static void main(String[] args) {
        String s1 = "ABC1234567MEFG";
        String s2 = "HILL1234567MNOP";
        System.out.println(getLength(s1, s2));
        System.out.println(getLengthBySpaceCompress(s1, s2));
    }

    public static int getLength(String s1, String s2) {
        //dp[i][j],表示s1以i结尾和s2以j结尾，构成的最长子串
        int[][] dp = new int[s1.length()][s2.length()];
        for (int i = 0; i < s2.length(); i++) {
            dp[0][i] = s1.charAt(0) == s2.charAt(i) ? 1 : 0;
        }
        for (int i = 1; i < s1.length(); i++) {
            for (int j = s2.length() - 1; j >= 0; j--) {
                boolean b = s2.charAt(j) == s1.charAt(i);
                if (j == 0) {
                    dp[i][0] = b ? 1 : 0;
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + (b ? 1 : 0);
                }
            }
        }
        return dp[s1.length() - 1][s2.length() - 1];
    }

    /**
     * 每行元素只和左上角有依赖
     * 从右上角开始，斜对角线，一直向左下走

     */
    public static String getLengthBySpaceCompress(String s1, String s2) {
        int row = 0;
        int col = s2.length() - 1;
        int max = 0;
        int end = 0;
        int length = 0;
        char[] chs1 = s1.toCharArray();
        char[] chs2 = s2.toCharArray();
        while (row < chs1.length) {
            int curRow = row;
            int curCol = col;
            length = 0;
            while (curRow < s1.length() && curCol < s2.length()){
                if (chs1[curRow] != chs2[curCol]){
                    length = 0;

                }else {
                    length++;
                }
                //可更新，记录end位置
                if (length > max){
                    end = curRow;
                    max = length;
                }
                curRow++;
                curCol++;
            }
            //起始点没到最左边，向左移动
            if (col > 0){
                col--;
            }else {
                //起始点在最左边，向下移动
                row++;
            }
        }
        return s1.substring(end-max+1,end+1);
    }
}